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

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

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

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

4、值呢？分析：將多項(xiàng)式變形為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這個(gè)算法過程就是秦九韶算法過？思考3：如何用秦九韶算法完成一般多項(xiàng)式的求值問題？數(shù)書九章數(shù)書九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn設(shè)設(shè))(xf是一個(gè)是一個(gè)n 次的多項(xiàng)式次的多項(xiàng)式對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫：對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫：0111)(axaxaxaxfnnnn012

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

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

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

8、設(shè)計(jì)？知識(shí)探究知識(shí)探究( (二二):):秦九韶算法的程序設(shè)計(jì)秦九韶算法的程序設(shè)計(jì) （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:該程序框圖對(duì)應(yīng)的程序如何表述？該程序框圖對(duì)應(yīng)的程序如何表述？輸入輸入ai

9、開始開始輸入輸入n,an,xi=0?輸出輸出v結(jié)束結(jié)束v=vx+aii=i-1yni=n-1v=an例例1： 已知一個(gè)五次多項(xiàng)式為已知一個(gè)五次多項(xiàng)式為用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x = 5的值。的值。解：解： 將多項(xiàng)式變形：將多項(xiàng)式變形：按由里到外的順序，依此計(jì)算一次多項(xiàng)式當(dāng)按由里到外的順序，依此計(jì)算一次多項(xiàng)式當(dāng)x = 5時(shí)的值：時(shí)的值：所以，當(dāng)所以，當(dāng)x = 5時(shí)，多項(xiàng)式的值等于時(shí)，多項(xiàng)式的值等于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+多項(xiàng)式的系數(shù)多項(xiàng)式的值20 110 567.5 2824.5 1413104練習(xí)練習(xí)1：已知已知多項(xiàng)式多項(xiàng)式f(xf(x)=x)=x5 5-3x-3x4 4+3x+3x3 3-5x-5x2 2- -5x+15x+1當(dāng)當(dāng)用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x=5時(shí)的時(shí)的值。值。,并統(tǒng)計(jì)需要

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