Question

用輾轉相除法求8 251與6 105的最大公約數,寫出算法分析，畫出程序框圖，寫出算法程序.

Answer 1

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

由此可得，6 105與2 146的公約數也是8 251與6 105的公約數，反過來，8 251與6 105的公約數也是6 105與2 146的公約數，所以它們的最大公約數相等.

對6 105與2 146重復上述步驟：6 105=2 146×2+1 813.

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

2 146=1 813×1+333，

1 813=333×5+148，

333=148×2+37，

148=37×4.

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

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

算法分析：從上面的例子可以看出，輾轉相除法中包含重復操作的步驟，因此可以用循環結構來構造算法.

算法步驟如下：

第一步，給定兩個正整數m，n.

第二步，計算m除以n所得的余數為r.

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

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

程序框圖如下圖：

程序：

INPUT  m,n

DO

  r=m MOD n

  m=n

  n=r

LOOP UNTIL r=0

PRINT m

END

點評：從教學實踐看，有些學生不能理解算法中的轉化過程，例如：求8 251與6 105的最大公約數,為什么可以轉化為求6 105與2 146的公約數.因為8 251=6 105×1+2 146，

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