1.3算法案例—(2)秦九韶算法

1、案例案例2 秦九韶算法秦九韶算法12021/3/10復習復習1、求兩個數(shù)的最大公約數(shù)的兩種方法分別是、求兩個數(shù)的最大公約數(shù)的兩種方法分別是_和和_2.兩個數(shù)兩個數(shù)21672，8127的最大公約數(shù)是的最大公約數(shù)是 （ ）A. 2709 B. 2606 C. 2703 D. 27063.用更相減損術求用更相減損術求140和和80的最大公約數(shù)是（）的最大公約數(shù)是（）A. 4 B. 5 C. 10 D. 20更相減損術更相減損術輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法AD21672=81272+54188127=54181+27095418=27092+022021/3/10輾轉(zhuǎn)相除法與更相減損術的比較輾轉(zhuǎn)相除法與更相減

2、損術的比較: : （1 1）都是求最大公約數(shù)的方法都是求最大公約數(shù)的方法，計算上，計算上輾轉(zhuǎn)輾轉(zhuǎn)相除法以除法為主相除法以除法為主，更相減損術以減法為主更相減損術以減法為主; ;計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。區(qū)別較明顯。（2 2）從結果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)）從結果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結果是結果是以相除余數(shù)為以相除余數(shù)為0 0則得到，而更相減損術則得到，而更相減損術則則以減數(shù)與差相等以減數(shù)與差相等而得到而得到. .32021/3/10問題問題1：怎樣

3、求多項式怎樣求多項式f(x)=x5+x4+x3+x2+x+1當當x=5時的值？并寫出程序時的值？并寫出程序.算法算法1 1：= 3906因為因為f(x)=x5+x4+x3+x2+x+1所以所以(5)=555551=31256251252551一共做了多少次乘法運算和多少次加法運算？一共做了多少次乘法運算和多少次加法運算？上述算法一共做了上述算法一共做了1+2+3+4=101+2+3+4=10次乘法運算，次乘法運算，5 5次加法運算次加法運算.優(yōu)點是簡單易懂，但計算效優(yōu)點是簡單易懂，但計算效率不高率不高.42021/3/10算法算法2 2：(5)=555551=5(55551 ) 1=5(5(5

4、55 1 )1 ) 1=5(5(5(5+5 +1) +1 ) +1 ) +1=5(5(5(5 (5 +1) +1 )+1)+1) +1計算多項式計算多項式f(x)=x5+x4+x3+x2+x+1當當x x = 5= 5的值的值共做了共做了4次乘法運算，次乘法運算，5次加法運算。次加法運算。52021/3/10問題問題2：能否探索一個算法能否探索一個算法,來解決任意多項式的來解決任意多項式的求值問題求值問題?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、-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.這種求多項式值的方法就叫這種求多項式值的方法就叫秦九韶算法秦九韶算法. .當當x=5時時,多項式多項式的值是多少？的值是多少？62021/3/10數(shù)書九章數(shù)書九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn設設)(xf是一個是一個n 次的多項式次的多項式對該多項式按下面的方式進行改寫：對該多項式按下面的

6、方式進行改寫：0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn72021/3/100121)()(axaxaxaxaxfnnn要求多項式的值，應該要求多項式的值，應該先算最內(nèi)層先算最內(nèi)層的一次多項式的的一次多項式的值，即值，即11nnaxav然后，然后，由內(nèi)到外逐層計算由內(nèi)到外逐層計算一次多項式的值，即一次多項式的值，即212naxvv323naxvv01axvvnn最后的一最后的一項是什么？項是什么？這種將求一個這種將求一個n n次多項式次多項式f f(x)(x)的值轉(zhuǎn)化成求的值轉(zhuǎn)化成求n

7、 n個個一次多項式的值的方法，稱為一次多項式的值的方法，稱為秦九韶算法秦九韶算法。0nva82021/3/10f(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)向外逐層計算由內(nèi)向外逐層計算一次多項式的值一次多項式的值,即即一般地一般地,對于一個對于一個n次多項式次多項式v2=v1x+an-2, v3=v2x+an-3, ,vn

8、=vn-1x+a0.這樣這樣,求求n次多項式次多項式f(x)的值就轉(zhuǎn)化為求的值就轉(zhuǎn)化為求n個個一次多項式的值一次多項式的值.這種算法稱為這種算法稱為秦九韶算法秦九韶算法.92021/3/10特點：特點：通過一次式的反復計算，逐步得出通過一次式的反復計算，逐步得出高次多項式高次多項式的值的值. 0111)(axaxaxaxfnnnn注注: :對于一個對于一個n n次多項式次多項式: :秦九韶算法把運算的次數(shù)由秦九韶算法把運算的次數(shù)由最多最多1+1+2+3+2+3+n n=n(n+1)/2n(n+1)/2次乘法和次乘法和n n次加法次加法的運算的運算, ,減少為減少為最多只需做最多只需做n n次乘

9、法和次乘法和n n次加法次加法運算運算, ,大大提高大大提高了運算效率了運算效率. .102021/3/10例例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=534 V5=v4x+7=5345+7=2677所以所以,當當x=5時時,多多項式的值是項式的值是

10、2677.然后然后由內(nèi)向外逐層計算一次多項式的值由內(nèi)向外逐層計算一次多項式的值,即即112021/3/102 -5 -4 3 -6 7x=5105252110510854053426702677所以所以,當當x=5時時,多項式的值是多項式的值是2677.原多項式原多項式的系數(shù)的系數(shù)多項式多項式的值的值.例例1:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當當x=5時的值時的值.解法二解法二:列表列表2v0 v1 v2 v3 v4 v5 122021/3/102 -5 0 -4 3 -6 0 x=51052525125121605608304030

11、34所以所以,當當x=5時時,多項式的值是多項式的值是15170.練一練練一練:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x6-5x5 -4x3+3x2-6x當當x=5x=5時的值時的值. .解解:原多項式先化為原多項式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0,列表如下列表如下21517015170 注意注意:n:n次多項式有次多項式有n+1n+1項項, ,因此缺少哪因此缺少哪一項應將其系數(shù)補一項應將其系數(shù)補0.0.132021/3/10v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.觀察上述秦九韶

12、算法中的觀察上述秦九韶算法中的n個一次式個一次式,可見可見vk的計算要用到的計算要用到vk-1的值的值. 若令若令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n這是一個在秦九韶算法中反復執(zhí)行的步這是一個在秦九韶算法中反復執(zhí)行的步驟驟,因此可用循環(huán)結構來實現(xiàn)因此可用循環(huán)結構來實現(xiàn).因此可用循環(huán)結因此可用循環(huán)結構來實現(xiàn)。構來實現(xiàn)。142021/3/10算法步驟：算法步驟：第一步：輸入多項式次數(shù)第一步：輸入多項式次數(shù)n、最高次項、最高次項的系數(shù)的系數(shù)an和和x的值的值.第二步：將第二步：將v的值初始化為的值初始化為an，將，將i的值的值初始化為初始化為1.第三步：輸入第三步：

13、輸入n-i次項的系數(shù)次項的系數(shù)an-i.第四步：第四步：v=vx+an-i , i=i+1.第五步：判斷第五步：判斷i是否是否小小于或等于于或等于n，若是，若是，則返回第三步；否則，輸出多項式的則返回第三步；否則，輸出多項式的值值v。152021/3/10否否開始開始輸入輸入a0,a1,a2,a3,a4,a5輸入輸入x0n5?n=1v=a5v=vx0+a5-nn=n+1輸出輸出v結束結束是是INPUT a0,a1,a2,a3,a4,a5INPUT x0n=1v=a5WHILE n=5 v=vx0+a5-n n=n+1WENDPRINT vEND程序程序程序框圖程序框圖162021/3/10練習、已知多項式練習、已知多