1.31輾轉(zhuǎn)相除法PPT學(xué)習(xí)教案

1、會計學(xué)1 1.31輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 一、三維目標(biāo) （a）知識與技能 1.理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊含的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析。 2.基本能根據(jù)算法語句與程序框圖的知識設(shè)計完整的程序框圖并寫出算法程序。 （b）過程與方法 在輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的學(xué)習(xí)過程中對比我們常見的約分求公因式的方法，比較它們在算法上的區(qū)別，并從程序的學(xué)習(xí)中體會數(shù)學(xué)的嚴(yán)謹(jǐn)，領(lǐng)會數(shù)學(xué)算法計算機處理的結(jié)合方式，初步掌握把數(shù)學(xué)算法轉(zhuǎn)化成計算機語言的一般步驟。 案例1 輾轉(zhuǎn)相除法與更相減損術(shù) 第1頁/共35頁 （c）情感態(tài)度與價值觀 1.通過閱讀中國古代數(shù)學(xué)中的算法案例，體會中國古代數(shù)學(xué)對世界數(shù)

2、學(xué)發(fā)展的貢獻(xiàn)。 2.在學(xué)習(xí)古代數(shù)學(xué)家解決數(shù)學(xué)問題的方法的過程中培養(yǎng)嚴(yán)謹(jǐn)?shù)倪壿嬎季S能力，在利用算法解決數(shù)學(xué)問題的過程中培養(yǎng)理性的精神和動手實踐的能力。 二、教學(xué)重難點 重點：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法。 難點：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語言。 三、學(xué)法 在理解最大公約數(shù)的基礎(chǔ)上去發(fā)現(xiàn)輾轉(zhuǎn)相除法與更相減損術(shù)中的數(shù)學(xué)規(guī)律，并能模仿已經(jīng)學(xué)過的程序框圖與算法語句設(shè)計出輾轉(zhuǎn)相除法程序框圖與算法程序。 第2頁/共35頁 3 5 9 15 問題1：在小學(xué)，我們已經(jīng)學(xué)過求最大公約數(shù) 的知識，你能求出18與30的最大公約數(shù)嗎？ 創(chuàng)設(shè)情景，揭示課題 18 302 3 18和

3、30的最大公約 數(shù)是23=6. 先用兩個數(shù)公有的質(zhì)因數(shù) 連續(xù)去除,一直除到所得 的商是互質(zhì)數(shù)為止,然后 把所有的除數(shù)連乘起來. 第3頁/共35頁 例：求下面兩個正整數(shù)的最大公約數(shù)： （1）求25和35的最大公約數(shù) （2）求49和63的最大公約數(shù) 25（1） 5 5 35 7 49（2） 7 7 63 9 所以，25和35的最大公約數(shù)為5所以，49和63的最大公約數(shù)為7 思考：除了用這種方法外還有沒有其它方法？ 第4頁/共35頁 問題2:我們都是利用找公約數(shù)的方法來求最大 公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察 又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們 的最大公約數(shù)？比如求8251與610

4、5的最大公約數(shù) ? 第5頁/共35頁 研探新知 1.輾轉(zhuǎn)相除法: 例1 求兩個正數(shù)8251和6105的最大公約數(shù)。 分析：8251與6105兩數(shù)都比較大，而且 沒有明顯的公約數(shù)，如能把它們都變小一點， 根據(jù)已有的知識即可求出最大公約數(shù). 解：825161051 2146 顯然8251與6105的最大公約數(shù)也必是 2146的約數(shù)，同樣6105與2146的公約數(shù)也必是 8251的約數(shù)，所以8251與6105的最大公約數(shù)也 是6105與2146的最大公約數(shù)。 第6頁/共35頁 研探新知 1.輾轉(zhuǎn)相除法: 例1 求兩個正數(shù)8251和6105的最大公約數(shù)。 解：825161051 2146; 61052

5、14621813; 214618131333; 333148237; 1483740. 則37為8251與6105的最大公約數(shù)。 以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn) 相除法。也叫歐幾里德算法，它是由歐幾里德 在公元前300年左右首先提出的。 第7頁/共35頁 完整的過程 8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0 例： 用輾轉(zhuǎn)相除法求225和135的最大公約 數(shù) 225=1351+90 135=901+45 90=452 顯然37是148和37的最

6、大公約 數(shù)，也就是8251和6105的最大 公約數(shù) 顯然45是90和45的最大公約數(shù)，也就是 225和135的最大公約數(shù) 思考1：從上面的兩個例子中可以看出 計算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù) S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù) S3：重復(fù)S1，直到余數(shù)為0 第8頁/共35頁 以上我們求最大公約數(shù)的 方法就是輾轉(zhuǎn)相除法也叫歐 幾里德算法，它是由歐幾里德 在公元前300年左右首先提出 的利用輾轉(zhuǎn)相除法求最大公 約數(shù)的。 第9頁/共35頁 練習(xí)1：利用輾轉(zhuǎn)相除法求兩數(shù)4081與 20723的最大公約數(shù). (53) 20723=40815+318; 4081=31812+265; 318=26

7、51+53; 265=535+0. 第10頁/共35頁 利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下： 第一步：用較大的數(shù)m除以較小的數(shù)n得到 一個商q0和一個余數(shù)r0；(m=nq0+r0) 第二步：若r00，則n為m，n的最大公約 數(shù)；若r00，則用除數(shù)n除以余數(shù)r0得到一個 商q1和一個余數(shù)r1；(n=r0q1+r1) 第三步：若r10，則r0為m，n的最大公約 數(shù)；若r10，則用除數(shù)r0除以余數(shù)r1得到一個 商q2和一個余數(shù)r2；(r0=r1q2+r2) 依次計算直至rn0，此時所得到的rn-1 即為所求的最大公約數(shù)。 第11頁/共35頁 (1)、算法步驟： 第一步：輸入兩個正整數(shù)m,n(mn)

8、. 第二步：計算m除以n所得的余數(shù)r. 第三步：m=n,n=r. 第四步：若r0,則m,n的最大公約數(shù)等于m； 否則轉(zhuǎn)到第二步. 第五步：輸出最大公約數(shù)m. 第12頁/共35頁 (2)、程序框圖： 開始 輸入m,n r=m MOD n m=n r=0? 是 否 n=r 輸出m 結(jié)束 第13頁/共35頁 (3)、程序： INPUT “m,n=“;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 第14頁/共35頁 否 4. 輾轉(zhuǎn)相除法的程序框圖及程序: 開始 輸入兩個正數(shù)m,n mn? r=m MOD n r0? 輸出n 結(jié)束 m=x m=n

9、 n=r 否 是 是 INPUT m,n IF mn THEN x=n n=m m=x END IF r=m MOD n WHILE r0 m=n n=r r=m MOD n WEND PRINT n END x=n n=m 第15頁/共35頁 2.更相減損術(shù): 我國早期也有解決求最大公約數(shù)問題的 算法，就是更相減損術(shù)。 更相減損術(shù)求最大公約數(shù)的步驟如下： 可半者半之，不可半者，副置分母子之?dāng)?shù)，以 少減多，更相減損，求其等也，以等數(shù)約之。 翻譯出來為：第一步：任意給出兩個正數(shù) ；判斷它們是否都是偶數(shù)。若是，用2約簡；若不 是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著 把較小的數(shù)與所得

10、的差比較，并以大數(shù)減小數(shù)。 繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個 數(shù)（等數(shù)）就是所求的最大公約數(shù)。 第16頁/共35頁 更相減損術(shù)算法步驟: 第四步：輸出最大公約數(shù)b. 第三步：如果br, 那么把b賦給a,把r賦給b; 否則把r賦給a，執(zhí)行第二步； 第二步：把a-b的差賦予r; 第一步：輸入兩個正整數(shù) a,b(ab,a,b都不是偶數(shù)); 第17頁/共35頁 例2 用更相減損術(shù)求98與63的最大公約數(shù). 解：由于63不是偶數(shù)，把98和63以大 數(shù)減小數(shù)，并輾轉(zhuǎn)相減， 即：986335; 633528; 35287; 28721; 21714; 1477. 所以，98與63的最大公約數(shù)是7。

11、 練習(xí)2：用更相減損術(shù)求兩個正數(shù)84與72的最 大公約數(shù)。 (12) 第18頁/共35頁 3.輾轉(zhuǎn)相除法與更相減損術(shù)的比較: （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ù)與差相等而得到. 第19頁/共35頁 （2）輾轉(zhuǎn)相除法算法步驟 第一步：輸入兩個正整數(shù)a,b(ab); 第二步：把a/b的余數(shù)賦給r; 第三步：如果r 0, 那么把b賦給a,把r賦給b,轉(zhuǎn) 到第二步;否則

12、轉(zhuǎn)到第四步； 第四步：輸出最大公約數(shù)b. 第20頁/共35頁 案例2 秦九韶算法 一、三維目標(biāo) （a）知識與技能 了解秦九韶算法的計算過程，并理解利用秦九韶算法可以減少計算次數(shù)提高計算效率的實質(zhì)。 （b）過程與方法 模仿秦九韶計算方法，體會古人計算構(gòu)思的巧妙. （c）情感態(tài)度與價值觀 通過對秦九韶算法的學(xué)習(xí)，了解中國古代數(shù)學(xué)家對數(shù)學(xué)的貢獻(xiàn)，充分認(rèn)識到我國文化歷史的悠久。 二、教學(xué)重難點 重點：1.秦九韶算法的特點; 難點: 2.秦九韶算法的先進(jìn)性理解 . 第21頁/共35頁 秦九韶（約1202-1261），字道古，四川安岳人。先后在湖北，安徽，江蘇，浙江等地做官，1261年左右被貶至梅州，（今

13、廣東梅縣），不久死于任所。他與李冶，楊輝，朱世杰并稱宋元數(shù)學(xué)四大家。早年在杭州“訪習(xí)于太史，又嘗從隱君子受數(shù)學(xué)”，1247年寫成著名的數(shù)書九章。數(shù)書九章全書凡18卷，81題，分為九大類。其最重要的數(shù)學(xué)成就-“大衍總數(shù)術(shù)”（一次同余組解法）與“正負(fù)開方術(shù)(高次方程數(shù)值解法），使這部宋代算經(jīng)在中世紀(jì)世界數(shù)學(xué)史上占有突出的地位。 第22頁/共35頁 教學(xué)設(shè)計 問題1設(shè)計求多項式f(x)=2x5-5x4-4x3+3x2-6x+7 當(dāng)x=5時的值的算法,并寫出程序. x=5 f=2x5-5x4-4x3+3x2-6x+7 PRINT f END 程 序 點評:上述算法一共做了15次乘法運算,5 次加法運算

14、.優(yōu)點是簡單,易懂;缺點是不通用,不 能解決任意多項多求值問題,而且計算效率不高. 第23頁/共35頁 這析計算上述多項式的值,一共需要9次 乘法運算,5次加法運算. 問題2有沒有更高效的算法? 分析:計算x的冪時,可以利用前面的計算 結(jié)果,以減少計算量, 即先計算x2,然后依次計算 222 ,(),()xx xxxxxxx 的值. 第二種做法與第一種做法相比,乘法的運 算次數(shù)減少了,因而能提高運算效率.而且對于 計算機來說,做一次乘法所需的運算時間比做一 次加法要長得多,因此第二種做法能更快地得到 結(jié)果. 第24頁/共35頁 問題3能否探索更好的算法,來解決任意多 項式的求值問題? f(x)

15、=2x5-5x4-4x3+3x2-6x+7 =(2x4-5x3-4x2+3x-6)x+7 =(2x3-5x2-4x+3)x-6)x+7 =(2x2-5x-4)x+3)x-6)x+7 =(2x-5)x-4)x+3)x-6)x+7 v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677 所以,當(dāng)x=5時,多項式的值是2677. 這種求多項式值的方法就叫秦九韶算法. 第25頁/共35頁 例1:用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x

16、+7當(dāng)x=5時的值. 解法一:首先將原多項式改寫成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7 v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677 所以,當(dāng)x=5時,多 項式的值是2677. 然后由內(nèi)向外逐層計算一次多項式的值,即 第26頁/共35頁 若將x的值代入變形后的式子中，那么求 值的計算過程是怎樣的? 計算的過程可以列表表示為： 多項式多項式x 系數(shù)系數(shù)254367 10251055402670 變形后變形后x 的的系

17、數(shù)系數(shù)25211085342677 f(x) =(2x5)x4)x+3)x6)x+7, x=5 第27頁/共35頁 2 -5 -4 3 -6 7 x=510 5 25 21 105 108 540 534 2670 2677 所以,當(dāng)x=5時,多項式的值是2677. 原多項式的系數(shù) 多項式的值. 例1:用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時的值. 解法二:列表 2 第28頁/共35頁 2 -5 0 -4 3 -6 0 x=510 5 25 25 125 121 605 608 3040 3034 所以,當(dāng)x=5時,多項式的值是15170. 練一練:用

18、秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)x=5時的值. 解:原多項式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0 列表 2 15170 15170 注意:n次多項式有n+1項,因此缺少哪一項 應(yīng)將其系數(shù)補0. 第29頁/共35頁 f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0. 我們可以改寫成如下形式: f(x)=(anx+an-1)x+an-2)x+a1)x+a0. 求多項式的值時,首先計算最內(nèi)層括號內(nèi) 一次多項式的值,即 v1=anx+an-1, 然后由內(nèi)向外逐層計算一次多項式的值,即 一般地,對于一個n次多項式 v2=v1x+an-2, v3=v2x+an-3, , vn=vn-1x+a0. 這樣,求n次多項式f(x)的值就轉(zhuǎn)化為求n 個一次多項式的值.這種算法稱為秦九韶算法. 第