1、Good is good, but better carries it.精益求精，善益求善。k51.3.1 輾轉相除法與更相減損術(珠海市斗門和風中學 鄺國均)1本文為自本人珍藏 版權所有 僅供參考13輾轉相除法與更相減損術珠海市斗門和風中學 鄺國均【教學目標】：（1） 理解輾轉相除法與更相減損術中蘊含的數學原理，并能根據這些原理進行算法分析。 （2） 基本能根據算法語句與程序框圖的知識設計完整的程序框圖并寫出算法程序。【教學重點】理解輾轉相除法與更相減損術求最大公約數的方法。【教學難點】把輾轉相除法與更相減損術的方法轉換成程序框圖與程序語言。【學法與教學用具】：學法：比較輾轉相除法與更相減損

2、術求最大公約數在算法上的區別，并從程序的學習中體會數學的嚴謹，領會數學算法計算機處理的結合方式，初步掌握把數學算法轉化成計算機語言的一般步驟。教學用具:計算機，TI-voyage200圖形計算器【教學過程】提出問題：在小學，我們已經學過求最大公約數的知識，如口算求出12與20的公約數。分析：我們都是利用找公約數的方法來求最大公約數，如果公約數比較大而且根據我們的觀察又不能得到一些公約數，我們又應該怎樣求它們的最大公約數？比如求8251與6105的最大公約數？這就是我們這一堂課所要探討的內容。輾轉相除法例1 求兩個正數8251和6105的最大公約數。分析：8251與6105兩數都比較大，而且沒有

3、明顯的公約數，可以把它們都變小一點，根據已有的知識即可求出最大公約數8251610512146顯然8251的最大公約數也必是2146的約數，同樣6105與2146的公約數也必是8251的約數，所以8251與6105的最大公約數也是6105與2146的最大公約數。6105214621813214618131333181333351483331482371483740則37為8251與6105的最大公約數。以上我們求最大公約數的方法就是輾轉相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。利用輾轉相除法求最大公約數的步驟如下：（1）：用較大的數m除以較小的數n得到一個商和一個

4、余數；（2）：若0，則n為m，n的最大公約數；若0，則用除數n除以余數得到一個商和一個余數；（3）：若0，則為m，n的最大公約數；若0，則用除數除以余數得到一個商和一個余數；依次計算直至0，此時所得到的即為所求的最大公約數。其程序框圖見課本其程序語言（BASIC）如下：INPUT “m=”;mINPUT “n=”;nIF m MOD n=nn=xEND IFr=m MOD nWHILE r0 r=m MOD nm=nn=rWENDPRINT mEND學生利用TI-voyage200圖形計算器操作：（老師現場指導）運行輸入不同的m、n都可以算出它們的最大公約數。這下子，學生會感到自己變得神通廣大

5、了。利用TI-voyage200圖形計算器更能培養學生的動手操作能力，并讓他們獲得完成程序后的成功感！更相減損術我國早期也有解決求最大公約數問題的算法，就是更相減損術。在九章算術中記載了更相減損術求最大公約數的步驟：可半者半之，不可半者，副置分母子之數，以少減多，更相減損，求其等也，以等數約之。翻譯為：（1）：任意給出兩個正數；判斷它們是否都是偶數。若是，用2約簡；若不是，執行第二步。（2）：以較大的數減去較小的數，接著把較小的數與所得的差比較，并以大數減小數。繼續這個操作，直到所得的數相等為止，則這個數（等數）就是所求的最大公約數。例2 用更相減損術求98與63的最大公約數.分析：由于63不

6、是偶數，把98和63以大數減小數，并輾轉相減，即：9863356335283528728721217141477所以，98與63的最大公約數是7。學生利用TI-voyage200圖形計算器操作：（老師現場指導）運行（其中“dashu”指輸入數值大的整數，“ xiaoshu”指數值小的整數，學生課余時間可以繼續修改） 輾轉相除法與更相減損術的區別：（1）都是求最大公約數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。（2）從結果體現形式來看，輾轉相除法體現結果是以相除余數為0則得到，而更相減損術則以減