高二數(shù)學(xué)必修3 算法案例(2) 教學(xué)目標(biāo)： （1）理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊(yùn)含的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析； （2）基本能根據(jù)算法語句與程序框圖的知識(shí)設(shè)計(jì)完整的程序框圖并寫出算法程序； 教學(xué)重點(diǎn)：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法 教學(xué)難點(diǎn)：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語言． 教學(xué)過程 一、問題情境 在初中，我們已經(jīng)學(xué)過求最大公約數(shù)的知識(shí)，你能求出18與30的公約數(shù)嗎？ 我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù)？這就是我們這一堂課所要探討的內(nèi)容． 二、算法設(shè)計(jì)思想： 1.輾轉(zhuǎn)相除法： 例1．求兩個(gè)正數(shù)8251和6105的最大公約數(shù)． （分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點(diǎn)，根據(jù)已有的知識(shí)即可求出最大公約數(shù)） 解：8251＝6105×1＋2146 顯然8251和的2146最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的約數(shù)，所以8251與6105的最大公約數(shù)也是6105與2146的最大公約數(shù)． 6105＝2146×2＋1813 2146＝1813×1＋333 1813＝333×5＋148 333＝148×2＋37 148＝37×4＋0 則37為8251與6105的最大公約數(shù)． 以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法．也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的．利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下： 第一步：用較大的數(shù)除以較小的數(shù)得到一個(gè)商和一個(gè)余數(shù)； 第二步：若，則為的最大公約數(shù)；若，則用除數(shù)除以余數(shù)得到一個(gè)商和一個(gè)余數(shù)； 第三步：若，則為的最大公約數(shù)；若，則用除數(shù)除以余數(shù)得到一個(gè)商和一個(gè)余數(shù)； …… 依次計(jì)算直至，此時(shí)所得到的即為所求的最大公約數(shù)． 練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù)（答案：53） 2.更相減損術(shù) 我國(guó)早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)． 更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之． 翻譯出來為： 第一步：任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)．若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步． 第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)．繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最大公約數(shù)． 例2． 用更相減損術(shù)求98與63的最大公約數(shù). 解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減， 即：98－63＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝14 14－7＝7 所以，98與63的最大公約數(shù)是7． 練習(xí)：用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù)．（答案：12） 3.比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 （1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯． （2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到． 三. 輾轉(zhuǎn)相除法的流程圖及偽代碼 利用輾轉(zhuǎn)相除法與更相減損術(shù)的計(jì)算算法，我們可以設(shè)計(jì)出程序框圖以及BSAIC程序來在計(jì)算機(jī)上實(shí)現(xiàn)輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)，下面由同學(xué)們?cè)O(shè)計(jì)相應(yīng)框圖并相互之間檢查框圖與程序的正確性，并在計(jì)算機(jī)上驗(yàn)證自己的結(jié)果． （1）輾轉(zhuǎn)相除法的程序框圖及程序 程序框圖： 輸出b 開始 輸入a,b 結(jié)束 偽代碼: 用較大的數(shù)除以較小的數(shù)，得到除式，直到. 四、回顧小結(jié)： 1．輾轉(zhuǎn)相除法與更相減損術(shù)中蘊(yùn)含的數(shù)學(xué)原理及算法語言的表示； 2．函數(shù)的含義． 五、課外作業(yè)： 課本第31頁第2 ；課本第35頁第13．