1、1.3.1 輾轉(zhuǎn)相除法與更相減損術(shù)、 秦九韶算法,教學(xué)目標(biāo) 1.理解算法案例的算法步驟和程序框圖. 2.引導(dǎo)學(xué)生得出自己設(shè)計(jì)的算法程序. 3.體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達(dá)能力. 重點(diǎn)難點(diǎn) 教學(xué)重點(diǎn)：引導(dǎo)學(xué)生得出自己設(shè)計(jì)的算法步驟、程序框圖和算法程序. 教學(xué)難點(diǎn)：體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學(xué)表達(dá)能力.,1.輾轉(zhuǎn)相除法與更相減損術(shù),3 5,9 15,問題1：在小學(xué)，我們已經(jīng)學(xué)過求最大公約數(shù)的知識，你能求出18與30的最大公約數(shù)嗎？,創(chuàng)設(shè)情景，揭示課題,18 30,2,3,18和30的最大公約數(shù)是23=6.,先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連

2、續(xù)去除,一直除到所得的商是互質(zhì)數(shù)為止,然后把所有的除數(shù)連乘起來.,問題2:我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？比如求8251與6105的最大公約數(shù).,研探新知,1.輾轉(zhuǎn)相除法:,例1 求兩個(gè)正數(shù)8251和6105的最大公約數(shù).,分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點(diǎn)，根據(jù)已有的知識即可求出最大公約數(shù).,解：8251610512146,顯然8251與6105的最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的約數(shù)，所以8251與61

3、05的最大公約數(shù)也是6105與2146的最大公約數(shù).,研探新知,1.輾轉(zhuǎn)相除法:,例1 求兩個(gè)正數(shù)8251和6105的最大公約數(shù).,解：8251610512146;,6105214621813; 214618131333; 333148237; 1483740.,則37為8251與6105的最大公約數(shù).,以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法.也叫歐幾里得算法，它是由歐幾里得在公元前300年左右首先提出的.,利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：,第一步：用較大的數(shù)m除以較小的數(shù)n得到一個(gè)商q0和一個(gè)余數(shù)r0；(m=nq0+r0) 第二步：若r00，則n為m，n的最

4、大公約數(shù)；若r00，則用除數(shù)n除以余數(shù)r0得到一個(gè)商q1和一個(gè)余數(shù)r1；(n=r0q1+r1) 第三步：若r10，則r0為m，n的最大公約數(shù)；若r10，則用除數(shù)r0除以余數(shù)r1得到一個(gè)商q2和一個(gè)余數(shù)r2；(r0=r1q2+r2) 依次計(jì)算直至rn0，此時(shí)所得到的rn-1 即為所求的最大公約數(shù).,練習(xí)1：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù).,提示：53,20723=40815+318; 4081=31812+265; 318=2651+53; 265=535+0.,2.更相減損術(shù):,我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù).,更相減損術(shù)求最大公約數(shù)的步驟如下：可

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

6、：用更相減損術(shù)求兩個(gè)正數(shù)84與72的最大公約數(shù).,提示：12,3.輾轉(zhuǎn)相除法與更相減損術(shù)的比較:,（1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主;計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯. （2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0而得到，而更相減損術(shù)則以減數(shù)與差相等而得到.,否,4. 輾轉(zhuǎn)相除法的程序框圖及程序:,開始,輸入兩個(gè)正整數(shù)m,n,mn?,r=m MOD n,r0?,輸出n,結(jié)束,m=x,m=n,n=r,否,是,是,x=n,n=m,2.秦九韶算法,教學(xué)設(shè)計(jì),問題1設(shè)計(jì)求多項(xiàng)式f(x)=2

7、x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)的值的算法,并寫出程序.,點(diǎn)評:上述算法一共做了15次乘法運(yùn)算,5次加法運(yùn)算.優(yōu)點(diǎn)是簡單,易懂;缺點(diǎn)是不通用,不能解決任意多項(xiàng)式求值問題,而且計(jì)算效率不高.,這樣計(jì)算上述多項(xiàng)式的值,一共需要5次乘法運(yùn)算,5次加法運(yùn)算.,問題2有沒有更高效的算法?,分析:計(jì)算x的冪時(shí),可以利用前面的計(jì)算結(jié)果,以減少計(jì)算量,即先計(jì)算x2,然后依次計(jì)算,的值.,第二種做法與第一種做法相比,乘法的運(yùn)算次數(shù)減少了,因而能提高運(yùn)算效率.而且對于計(jì)算機(jī)來說,做一次乘法所需的運(yùn)算時(shí)間比做一次加法要長得多,因此第二種做法能更快地得到結(jié)果.,問題3能否探索更好的算法,來解決任意多項(xiàng)

8、式的求值問題?,f(x)=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時(shí),多項(xiàng)式的值是2677.,這種求多項(xiàng)式值的方法就叫秦九韶算法.,例:用秦九韶算法求多項(xiàng)式 f(x)=2x5-5x4-4x3+3x2-6

9、x+7當(dāng)x=5時(shí)的值.,解法一:首先將原多項(xiàng)式改寫成如下形式 : 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時(shí),多項(xiàng)式的值是2677.,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即,2 -5 -4 3 -6 7,x=5,10,5,25,21,105,108,540,534,2670,2677,所以,當(dāng)x=5時(shí),多項(xiàng)式的值是2677.,原多項(xiàng)式的系數(shù),多項(xiàng)式的值.,例:用秦九韶算法

10、求多項(xiàng)式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)的值.,解法二:列表,2,2 -5 0 -4 3 -6 0,x=5,10,5,25,25,125,121,605,608,3040,3034,所以,當(dāng)x=5時(shí),多項(xiàng)式的值是15170.,練一練:用秦九韶算法求多項(xiàng)式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)x=5時(shí)的值.,解:原多項(xiàng)式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0 列表,2,15170,15170,注意:n次多項(xiàng)式有n+1項(xiàng),因此缺少哪一項(xiàng)應(yīng)將其系數(shù)補(bǔ)0.,f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.

11、,我們可以改寫成如下形式:,f(x)=(anx+an-1)x+an-2)x+a1)x+a0.,求多項(xiàng)式的值時(shí),首先計(jì)算最內(nèi)層括號內(nèi)一次多項(xiàng)式的值,即,v1=anx+an-1,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即,一般地,對于一個(gè)n次多項(xiàng)式,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,這樣,求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值.這種算法稱為秦九韶算法.,點(diǎn)評:秦九韶算法是求一元多項(xiàng)式的值的一種方法. 它的特點(diǎn)是:把求一個(gè)n次多項(xiàng)式的值轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值,通過這種轉(zhuǎn)化,把運(yùn)算的次數(shù)由至多n(n+1)/2次乘法運(yùn)算和n次加法運(yùn)算,減少為n次乘法運(yùn)算和n次加法運(yùn)算,大大提高了運(yùn)算效率.,v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,觀察上述秦九韶算法中的n個(gè)一次式,可見vk的計(jì)算要用到vk-1的值.,若令v0=an,得,這是一個(gè)在秦九韶算法