求兩個正整數(shù)最大公約數(shù)的算法

1、求兩個正整數(shù)求兩個正整數(shù)最大公約數(shù)的算法最大公約數(shù)的算法學習目標：學習目標：（）了解中國古代數(shù)學中求兩個正整數(shù)最大公約數(shù)的算法（）了解中國古代數(shù)學中求兩個正整數(shù)最大公約數(shù)的算法以及割圓術(shù)的算法；以及割圓術(shù)的算法；（）通過對（）通過對“更相減損之術(shù)更相減損之術(shù)”及及“割圓術(shù)割圓術(shù)”的學習，更好的學習，更好的理解將要解決的問題的理解將要解決的問題“算法化算法化”的思維方法，并注意理解推的思維方法，并注意理解推導導“割圓術(shù)割圓術(shù)”的操作步驟。的操作步驟。（3）學會借助實例分析，探究數(shù)學問題。）學會借助實例分析，探究數(shù)學問題。 人們在長期的生活，生產(chǎn)和勞動過程中，創(chuàng)人們在長期的生活，生產(chǎn)和勞動過程中，

2、創(chuàng)造了整數(shù)，分數(shù)，小數(shù)，正負數(shù)及其計算，以及造了整數(shù)，分數(shù)，小數(shù)，正負數(shù)及其計算，以及無限逼近任一實數(shù)的方法，在代數(shù)學，幾何學方無限逼近任一實數(shù)的方法，在代數(shù)學，幾何學方面，我國在宋，元之前也都處于世界的前列。我面，我國在宋，元之前也都處于世界的前列。我們在小學，中學學到的算術(shù)，代數(shù)，從記數(shù)到多們在小學，中學學到的算術(shù)，代數(shù)，從記數(shù)到多元一次聯(lián)立方程的求根方法，都是我國古代數(shù)學元一次聯(lián)立方程的求根方法，都是我國古代數(shù)學家最先創(chuàng)造的。更為重要的是我國古代數(shù)學的發(fā)家最先創(chuàng)造的。更為重要的是我國古代數(shù)學的發(fā)展有著自己鮮明的特色，也就是展有著自己鮮明的特色，也就是“寓理于算寓理于算”，即把解決的問題即

3、把解決的問題“算法化算法化”。本章的內(nèi)容是算法，。本章的內(nèi)容是算法，特別是在中國古代也有著很多算法案例，我們來特別是在中國古代也有著很多算法案例，我們來看一下并且進一步體會看一下并且進一步體會“算法算法”的概念。的概念。求最大公約數(shù)你能求出你能求出18與與30的公約數(shù)嗎的公約數(shù)嗎? 你能看出你能看出78與與36的公約數(shù)嗎的公約數(shù)嗎? 更相減損之術(shù)（指導閱讀課本更相減損之術(shù)（指導閱讀課本P27-P28）步驟：步驟： 以兩數(shù)中較大的數(shù)減去較小的數(shù)，即以兩數(shù)中較大的數(shù)減去較小的數(shù)，即；以差數(shù)和較小的數(shù)；以差數(shù)和較小的數(shù)3構(gòu)成新的一對數(shù)，對這一構(gòu)成新的一對數(shù)，對這一對數(shù)再用大數(shù)減去小數(shù)，即對數(shù)再用大數(shù)

4、減去小數(shù)，即,再以差數(shù)再以差數(shù)和較小的數(shù)構(gòu)成新的一對數(shù)，對這一對數(shù)再用大數(shù)減和較小的數(shù)構(gòu)成新的一對數(shù)，對這一對數(shù)再用大數(shù)減去小數(shù)，即去小數(shù)，即,繼續(xù)這一過程繼續(xù)這一過程,直到產(chǎn)生一對直到產(chǎn)生一對相等的數(shù)，這個數(shù)就是最大公約數(shù)相等的數(shù)，這個數(shù)就是最大公約數(shù) )36, 6()36,42()36,78()6 ,30()6 ,24()6 , 6()6 ,12()6 ,18(即，rbarbaba,rb,由由，得與有相同的公約數(shù)有相同的公約數(shù) 理論依據(jù)：理論依據(jù)：算法：算法：1S)(,baba輸入兩個正數(shù)輸入兩個正數(shù)2Sba 3S5S如果如果，則執(zhí)行則執(zhí)行，否則轉(zhuǎn)到否則轉(zhuǎn)到3Sba r將將的值賦予的值賦予

5、 4Srb barbra2S若若，則把則把賦予賦予，把把賦予賦予，否則把否則把賦予賦予，重新執(zhí)行重新執(zhí)行 5Sb輸出最大公約數(shù)輸出最大公約數(shù) 程序程序:a=input(“a=”)b=input(“b=”)while ab if a=b a=a-b; else b=b-a； endendprint(%io(2),a,b) 我國早期也有解決求最大公約數(shù)問題的算法，就是我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。更相減損術(shù)。更相減損術(shù)求最大公約數(shù)更相減損術(shù)求最大公約數(shù) 可半者半之，不可半者，副置分母分子之數(shù)，可半者半之，不可半者，副置分母分子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約以

6、少減多，更相減損，求其等也，以等數(shù)約之。之。 翻譯出來為：翻譯出來為： 第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用若是，用2約簡；若不是，執(zhí)行第二步。約簡；若不是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。公約數(shù)。 例例1 用更相減損術(shù)求用更相減損術(shù)求91與與49的最大

7、公約數(shù)的最大公約數(shù).更相減損術(shù)的應用更相減損術(shù)的應用 解：由于解：由于49不是偶數(shù)，把不是偶數(shù)，把91和和49以大數(shù)減小以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，數(shù)，并輾轉(zhuǎn)相減， 即：即：914842 49427 42735 35728 28721 21714 1477 所以，所以，91與與49的最大公約數(shù)是的最大公約數(shù)是7。 例例2 求兩個正數(shù)求兩個正數(shù)a=204和和b=85的最大的最大公約數(shù)。公約數(shù)。輾轉(zhuǎn)相除法求最大公約數(shù)輾轉(zhuǎn)相除法求最大公約數(shù) 分析：分析：204與與85兩數(shù)都比較大，而且兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都沒有明顯的公約數(shù)，如能把它們都變小一點，根據(jù)已有的知識即可求變小一點，

8、根據(jù)已有的知識即可求出最大公約數(shù)出最大公約數(shù) 20485234 顯然顯然204的最大公約數(shù)也必是的最大公約數(shù)也必是85的約數(shù)，的約數(shù)，同樣同樣204與與85的公約數(shù)也必是的公約數(shù)也必是34的約數(shù)，的約數(shù)，所以所以204與與85的最大公約數(shù)也是的最大公約數(shù)也是85與與34的最大公約數(shù)。的最大公約數(shù)。 8534217 34172+0 則則17為為204與與85的最大公約數(shù)。的最大公約數(shù)。輾轉(zhuǎn)相除法的基本步驟：第一步：用較大的數(shù)第一步：用較大的數(shù)m除以較小的數(shù)除以較小的數(shù)n得到得到一個商一個商q0和一個余數(shù)和一個余數(shù)r0；第二步：若第二步：若r00，則，則n為為m，n的最大公約的最大公約數(shù)；若數(shù)；若

9、r00，則用除數(shù)，則用除數(shù)n除以余數(shù)除以余數(shù)r0得到一得到一個商個商q1和一個余數(shù)和一個余數(shù)r1；第三步：若第三步：若r10，則，則r1為為m，n的最大公約的最大公約數(shù)；若數(shù)；若r10，則用除數(shù)，則用除數(shù)r0除以余數(shù)除以余數(shù)r1得到一得到一個商個商q2和一個余數(shù)和一個余數(shù)r2； 依次計算直至依次計算直至rn0，此時所得到的，此時所得到的rn1即即為所求的最大公約數(shù)。為所求的最大公約數(shù)。程序框圖：a=input(“a=”);b=input(“b=”);While modulo(a,b)0, r=modulo(a,b); a=b;b=r;endd=b開始開始輸入a,b求a除以b的余數(shù)ra=bb=r

10、r=0 ?結(jié)束結(jié)束輸出b是否程序：比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。明顯。 （2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為果是以相除余數(shù)為0則得到，而更相減損術(shù)則以則得到，而更相減損術(shù)則以減數(shù)與差相等而得到。減數(shù)與差相等而得到。鞏固運用鞏固運用 求求196和和147的最大公約數(shù)的最大公約數(shù) 回顧反思回顧反思 輾轉(zhuǎn)相除法是當大數(shù)被小數(shù)除盡時，結(jié)束除輾轉(zhuǎn)相除法是當大數(shù)被小數(shù)除盡時，結(jié)束除法運算，較小的數(shù)就是最大公約數(shù)法運算，較小的數(shù)就是最大公約數(shù) 更相減