算法案例秦九邵算法人教A版必修市公開(kāi)課一等獎(jiǎng)省賽課微課金獎(jiǎng)?wù)n件

1.3算法案例

第二課時(shí)1/18例2求325，130，270三個(gè)數(shù)最大條約數(shù).因?yàn)?25=130×2+65，130=65×2，所以325與130最大條約數(shù)是65.

因?yàn)?70=65×4+10，65=10×6+5，10=5×2，所以65與270最大條約數(shù)是5.故325，130，270三個(gè)數(shù)最大條約數(shù)是5.2/18問(wèn)題提出1.輾轉(zhuǎn)相除法和更相減損術(shù)，是求兩個(gè)正整數(shù)最大條約數(shù)優(yōu)異算法，我們將算法轉(zhuǎn)化為程序后，就能夠由計(jì)算機(jī)來(lái)執(zhí)行運(yùn)算，實(shí)現(xiàn)了古代數(shù)學(xué)與當(dāng)代信息技術(shù)完美結(jié)合.2.對(duì)于求n次多項(xiàng)式值，在我國(guó)古代數(shù)學(xué)中有一個(gè)優(yōu)異算法，即秦九韶算法，我們將對(duì)這個(gè)算法作些了解和探究.3/18秦九韶算法4/18[問(wèn)題1]設(shè)計(jì)求多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)值算法,并寫(xiě)出程序.x=5f=2＊x^5-5＊x^4-4＊x^3+3＊x^2-6＊x+7PRINTfEND程序

點(diǎn)評(píng):上述算法一共做了15次乘法運(yùn)算,5次加法運(yùn)算.優(yōu)點(diǎn)是簡(jiǎn)單,易懂;缺點(diǎn)是不通用,不能處理任意多項(xiàng)多求值問(wèn)題,而且計(jì)算效率不高.知識(shí)探究(一):秦九韶算法基本思想

5/18思索2:在上述問(wèn)題中，若先計(jì)算x2值，然后依次計(jì)算x2·x，(x2·x)·x，((x2·x)·x)·x值，這么每次都能夠利用上一次計(jì)算結(jié)果，，那么一共做了多少次乘法運(yùn)算和多少次加法運(yùn)算？9次乘法運(yùn)算，5次加法運(yùn)算.

第二種做法與第一個(gè)做法相比,乘法運(yùn)算次數(shù)降低了,因而能提升運(yùn)算效率.而且對(duì)于計(jì)算機(jī)來(lái)說(shuō),做一次乘法所需運(yùn)算時(shí)間比做一次加法要長(zhǎng)得多,所以第二種做法能更加快地得到結(jié)果.6/18

思索3:能否探索更加好算法,來(lái)處理任意多項(xiàng)式求值問(wèn)題?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+7v0=2v1=v0x-5=2×5-5=5v2=v1x-4=5×5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677所以,當(dāng)x=5時(shí),多項(xiàng)式值是2677.這種求多項(xiàng)式值方法就叫秦九韶算法.5次乘法運(yùn)算，5次加法運(yùn)算.7/18思索4:利用最終一個(gè)算法求多項(xiàng)式f(x)=anxn+an-1xn-1+…+a1x+a0值，這個(gè)多項(xiàng)式應(yīng)寫(xiě)成哪種形式？f(x)=anxn+an-1xn-1+…+a1x+a0=(anxn-1+an-1xn-2+…+a2x+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=…=(…((anx+an-1)x+an-2)x+…+a1)x+a0.8/18思索4:對(duì)于f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0，由內(nèi)向外逐層計(jì)算一次多項(xiàng)式值，其算法步驟怎樣？第一步，計(jì)算v1=anx+an-1.第二步，計(jì)算v2=v1x+an-2.第三步，計(jì)算v3=v2x+an-3.…第n步，計(jì)算vn=vn-1x+a0.9/18思索5:上述求多項(xiàng)式f(x)=anxn+an-1xn-1+…+a1x+a0值方法稱為秦九韶算法，利用該算法求f(x0)值，一共需要多少次乘法運(yùn)算，多少次加法運(yùn)算？思索6:在秦九韶算法中，記v0=an，那么第k步算式是什么？

vk=vk-1x+an-k(k=1，2，…，n)n次乘法運(yùn)算，n次加法運(yùn)算10/18知識(shí)探究(二):秦九韶算法程序設(shè)計(jì)

思索1:用秦九韶算法求多項(xiàng)式值，能夠用什么邏輯結(jié)構(gòu)來(lái)結(jié)構(gòu)算法？其算法步驟怎樣設(shè)計(jì)？第一步，輸入多項(xiàng)式次數(shù)n，最高次 項(xiàng)系數(shù)an和x值.

第二步，令v=an，i=n-1.

第三步，輸入i次項(xiàng)系數(shù)ai.第四步，v=vx+ai，i=i-1.第五步，判斷i≥0是否成立.若是，則返回第 二步；不然，輸出多項(xiàng)式值v.11/18思索2:該算法程序框圖怎樣表示？開(kāi)始輸入n，an，x值v=anv=vx+ai輸入aii≥0？i=n-1i=i-1結(jié)束是輸出v否12/18思索3:該程序框圖對(duì)應(yīng)程序怎樣表述？開(kāi)始輸入n，an，x值v=anv=vx+ai輸入aii≥0？i=n-1i=i-1結(jié)束是輸出v否INPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ani=n-1WHILEi>=0INPUT“ai=”；bv=v*x+bi=i-1

WENDPRINTyEND13/18理論遷移例1已知一個(gè)5次多項(xiàng)式為 用秦九韶算法求f(5)值.f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=5×5+2=27；v2=27×5+3.5=138.5；v3=138.5×5-2.6=689.9；v4=689.9×5+1.7=3451.2；v5=3451.2×5-0.8=17255.2.所以f(5)==17255.2.14/18變式：例2已知一個(gè)5次多項(xiàng)式為 用秦九韶算法求當(dāng)x=5時(shí)，V1,V3值及求f(5)值做多少次乘法運(yùn)算.解：f(x)=((((5x+0)x+3.5)x+0)x+1.7)x-0.8.v1=5×5+0=25；v2=25×5+3.5=128.5；v3=128.5×5+0=642.5；v4=642.5×5+1.7=3214.2；v5=3214.2×5-0.8=16070.8.所以v1=25，v3=642.5，f(5)=16070.8.15/18例3閱讀以下程序，說(shuō)明它處理實(shí)際問(wèn)題是什么？INPUT“x=”；an=0y=0WHLEn<5

y=y+(n+1)*a∧nn=n+1WENDPRINTyEND求多項(xiàng)式