歐幾里德算法和更相減損術：用Scratch實現古老的數學算法

2018-11-28 由 scratch少兒編程教程 發表于資訊

有兩個自然數a和b，如果a能被b整除，那麼，b就叫做a的約數。

兩個或多個自然數的共有約數中最大的一個，叫做它們的最大公約數，也稱最大公因數、最大公因子。

求最大公約數有多種方法，常見的有

質因數分解法、

短除法、

輾轉相除法、

輾轉相減法、

更相減損法等。

【問題】

輸入兩個正整數a和b，求它們的最大公約數。

【編程解題】

下面小海豚科學館將分別介紹使用輾轉相除法、更相減損法來求兩個數的最大公約數。

輾轉相除法

輾轉相除法，又稱歐幾里德算法，用於計算兩個正整數a、b的最大公約數。它是已知最古老的算法，其可追溯至公元前300年前。

輾轉相除法的算法步驟是，對於給定的兩個正整數a、b（a>b），用a除以b得到餘數c。若餘數c不為0，就將b和c構成新的一對數（a=b，b=c），繼續上面的除法，直到餘數c為0，這時b就是原來兩個數的最大公約數。

因為這個算法需要反覆進行除法運算，故被形象地命名為「輾轉相除法」。

小海豚科學館舉例說明，用輾轉相除法求255和75的最大公約數。

給定兩個數：255，75

第一次：用255除75，餘30；

第二次：用75除30，餘15；

第三次：用30除15，餘0；

這時就得到255和75的最大公約數是15。

下面小海豚科學館把輾轉相除法的算法用流程圖表示如下。

註： a mod b ，即 a 除以 b 的餘數。

根據上面的算法步驟，我們編寫一個名為「輾轉相除法」的模塊，用來求兩個數的最大公約數。該模塊的完整代碼如下：

下面小海豚科學館帶你編寫調用「輾轉相除法」模塊的主程序，用來求255和75的最大公約數。主程序的代碼如下：

更相損減法

《九章算術》是中國古代的數學專著，其中的「更相減損術」可以用來求兩個數的最大公約數。該書成於公元一世紀左右，書中內容十分豐富，系統總結了戰國、秦、漢時期的數學成就。

小海豚科學館向你介紹更相損減法的算法步驟：

第一步：任意給定兩個正整數，判斷它們是否都是偶數。若是，則用2約簡；若不是則執行第二步。

第二步：以較大的數減較小的數，接著把所得的差與較小的數比較，並以大數減小數。繼續這個操作，直到所得的差和減數相等為止。

第三步：最後把第一步中約掉的若干個2與第二步中等數的乘積就是所求的最大公約數。

這裡所說的「等數」，就是最大公約數，求「等數」的辦法就是「更相減損法」，所以，更相減損法也叫等值算法。

小海豚科學館舉例說明，用更相減損術求260和104的最大公約數。

第一步：由於260和104均為偶數，首先用2約簡得到130和52，再用2約簡得到65和26。

第二步：此時65是奇數，而26不是奇數，故把65和26輾轉相減：

65－26＝39

39－26＝13

26－13＝13

第三步：最後把第一步中約掉的兩個2和「等數」13相乘：

13×2×2＝52

所以，260與104的最大公約數是52。

下面小海豚科學館把更相減損法的算法用流程圖表示。

註：GCD，即最大公約數。

根據上面的算法步驟，我們編寫一個名為「更相減損法」的模塊，用來求兩個數的最大公約數。該模塊的完整代碼如下：

下面，小海豚科學館帶你編寫調用「更相減損法」模塊的主程序，用來求260和104的最大公約數。主程序的代碼如下：

點擊綠旗運行程序，求得260和104的最大公約數是52。

---

輾轉相減法

如果去掉「更相減損法」中對兩個正整數均為偶數時做的除法運算，只保留減法運算，也能求出兩數的最大公約數。

這種方法叫輾轉相減法，即尼考曼徹斯法，其特色是做一系列減法，從而求得最大公約數。

例如：用輾轉相減法求兩個自然數35和14的最大公約數。

35 – 14 = 21 用大數減去小數

21 – 14 = 7 7小於14，要做一次交換，把14作為被減數

14 – 7 = 7 求得「等數」，這樣也就求出了最大公約數7。

原文網址：https://kknews.cc/news/jeya3xl.html