《高二數(shù)學(xué)必修3 算法案例(2)》由會(huì)員分享,可在線閱讀,更多相關(guān)《高二數(shù)學(xué)必修3 算法案例(2)(3頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、高二數(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的最
2、大公約數(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=14
3、8×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ó)早
4、期也有解決求最大公約數(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=
5、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.