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

2、第二種做法能更快地得到結(jié)果.,問(wèn)題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+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)式值的方法就叫秦九韶算法.

3、,例1:用秦九韶算法求多項(xiàng)式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時(shí)的值.,解法一:首先將原多項(xiàng)式改寫(xiě)成如下形式 : 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

4、時(shí),多項(xiàng)式的值是2677.,原多項(xiàng)式的系數(shù),多項(xiàng)式的值.,例1:用秦九韶算法求多項(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ǔ)

5、0.,f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.,我們可以改寫(xiě)成如下形式:,f(x)=(anx+an-1)x+an-2)x+a1)x+a0.,求多項(xiàng)式的值時(shí),首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值,即,v1=anx+an-1,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即,一般地,對(duì)于一個(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)式的值.這種算法稱(chēng)為秦九韶算法.,點(diǎn)評(píng):秦九韶算法是求一元多項(xiàng)式的值的一種方法. 它的特點(diǎn)是:把求一個(gè)n次多項(xiàng)式的值轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值,通過(guò)這種轉(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è)一次式,可見(jiàn)vk的計(jì)算要用到vk-1的值.,若令v0=an,得,這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟,因此可用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn).,問(wèn)題：畫(huà)出程序框圖,表示用秦九韶算法求5次多項(xiàng)式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0當(dāng)x=x0 (x0是任意