輾轉(zhuǎn)相除法與更相減損術(shù)

1、輾轉(zhuǎn)相除法與更相減損術(shù)一、教學(xué)設(shè)計:本節(jié)教學(xué)讓學(xué)生通過操作、探索，經(jīng)歷“寫出算法步驟、畫出程序框圖、編制程序、上機驗證”的全過程，給學(xué)生提供探索與交流的時空（活動的時間，思維的空間），真正使學(xué)生經(jīng)歷問題的提出過程、感受知識的形成與發(fā)展過程、暴露問題解決的思維過程、體驗成功的喜悅過程，使學(xué)生形成發(fā)現(xiàn)與解決問題的能力、養(yǎng)成良好的學(xué)習(xí)習(xí)慣、掌握必備的數(shù)學(xué)知識，從而達到知識與技能、過程與方法、情感與態(tài)度三位一體的統(tǒng)一。 二、教學(xué)目標：（a）知識與技能1. 解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊含的算法思想。2.基本能根據(jù)算法語句與程序框圖的知識設(shè)計完整的程序框圖并寫出算法程序。（b）過程與方法1、通過操作、探索

2、，經(jīng)歷“寫出算法步驟、畫出程序框圖、編制程序、上機驗證”的全過程。2、對比用輾轉(zhuǎn)相除法與更相減損術(shù)求兩數(shù)的最大公約數(shù)的方法，比較它們在算法上的區(qū)別，并從程序的學(xué)習(xí)中體會數(shù)學(xué)的嚴謹。（c）情態(tài)與價值1.通過閱讀中國古代數(shù)學(xué)中的算法案例，體會中國古代數(shù)學(xué)對世界數(shù)學(xué)發(fā)展的貢獻。2. 在利用算法解決數(shù)學(xué)問題的過程中培養(yǎng)嚴謹?shù)倪壿嬎季S能力和動手實踐的能力。3.在合作學(xué)習(xí)的過程中體驗合作的愉快和成功的喜悅。三、教學(xué)重難點重點：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法。難點：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語言。四、學(xué)法與教學(xué)用具學(xué)法：在理解最大公約數(shù)的基礎(chǔ)上去發(fā)現(xiàn)輾轉(zhuǎn)相除法與更相減損

3、術(shù)中的數(shù)學(xué)規(guī)律，并能模仿已經(jīng)學(xué)過的程序框圖與算法語句設(shè)計出輾轉(zhuǎn)相除法與更相減損術(shù)的程序框圖與算法程序。教學(xué)用具：電腦五、教學(xué)過程（一）創(chuàng)設(shè)游戲，激發(fā)興趣動畫播放（配語音）：希臘人常以線段代表數(shù)。甲乙兩數(shù)可以看成長度分別為甲乙兩數(shù)的直尺。輾轉(zhuǎn)相除的意思就是拿矩尺去量長尺；若有剩余，再用剩余部分為尺，去量原來的短尺，如此繼續(xù)下去。如果兩尺長度之比為有理數(shù)，經(jīng)過輾轉(zhuǎn)相量，在有限次內(nèi)，總會有量盡的時候。若用最后量盡時所用的尺回頭分別來量原來的兩把尺，也是會量盡的。希臘人就說這兩把尺（兩個線段、兩個數(shù)）是可共度的。（用代數(shù)的觀點來看，若兩線段的長度比為m：n，m、n都是整數(shù)，則把第一線段等分所得的小線段

4、，可以同時量盡這兩線段。）原先希臘人以為任何兩線段都是可共度的，后來才發(fā)現(xiàn)問題不那么簡單。游戲：這里有一個公升及一個公升的無刻度容器,如何到水邊裝回恰好公升的水。3公升5公升步驟:(1)裝滿公升的水(2)將公升的水倒入公升的容器中(3)倒掉公升的水 (4)將大容器中的公升倒入公升的容器中(5)再裝滿公升的水  (6)由大容器中的水倒?jié)M小容器最后,大容器所剩下來的水就是公升. （二）創(chuàng)設(shè)情景，揭示課題1.教師首先提出問題：在初中，我們已經(jīng)學(xué)過求最大公約數(shù)的知識，你能求出18與30的公約數(shù)嗎？2.接著教師進一步提出問題，我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公

5、約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù)？這就是我們這一堂課所要探討的內(nèi)容。（二）研探新知 1.輾轉(zhuǎn)相除法例1 求兩個正數(shù)8251和6105的最大公約數(shù)。（分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點，根據(jù)已有的知識即可求出最大公約數(shù)）解：82516105×12146顯然8251的最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的約數(shù)，所以8251與6105的最大公約數(shù)也是6105與2146的最大公約數(shù)。61052146×21813

6、21461813×#215;5148333148×23714837×40則37為8251與6105的最大公約數(shù)。以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：第一步：用較大的數(shù)m除以較小的數(shù)n得到一個商q0和一個余數(shù)r0；第二步：若r00，則n為m，n的最大公約數(shù)；若r00，則用除數(shù)n除以余數(shù)r0得到一個商q1和一個余數(shù)r1；第三步：若r10，則r1為m，n的最大公約數(shù)；若r10，則用除數(shù)r0除以余數(shù)r1得到一個商q2和一個余數(shù)r2；依次計算直

7、至rn0，此時所得到的rn1即為所求的最大公約數(shù)。練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù)（答案：53）2.更相減損術(shù)我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。播放：更相減損術(shù)最早的文字記載見于九章算術(shù)“方田”章“約分術(shù)”，用于求一個分數(shù)的分子、分母的最大公約數(shù)后又被中國古代數(shù)學(xué)家推廣應(yīng)用于求最小公倍數(shù)、解一次不定方程和一次同余式組以及解線性方程組等更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母·子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第

8、二步。第二步：以較大的數(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。練習(xí)：用更相減損術(shù)求兩個正數(shù)84與72的最大公約數(shù)。（答案：12）3.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小

9、區(qū)別較大時計算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到4. 輾轉(zhuǎn)相除法與更相減損術(shù)計算的程序框圖及程序利用輾轉(zhuǎn)相除法與更相減損術(shù)的計算算法，我們可以設(shè)計出程序框圖以及BSAIC程序來在計算機上實現(xiàn)輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)，下面由同學(xué)們設(shè)計相應(yīng)框圖并相互之間檢查框圖與程序的正確性，并在計算機上驗證自己的結(jié)果。（1）輾轉(zhuǎn)相除法的程序框圖及程序開始Yr=m MOD n輸出nYN輸入兩個正整數(shù)m,nr=0結(jié)束m>nx=nn=mm=xNm=nn=r 程序框圖：程序：INPUT “m=”;mINPUT “n=”

10、;nIF m>n THEN x=mm=nn=xEND IFr=m MOD nWHILE r<>0 r=m MOD nm=nn=rWENDPRINT nEND更相減損術(shù)的程序框圖及程序INPUT m,n"m,nDOIF m<n THENr=mm=nn=rEND IFm=m-nLOOP UNTIL m=0PRINT "GCD="nEND5.課堂練習(xí)一.用輾轉(zhuǎn)相除法求下列各組數(shù)的最大公約數(shù)，并在自己編寫的BASIC程序中驗證。（1）225；135 （2）98；196 （3）72；168 （4）153；119二、解答課前的游戲6.小結(jié)：輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的計