【題記】

寶石雖落在泥土里，仍是寶石，砂粒雖被吹到天空中，還是砂粒。——莎士比亞不是有水的地方就有青蛙，但是青蛙叫的地方必定有水。——歌德

【配合教材】本探究配合“因數與倍數”。通過本探究能夠幫助學生鞏固所學知識，激發學生數學學習的興趣，讓學生學會舉一反三，培養學生思維的嚴密性和開放性，增強學生數學學習的信心，拓展學生數學學習的視野。【基本探究】同學們，我們在日常學習中，求的最大公因數一般都比較小，我們可以通過口算、短除法等來求出最大公因數。但是中國和西方的古代數學中，已有人有許多高人懂得更妙的求最大公因數的方法，今天我們就一起來見識一下吧。這兩種妙法分別叫“更相減損法”和“輾轉相除法”。一、更相減損法更相減損法：也叫更相減損術，是出自《九章算術》的一種求最大公因數的算法，它原本是為約分而設計的，但它適用于任何需要求最大公因數的場合。

《九章算術》是中國古代的數學專著，其中的“更相減損術”可以用來求兩個數的最大公因數，即“可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。”

翻譯成現代語言如下：第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用2約簡；若不是則執行第二步。第二步：以較大的數減較小的數，接著把所得的差與較小的數比較，并以大數減小數。繼續這個操作，直到所得的減數和差相等為止。則第一步中約掉的若干個2與第二步中等數的乘積就是所求的最大公因數。其中所說的“等數”，就是最大公因數。求“等數”的辦法是“更相減損”法。所以更相減損法也叫等值算法。說了半天，同學們可能聽得云里霧里吧，還是舉個例子來說吧。比如，用“更相減損術”求98與63的最大公因數，我們可以這樣進行——由于63不是偶數，把98和63以大數減小數，并輾轉相減：98-63=35，63-35=28，35-28=7，28-7=21，21-7=14，14-7=7，所以，98和63的最大公因數等于7。這個過程還可以簡單的寫為：(98，63)=(35，63)=(35，28)=(7，28)=(7，21)=(7，14)=(7，7)=7.

二、輾轉相除法“輾轉相除法”是求兩個自然數的最大公因數的一種方法，也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。用“輾轉相除法”求幾個數的最大公因數，可以先求出其中任意兩個數的最大公因數，再求這個最大公因數與第三個數的最大公因數，依次求下去，直到最后一個數為止。最后所得的那個最大公因數，就是所有這些數的最大公因數。我們也來舉個例子。比如，求319與377的最大公因數。注意求最大公因數也可以簡寫成：(319，377)=？過程如下——∵ 319÷377=0(余319)，∴(319，377)=(377，319)；∵ 377÷319=1(余58)，∴(377，319)=(319，58)；∵ 319÷58=5(余29)，∴ (319，58)=(58，29)；∵ 58÷29=2(余0)，∴ (58，29)= 29；∴ (319，377)=29。【指點迷津】更相減損術與輾轉相除法的區別在哪里呢？首先，它們都是求最大公因數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。其次，從結果體現形式來看，輾轉相除法體現結果是以相除余數為0則得到，而更相減損術則以減數與差相等而得到。【探究進階】1．請同學們試著用“更相減損術”求260和104的最大公因數。2．請同學們試著用“輾轉相除法”求8251和6105的最大公因數。【參考答案】1．由于260和104均為偶數，首先用2約簡得到130和52，再用2約簡得到65和26。此時65是奇數而26不是奇數，故把65和26輾轉相減：65-26=39，39-26=13，26-13=13，所以260與104的最大公因數等于13乘以第一步中約掉的兩個2，即13×2×2=52。這個過程可以簡單地寫為：(260，104)(/2/2) =>(65，26)=(39，26)=(13，26)=(13，13)=13，13×2×2=52。2．因為8251＝6105×1＋2146，所以8251與6105的最大公因數也必是2146的因數，同樣6105與2146的公因數也必是8251的因數，所以8251與6105的最大公因數也是6105與2146的最大公因數。于是有：6105＝2146×2＋1813，2146＝1813×1＋333，1813＝333×5＋148，333＝148×2＋37，148＝37×4＋0，所以37就是8251與6105的最大公因數。

50個高年級數學【游戲與探究】(二)，一定要收藏

50個高年級數學【游戲與探究】(一)，一定要收藏

81個中年級數學【游戲與探究】(二)，一定要收藏

81個中年級數學【游戲與探究】(一)，一定要收藏

92個低年級數學【游戲與探究】，一定要收藏?

總結

以上是生活随笔為你收集整理的c语言辗转相除法求最大公约数_趣味探究：妙法求“最大公因数”，比书上难一点，你敢挑战吗？（适合56年级）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。