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

2、加法運算.問題問題2有沒有更高效的算法有沒有更高效的算法?分析分析:計算計算x的冪時的冪時,可以利用前面的計算結可以利用前面的計算結果果,以減少計算量以減少計算量,即先計算即先計算x2,然后依次計算然后依次計算222,(),()xx xxxxxxx的值的值.第二種做法與第一種做法相比第二種做法與第一種做法相比,乘法的運乘法的運算次數減少了算次數減少了,因此能提高運算效率因此能提高運算效率.而且對于而且對于計算機來說計算機來說,做一次乘法所需的運算時間比做一做一次乘法所需的運算時間比做一次加法要長得多次加法要長得多,因此第二種做法能更快地得到因此第二種做法能更快地得到結果結果.問題問題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所以所以,當當x=5時時,多項式的值是多項式的值是2677.這種求多項式值的方法就叫秦九韶算法這種求多項

4、式值的方法就叫秦九韶算法.例例1:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當當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所以所以,當當x=5時時,多多項式的值是項式的值是2677.然后由內向外逐層計算一次多項式的值然后由內向外逐層計算一次多項式的值,即即

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

6、6x當當x=5時的值時的值.解解:原多項式先化為原多項式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列表列表21517015170 留意留意:n次多項式有次多項式有n+1項項,因此短少哪一項因此短少哪一項應將其系數補應將其系數補0.f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我們可以改寫成如下方式我們可以改寫成如下方式:f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求多項式的值時求多項式的值時,首先計算最內層括號內一首先計算最內層括號內一次多項式的值次多項式的值,即即 v1=anx+an-1,然后由內向外逐層計算一次多項式

7、的值然后由內向外逐層計算一次多項式的值,即即普通地普通地,對于一個對于一個n次多項式次多項式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.這樣這樣,求求n次多項式次多項式f(x)的值就轉化為求的值就轉化為求n個個一次多項式的值一次多項式的值.這種算法稱為秦九韶算法這種算法稱為秦九韶算法.點評點評:秦九韶算法是求一元多項式的秦九韶算法是求一元多項式的值的一種方法值的一種方法.它的特點是它的特點是:把求一個把求一個n次多項式的值次多項式的值轉化為求轉化為求n個一次多項式的值個一次多項式的值,經過這種轉經過這種轉化化,把運算的次數由至多把運算的次數由至多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的值的值.假設令假設令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n這是一個在秦九韶算法中反復執行的步這是一個在秦九韶算法中反復執行的步驟驟,因此可用循環構造來實現因此可用循環構造來實現.問題問題畫出程序框圖畫出程序框圖,表示用秦九韶算法求表示用秦九韶算法求5次多次多項式項式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0當當x=x0 (x0是恣意實數是恣意實數)時的值的過程時的值的過程,然后寫出程然后寫出程序序.否否程序框圖程序框圖開場開場輸入輸入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輸出