福建省永安市高中數(shù)學第一章算法初步1.3.2秦九韶算法課件新人教A版必修

1、算算 法法 案案 例例第二課時案例案例2 秦九韶算法秦九韶算法這節(jié)課我們主要研究的是秦九韶算法中的一種這節(jié)課我們主要研究的是秦九韶算法中的一種 情境引入情境引入 問題是數(shù)學的心臟。p.r.halmos（波利亞） 帶著問題我們一起去看看古代中國人的智慧吧！了解一下中國古代數(shù)學對現(xiàn)代世界數(shù)學發(fā)展的貢獻吧！新課探究:思考思考1：怎樣求多項式怎樣求多項式f(xf(x)=x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1當當x=5x=5時的值呢？時的值呢？x=5f=x5+x4+x3+x2+x+1print fend程序程序知識探究知識探究( (一一):):秦九韶算法的基本思想秦九韶

2、算法的基本思想 計算多項式計算多項式() =當當x = 5的值的算法：的值的算法：算法算法1：因為因為() =所以所以(5)=55555=3125625125255= 3906共做了共做了1+2+3+4=10次乘法運算，次乘法運算，5次加法運算。次加法運算。算法算法2:2:在上述問題中，若先計算在上述問題中，若先計算x x2 2的值，的值，然后依次計算然后依次計算x x2 2xx，(x(x2 2x)xx)x，(x(x2 2x)x)xx)x)x的值，這樣每次都可以的值，這樣每次都可以利用上一次計算的結(jié)果利用上一次計算的結(jié)果. .共做了共做了4次乘法運算，次乘法運算，5次加法運算。次加法運算。第二

3、種做法與第一種做法相比第二種做法與第一種做法相比,乘法的運算次數(shù)乘法的運算次數(shù)減少了減少了,因而能提高運算效率因而能提高運算效率.而且對于計算機來說而且對于計算機來說,做做一次乘法所需的運算時間比做一次加法要長得多一次乘法所需的運算時間比做一次加法要長得多,因因此第二種做法能更快地得到結(jié)果此第二種做法能更快地得到結(jié)果.算法算法3：( )(1)1)1)1)1f xxxxxx我們把多項式() =變形為： 從而得： 共做了共做了4次乘法運算，次乘法運算，5次加法運算。次加法運算。一種更高效的算法(5)(5 1) 5 1) 5 1) 5 1) 5 13096f 因為因為思考2：怎樣求多項式當x=5時的

4、值呢？分析：將多項式變形為5432( )254367f xxxxxx( )(25)4)3)6)7f xxxxxx令1052 555vv x 02v 2145 5421vv x 32321 53108vvx 436108 56534vvx 547534 572677vv x (5)2677f這個算法過程就是秦九韶算法過？思考3：如何用秦九韶算法完成一般多項式的求值問題？數(shù)書九章數(shù)書九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn設(shè)設(shè))(xf是一個是一個n 次的多項式次的多項式對該多項式按下面的方式進行改寫：對該多項式按下面的方式進行改寫：0111)(axaxaxaxfnnnn012

5、11)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn這是怎樣的一種改寫方式？最后的結(jié)果是什么？0121)()(axaxaxaxaxfnnn要求多項式的值，應該先算最內(nèi)層的一次多項式的值，即要求多項式的值，應該先算最內(nèi)層的一次多項式的值，即11nnaxav然后，由內(nèi)到外逐層計算一次多項式的值，即然后，由內(nèi)到外逐層計算一次多項式的值，即212naxvv323naxvv01axvvnn最后的一最后的一項是什么？項是什么？這種將求一個這種將求一個n次多項式次多項式f(x)的值轉(zhuǎn)化成求的值轉(zhuǎn)化成求n個一個一次多項式的值的方法，稱為次多項式的值的方法

6、，稱為秦九韶算法秦九韶算法。把求一個把求一個n次多項式的值轉(zhuǎn)化為求次多項式的值轉(zhuǎn)化為求n個一次多項個一次多項式的值式的值,通過這種轉(zhuǎn)化通過這種轉(zhuǎn)化,把運算的次數(shù)由至多把運算的次數(shù)由至多n(n+1)/2次乘法運算和次乘法運算和n次加法運算次加法運算,減少為減少為n次次乘法運算和乘法運算和n次加法運算次加法運算,大大提高了運算效率大大提高了運算效率.秦九韶算法的特點：秦九韶算法的特點：思考思考5 5 利用利用秦九韶算法秦九韶算法算法算法n n次多項式次多項式求求f(xf(x0 0) )的值，一共需要多少次乘法運算，的值，一共需要多少次乘法運算，多少次加法運算？多少次加法運算？ (1)、算法步驟：、

7、算法步驟：第一步：輸入多項式次數(shù)第一步：輸入多項式次數(shù)n、最高次項的系數(shù)、最高次項的系數(shù)an和和x的值的值.第二步：將第二步：將v的值初始化為的值初始化為an，將，將i的值初始化為的值初始化為n-1.第三步：輸入第三步：輸入i次項的系數(shù)次項的系數(shù)an.第四步：第四步：v=vx+ai, i=i-1.第五步：判斷第五步：判斷i是否大于或等于是否大于或等于0，若是，則返回第，若是，則返回第三步；否則，輸出多項式的值三步；否則，輸出多項式的值v。思考思考1:用秦九韶算法求多項式的值，可以用什么用秦九韶算法求多項式的值，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計？邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何

8、設(shè)計？知識探究知識探究( (二二):):秦九韶算法的程序設(shè)計秦九韶算法的程序設(shè)計 （2）程序框圖：）程序框圖：輸入輸入ai開始開始輸入輸入n,an,xi=0?輸出輸出v結(jié)束結(jié)束v=vx+aii=i-1yni=n-1v=an思考思考2:該算法的程序框圖如何表示？該算法的程序框圖如何表示？程序：程序：input “n=”；ninput “an=“;ainput “x=“;xv=ai=n-1while i=0 print “i=“;i input “ai=“;a v=v*x+a i=i-1wendprint vend思考思考3:該程序框圖對應的程序如何表述？該程序框圖對應的程序如何表述？輸入輸入ai

9、開始開始輸入輸入n,an,xi=0?輸出輸出v結(jié)束結(jié)束v=vx+aii=i-1yni=n-1v=an例例1： 已知一個五次多項式為已知一個五次多項式為用秦九韶算法求這個多項式當用秦九韶算法求這個多項式當x = 5的值。的值。解：解： 將多項式變形：將多項式變形：按由里到外的順序，依此計算一次多項式當按由里到外的順序，依此計算一次多項式當x = 5時的值：時的值：所以，當所以，當x = 5時，多項式的值等于時，多項式的值等于14130.25432( )423.52.61.70.8f xxxxxx( )(42)3.5)2.6)1.7)0.8f xxxxxx04v 14 5222v 222 53.5

10、113.5v 3113.5 52.6564.9v 4564.9 5 1.72826.2v 52826.2 50.814130.2v 理論遷移理論遷移另解：（秦九韶算法的另一種直觀算法） 4 2 3.5 -2.6 1.7 -0.8 x5 22 113.5 564.9 2826.2 14130.2+多項式的系數(shù)多項式的值20 110 567.5 2824.5 1413104練習練習1：已知已知多項式多項式f(xf(x)=x)=x5 5-3x-3x4 4+3x+3x3 3-5x-5x2 2- -5x+15x+1當當用秦九韶算法求這個多項式當用秦九韶算法求這個多項式當x=5時的時的值。值。,并統(tǒng)計需要

11、多少次乘法計算和多少次加并統(tǒng)計需要多少次乘法計算和多少次加法計算？法計算？例2：已知多項式已知多項式f(x)=3x4+2x2+4x+2用用秦九韶算法求這個多項式當秦九韶算法求這個多項式當x=-2時的值及時的值及v1,v3的值。的值。解：這個解法正確嗎？01231333 ( 2)244( 2)41212( 2)2224,22,( 2)22vvvvvvf 理論遷移理論遷移012341333 ( 2)066 ( 2)21414 ( 2)42424 ( 2)2506,24,( 2)50vvvvvvvf 解解:原多項式先化為原多項式先化為: f(x)=3x4+0 x3+2x2+4x+2(30)2)4)2xxxx 注意注意:n次多項式有次多項式有n+1項項,因此缺少哪一項因此缺少哪一項應將其系數(shù)補應將其系數(shù)補0.2 -5 0 -4 3 -6 0 x=24-1-2-2-4-8-16-13-26-32所以所以,當當x=2時時,多項式的值是多項式的值是-64.練習練習2:用秦九韶算法求多項式用秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當當x=2時的值時的值.解解:原多項式先化為原多項式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列表列表2-64-64 注意注意:n次多項式有次多項式有n+1項項,因