1、算法案例教案8（蘇教版必修3）第13課時142算法案例（2）教學(xué)目標(biāo)： （1）理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊(yùn)含的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析；（2）基本能根據(jù)算法語句與程序框圖的知識設(shè)計完整的程序 框圖并寫出算法程序；教學(xué)重點(diǎn)：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法 教學(xué)難點(diǎn)：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框 圖與程序語言教學(xué)過程一、問題情境 在初中，我們已經(jīng)學(xué)過求最大公約數(shù)的知識，你能求出18與30的公約數(shù)嗎？ 我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù) 比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又 應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與61

2、05的最大 公約數(shù)？這就是我們這一堂課所要探討的內(nèi)容、算法設(shè)計思想：1.輾轉(zhuǎn)相除法：例1求兩個正數(shù)8251和6105的最大公約數(shù)（分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約 數(shù)，如能把它們都變小一點(diǎn)，根據(jù)已有的知識即可求出最大 公約數(shù)）解：8251=6105X1+2146顯然8251和的2146最大公約數(shù)也必是2146的約數(shù)，同樣6105與21 46的公約數(shù)也必是8251的約數(shù)，所以8251與6105的最大公約數(shù)也是6105與2 1 46的最大公約數(shù)6105=2146X2+18132146=1813X1+3331813=333X5+148333=148X2+37148=37X4+

3、0則37為8251與6105的最大公約數(shù)以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法也叫歐幾里 德算法，它是由歐幾里德在公元前300年左右首先提出 的利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：第一步：用較大的數(shù)除以較小的數(shù)得到一個商和一個余數(shù)； 第二步：若，則為的最大公約數(shù)；若，則用除數(shù)除以余數(shù)得 到一個商和一個余數(shù)；第三步：若，則為的最大公約數(shù)；若，則用除數(shù)除以余數(shù)得到一個商和一個余數(shù)；依次計算直至，此時所得到的即為所求的最大公約數(shù) 練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù) （答案：53）2.更相減損術(shù) 我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損 術(shù)更相減損術(shù)求最大公約數(shù)

4、的步驟如下：可半者半之，不可半 者，副置分母之?dāng)?shù)，以少減多，更相減損，求其等也，以等 數(shù)約之翻譯出來為：第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)若是，用2約簡；若不是，執(zhí)行第二步第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得 的差比較，并以大數(shù)減小數(shù)繼續(xù)這個操作，直到所得的數(shù) 相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù) 例2 用更相減損術(shù)求98與63的最大公約數(shù).解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相 減，即：98-63=35 63-35=2835-28=7 28-7=2121-7=1414-7=7所以，98與63的最大公約數(shù)是7練習(xí)：用更相減損術(shù)求兩個正數(shù)8

5、4與72的最大公約數(shù)（ 案：12）3.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別（1）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為 主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次 數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū) 別較明顯（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余 數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到三.輾轉(zhuǎn)相除法的流程圖及偽代碼 利用輾轉(zhuǎn)相除法與更相減損術(shù)的計算算法，我們可以設(shè)計出 程序框圖以及BSAIC程序來在計算機(jī)上實現(xiàn)輾轉(zhuǎn)相除法與更 相減損術(shù)求最大公約數(shù)， 下面由同學(xué)們設(shè)計相應(yīng)框圖并相互 之間檢查框圖與程序的正確性，并在計算機(jī)上驗證自己的結(jié) 果（1）輾轉(zhuǎn)相除法的程序框圖及程序程序框圖：偽代碼:用較大的數(shù)除以較小的數(shù)，得