歐幾里德算法和更相減損術:用Scratch實現古老的數學算法2018-11-28 由 scratch少兒編程教程 發表于資訊 【問題】 輸入兩個正整數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 | 輾轉相除法【最大公因數】 |