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的最大公約數。主程序的代碼如下：

點擊綠旗運行程序，求得255和75的最大公約數是15。

更相損減法

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

更相損減法的算法步驟：

第一步：任意給定兩個正整數，判斷它們是否都是偶數。若是，則用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。

       請你試一試，用Scratch編寫一個名為“輾轉相減法”的模塊，用來求兩個數的最大公約數。