04.02更相減損法


歐幾里德算法和更相減損術:用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的最大公約數。主程序的代碼如下:




點擊綠旗運行程序,求得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。



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

更相減損術

輾轉相除法【最大公因數】

更相減損法


Comments