1、輾轉(zhuǎn)相除法與更相減損術(shù)【教學目標】：理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊含的數(shù)學原理，并能根據(jù)這些原理進行算法分析。 基本能根據(jù)算法語句與程序框圖的知識設(shè)計完整的程序框圖并寫出算法程序?！窘虒W重點】理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法?！窘虒W難點】把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語言?！緦W法與教學用具】：學法：比較輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)在算法上的區(qū)別，并從程序的學習中體會數(shù)學的嚴謹，領(lǐng)會數(shù)學算法計算機處理的結(jié)合方式，初步掌握把數(shù)學算法轉(zhuǎn)化成計算機語言的一般步驟。教學用具:計算機，TI-voyage200圖形計算器【教學過程】提出問題：在小學，我們已經(jīng)學過求最大公

2、約數(shù)的知識，如口算求出12與20的公約數(shù)。分析：我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù)？這就是我們這一堂課所要探討的內(nèi)容。輾轉(zhuǎn)相除法例1 求兩個正數(shù)8251和6105的最大公約數(shù)。分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，可以把它們都變小一點，根據(jù)已有的知識即可求出最大公約數(shù)8251610512146顯然8251的最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的約數(shù)，所以8251與6105的最大公約數(shù)也是6105與21

3、46的最大公約數(shù)。6105214621813214618131333181333351483331482371483740則37為8251與6105的最大公約數(shù)。以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：（1）：用較大的數(shù)m除以較小的數(shù)n得到一個商和一個余數(shù)；（2）：若0，則n為m，n的最大公約數(shù)；若0，則用除數(shù)n除以余數(shù)得到一個商和一個余數(shù)；（3）：若0，則為m，n的最大公約數(shù)；若0，則用除數(shù)除以余數(shù)得到一個商和一個余數(shù)；依次計算直至0，此時所得到的即為所求的最大公約數(shù)。其程序框圖見課本其程

4、序語言（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圖形計算器操作：（老師現(xiàn)場指導）運行輸入不同的m、n都可以算出它們的最大公約數(shù)。這下子，學生會感到自己變得神通廣大了。利用TI-voyage200圖形計算器更能培養(yǎng)學生的動手操作能力，并讓他們獲得完成程序后的成功感！更相減損術(shù)我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。在九章算術(shù)中記載了更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置分

5、母子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯為：（1）：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。（2）：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。例2 用更相減損術(shù)求98與63的最大公約數(shù).分析：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：9863356335283528728721217141477所以，98與63的最大公約數(shù)是7。學生利用TI-voyage200圖形計算器操作：（老師現(xiàn)場指導）運行（其中“dashu”指輸入數(shù)值大的整數(shù)，“ xiaoshu”指數(shù)值小的整數(shù)，學生課余時間可以繼續(xù)修改） 輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相