介绍e2大二上习题.pdfVIP

P1815.2

E2.Thegreatestcommondivisor()oftwopositiveintegersisthelargestinteger

thatdividesbothofthem.Thus,forexample,theof8and12is4,theof9and

18is9,andtheof16and25is1.

(a)Writeanonrecursivefunctionint(intx,inty),wherexandyarerequiredto

bepositiveintegers,thatsearchesthroughthepositiveintegersuntilitfindsthe

largestintegerdividingbothxandy.

Answerint(intx,inty)

/*Pre:Integersxandyarebothpositive.

Post:Thegreatestcommonddivisorofxandyisreturned.*/

{

int=1;

inttest=2;

while(testxtesty){

if((x%test0)(y%test0))

=test;

test++;

}

return;

}

(b)Writearecursivefunctionint(intx,inty)thatimplementsEuclid’s

algorithm:Ify=0,thentheofxandyisx;otherwisetheofxandyisthe

sameastheofyandx%y.

Answerint(intx,inty)

/*Pre:Integersxandyarebothatleast0,andtheyarenotbothequalto0，

andmakesurethatxislargerthanorequaltoy.

Post:Thegreatestcommonddivisorofxandyisreturned.*/

{

if(y0)returnx;

return(y,x%y);

}

(c)Rewritethefunctionofpart(b)intoiterativeform.

Answerint(intx,inty)

/*Pre:Integersxandyarebothatleast0,andtheyarenotbothequalto0.

Post:Thegreatestcommonddivisorofxandyisreturned.*/

{

inttemp;

if(xy){temp=x;x=y;y=x;}

while(y0){

temp=x;

x=y;

y=temp%y;

}

returnx;

}

(d)Discusstheadvantagesanddisadvantagesofeachofthesemethods.

Answer(a)比较容易理解，但效率较低。

(b)(c)采用欧几里得辗转相处算法，循环次数减少。b中由于采用了递归，需要

的时间和空间。

P1815.2

E2.两个正整数的最大共同除数（）是最