1、1.3 1.3 算法案例算法案例 第二課時(shí)第二課時(shí) 案例案例2 2秦九韶算法秦九韶算法問題提出問題提出教學(xué)設(shè)計(jì)教學(xué)設(shè)計(jì)問題問題1設(shè)計(jì)求多項(xiàng)式設(shè)計(jì)求多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時(shí)的值的算法時(shí)的值的算法,并寫出程序并寫出程序.x=5f=2x5-5x4-4x3+3x2-6x+7PRINT fEND程序程序點(diǎn)評點(diǎn)評:上述算法一共做了上述算法一共做了15次乘法運(yùn)算次乘法運(yùn)算,5次次加法運(yùn)算加法運(yùn)算.優(yōu)點(diǎn)是簡單優(yōu)點(diǎn)是簡單,易懂易懂;缺點(diǎn)是計(jì)算效率不高缺點(diǎn)是計(jì)算效率不高. 這樣計(jì)算上述多項(xiàng)式的值這樣計(jì)算上述多項(xiàng)式的值,一共需要一共需要9次乘次乘法運(yùn)算法運(yùn)算,5次加法運(yùn)算

2、次加法運(yùn)算.問題問題2有沒有更高效的算法有沒有更高效的算法?分析分析:計(jì)算計(jì)算x的冪時(shí)的冪時(shí),可以利用前面的計(jì)算結(jié)可以利用前面的計(jì)算結(jié)果果,以減少計(jì)算量以減少計(jì)算量,即先計(jì)算即先計(jì)算x2,然后依次計(jì)算然后依次計(jì)算222,(),()xx xxxxxxx的值的值.第二種做法與第一種做法相比第二種做法與第一種做法相比,乘法的運(yùn)乘法的運(yùn)算次數(shù)減少了算次數(shù)減少了,因而能提高運(yùn)算效率因而能提高運(yùn)算效率.而且對于而且對于計(jì)算機(jī)來說計(jì)算機(jī)來說,做一次乘法所需的運(yùn)算時(shí)間比做一做一次乘法所需的運(yùn)算時(shí)間比做一次加法要長得多次加法要長得多,因此第二種做法能更快地得到因此第二種做法能更快地得到結(jié)果結(jié)果.f(x)=2x5

3、-5x4-4x3+3x2-6x+7問題問題3能否探索更好的算法能否探索更好的算法,來解決任意多來解決任意多項(xiàng)式的求值問題項(xiàng)式的求值問題?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這種求多項(xiàng)式值的方法就叫這種求多項(xiàng)式值的方法就叫秦九韶算法秦九韶算法.共用了多少次算法？共用了多少次算法？例用秦九韶算法求多項(xiàng)式例用秦九韶算法求多項(xiàng)式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時(shí)的值時(shí)的值.解法一解法一

4、:首先將原多項(xiàng)式改寫成如下形式首先將原多項(xiàng)式改寫成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所以所以,當(dāng)當(dāng)x=5時(shí)時(shí),多多項(xiàng)式的值是項(xiàng)式的值是2677.然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即即2 -5 -4 3 -6 7x=5105252110510854053426702677所以所以,當(dāng)當(dāng)x=5時(shí)時(shí),多項(xiàng)式的值是多項(xiàng)式的值是2677.原多項(xiàng)式原多項(xiàng)

5、式的系數(shù)的系數(shù)多項(xiàng)式多項(xiàng)式的值的值.例用秦九韶算法求多項(xiàng)式例用秦九韶算法求多項(xiàng)式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時(shí)的值時(shí)的值.解法二解法二:列表列表22 -5 0 -4 3 -6 0 x=5105252512512160560830403034所以所以,當(dāng)當(dāng)x=5時(shí)時(shí),多項(xiàng)式的值是多項(xiàng)式的值是15170.變式變式:用秦九韶算法求多項(xiàng)式用秦九韶算法求多項(xiàng)式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)當(dāng)x=5時(shí)的值時(shí)的值.解解:原多項(xiàng)式先化為原多項(xiàng)式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列表列表21517015170 注意注意:

6、n次多項(xiàng)式有次多項(xiàng)式有n+1項(xiàng)項(xiàng),因此缺少哪一項(xiàng)因此缺少哪一項(xiàng)應(yīng)將其系數(shù)補(bǔ)應(yīng)將其系數(shù)補(bǔ)0.f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我們可以改寫成如下形式我們可以改寫成如下形式:f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求多項(xiàng)式的值時(shí)求多項(xiàng)式的值時(shí),首先計(jì)算最內(nèi)層括號內(nèi)一首先計(jì)算最內(nèi)層括號內(nèi)一次多項(xiàng)式的值次多項(xiàng)式的值,即即 v1=anx+an-1,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即即一般地一般地,對于一個(gè)對于一個(gè)n次多項(xiàng)式次多項(xiàng)式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.

7、這樣這樣,求求n次多項(xiàng)式次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求n個(gè)個(gè)一次多項(xiàng)式的值一次多項(xiàng)式的值.這種算法稱為這種算法稱為秦九韶算法秦九韶算法.點(diǎn)評點(diǎn)評:秦九韶算法是求一元多項(xiàng)式的秦九韶算法是求一元多項(xiàng)式的值的一種方法值的一種方法.它的特點(diǎn)是它的特點(diǎn)是:把求一個(gè)把求一個(gè)n次多項(xiàng)式的值次多項(xiàng)式的值轉(zhuǎn)化為求轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值個(gè)一次多項(xiàng)式的值,通過這種轉(zhuǎn)通過這種轉(zhuǎn)化化,把運(yùn)算的次數(shù)把運(yùn)算的次數(shù)由至多由至多n(n+1)/2次乘法次乘法運(yùn)算和運(yùn)算和n次加法運(yùn)算次加法運(yùn)算,減少為減少為n次乘法運(yùn)算次乘法運(yùn)算和和n次加法運(yùn)算次加法運(yùn)算,大大提高了運(yùn)算效率大大提高了運(yùn)算效率.（P38）v1=an

8、x+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.觀察上述秦九韶算法中的觀察上述秦九韶算法中的n個(gè)一次式個(gè)一次式,可見可見vk的計(jì)算要用到的計(jì)算要用到vk-1的值的值. 若令若令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n)這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟驟,因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn).探究探究: :秦九韶算法的程序設(shè)計(jì)秦九韶算法的程序設(shè)計(jì) 問題問題1:1:用秦九韶算法求多項(xiàng)式的值，可以用用秦九韶算法求多項(xiàng)式的值，可以用循環(huán)結(jié)構(gòu)來構(gòu)造算法，其算法步驟如何設(shè)計(jì)？循環(huán)結(jié)構(gòu)來構(gòu)造

9、算法，其算法步驟如何設(shè)計(jì)？第一步，輸入多項(xiàng)式的次數(shù)第一步，輸入多項(xiàng)式的次數(shù)n n，最高次，最高次 項(xiàng)的系數(shù)項(xiàng)的系數(shù)a an n和和x x的值的值. . 第二步，令第二步，令v=av=an n，i=n-1.i=n-1. 第三步，輸入第三步，輸入i i次項(xiàng)的系數(shù)次項(xiàng)的系數(shù)a ai i. . 第四步，第四步，v=vx+av=vx+ai i，i=i-1.i=i-1.第五步，判斷第五步，判斷i0i0是否成立是否成立. .若是，則返回第若是，則返回第 二步；否則，輸出多項(xiàng)式的值二步；否則，輸出多項(xiàng)式的值v.v. 問題問題2:2:該算法的程序框圖如何表示？該算法的程序框圖如何表示？開始開始輸入輸入n，an，x的值的值v=anv=vx+ai輸入輸入aii0？i=n- -1i=i- -1結(jié)束結(jié)束是是輸出輸出v否否問題問題3:3:該程序框圖對應(yīng)的程序如何表述？該程序框圖對應(yīng)的程序如何表述？開始開始輸入輸入n，an，x的值的值v=anv=vx+ai輸入輸入aii0？i=n- -1i=i- -1結(jié)束結(jié)束是是輸出輸出v否否INPUT “n=”INPUT “n=”；n nINPUT “an=”INPUT “an=”；a aINPUT “x=”INPUT “x=”；x x v=a