Question

用輾轉(zhuǎn)相除法求8 251與6 105的最大公約數(shù),寫(xiě)出算法分析，畫(huà)出程序框圖，寫(xiě)出算法程序.

Answer 1

解：用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)：8 251=6 105×1+2 146.

由此可得，6 105與2 146的公約數(shù)也是8 251與6 105的公約數(shù)，反過(guò)來(lái)，8 251與6 105的公約數(shù)也是6 105與2 146的公約數(shù)，所以它們的最大公約數(shù)相等.

對(duì)6 105與2 146重復(fù)上述步驟：6 105=2 146×2+1 813.

同理，2 146與1 813的最大公約數(shù)也是6 105與2 146的最大公約數(shù).繼續(xù)重復(fù)上述步驟：

2 146=1 813×1+333，

1 813=333×5+148，

333=148×2+37，

148=37×4.

    最后的除數(shù)37是148和37的最大公約數(shù)，也就是8 251與6 105的最大公約數(shù).

    這就是輾轉(zhuǎn)相除法.由除法的性質(zhì)可以知道，對(duì)于任意兩個(gè)正整數(shù)，上述除法步驟總可以在有限步之后完成，從而總可以用輾轉(zhuǎn)相除法求出兩個(gè)正整數(shù)的最大公約數(shù).

算法分析：從上面的例子可以看出，輾轉(zhuǎn)相除法中包含重復(fù)操作的步驟，因此可以用循環(huán)結(jié)構(gòu)來(lái)構(gòu)造算法.

算法步驟如下：

第一步，給定兩個(gè)正整數(shù)m，n.

第二步，計(jì)算m除以n所得的余數(shù)為r.

第三步，m=n，n=r.

第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步.

程序框圖如下圖：

程序：

INPUT  m,n

DO

  r=m MOD n

  m=n

  n=r

LOOP UNTIL r=0

PRINT m

END

點(diǎn)評(píng)：從教學(xué)實(shí)踐看，有些學(xué)生不能理解算法中的轉(zhuǎn)化過(guò)程，例如：求8 251與6 105的最大公約數(shù),為什么可以轉(zhuǎn)化為求6 105與2 146的公約數(shù).因?yàn)? 251=6 105×1+2 146，

可以化為8 251-6 105×1=2 164，所以公約數(shù)能夠整除等式兩邊的數(shù)，即6 105與2 146的公約數(shù)也是8 251與6 105的公約數(shù).