1、算法案例之算法案例之秦九韶算法秦九韶算法問題問題1設(shè)計求多項式設(shè)計求多項式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時的值的算法時的值的算法,并寫出程序并寫出程序.x=5f=2x5-5x4-4x3+3x2-6x+7PRINT fEND程序程序點評點評:上述算法一共做了上述算法一共做了15次乘法運算次乘法運算,5次次加法運算加法運算.優(yōu)點是簡單優(yōu)點是簡單,易懂易懂;缺陷是不通用缺陷是不通用,不能不能處理恣意多項式求值問題處理恣意多項式求值問題,而且計算效率不高而且計算效率不高. 分析計算上述多項式的值分析計算上述多項式的值,一共需求一共需求9次乘次乘法運算法運算,5次加法運算次

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

3、更好的算法能否探求更好的算法,來處理恣意多來處理恣意多項式的求值問題項式的求值問題?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=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時時,多項式的值是多項式的值是2677.這種求多項式值的方法就叫秦九韶算法這種求多項

4、式值的方法就叫秦九韶算法.例例1:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時的值時的值.解法一解法一:首先將原多項式改寫成如下方式首先將原多項式改寫成如下方式 : 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時時,多多項式的值是項式的值是2677.然后由內(nèi)向外逐層計算一次多項式的值然后由內(nèi)向外逐層計算一次多項式的值,即即

5、2 -5 -4 3 -6 7x=5105252110510854053426702677所以所以,當(dāng)當(dāng)x=5時時,多項式的值是多項式的值是2677.原多項式原多項式的系數(shù)的系數(shù)多項式多項式的值的值.例例1:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng)x=5時的值時的值.解法二解法二:列表列表22 -5 0 -4 3 -6 0 x=5105252512512160560830403034所以所以,當(dāng)當(dāng)x=5時時,多項式的值是多項式的值是15170.練一練練一練:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-

6、6x當(dāng)當(dāng)x=5時的值時的值.解解:原多項式先化為原多項式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列表列表21517015170 留意留意:n次多項式有次多項式有n+1項項,因此短少哪一項因此短少哪一項應(yīng)將其系數(shù)補應(yīng)將其系數(shù)補0.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)一首先計算最內(nèi)層括號內(nèi)一次多項式的值次多項式的值,即即 v1=anx+an-1,然后由內(nèi)向外逐層計算一次多項式

7、的值然后由內(nèi)向外逐層計算一次多項式的值,即即普通地普通地,對于一個對于一個n次多項式次多項式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.這樣這樣,求求n次多項式次多項式f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求n個個一次多項式的值一次多項式的值.這種算法稱為秦九韶算法這種算法稱為秦九韶算法.點評點評:秦九韶算法是求一元多項式的秦九韶算法是求一元多項式的值的一種方法值的一種方法.它的特點是它的特點是:把求一個把求一個n次多項式的值次多項式的值轉(zhuǎn)化為求轉(zhuǎn)化為求n個一次多項式的值個一次多項式的值,經(jīng)過這種轉(zhuǎn)經(jīng)過這種轉(zhuǎn)化化,把運算的次數(shù)由至多把運算的次數(shù)由至多n(n+1)/

8、2次乘法次乘法運算和運算和n次加法運算次加法運算,減少為減少為n次乘法運算次乘法運算和和n次加法運算次加法運算,大大提高了運算效率大大提高了運算效率.v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.察看上述秦九韶算法中的察看上述秦九韶算法中的n個一次式個一次式,可見可見vk的計算要用到的計算要用到vk-1的值的值.假設(shè)令假設(shè)令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n這是一個在秦九韶算法中反復(fù)執(zhí)行的步這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟驟,因此可用循環(huán)構(gòu)造來實現(xiàn)因此可用循環(huán)構(gòu)造來實現(xiàn).問題問題畫出程序框圖畫出程序框圖,表示用秦九韶算法求表示用秦九韶算法求5次多次多項式項式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0當(dāng)當(dāng)x=x0 (x0是恣意實數(shù)是恣意實數(shù))時的值的過程時的值的過程,然后寫出程然后寫出程序序.否否程序框圖程序框圖開場開場輸入輸入a(0),a(1),a(2),a(3),a(4),a(5)輸入輸入xn5?n=1v=a(5)v=vx+a(5-n)n=n+1輸出