數(shù)學(xué)132算法案例秦九韶算法課件新人教A版必修PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 數(shù)學(xué)數(shù)學(xué)132算法案例秦九韶算法課件新人教算法案例秦九韶算法課件新人教 A版必修版必修 教學(xué)設(shè)計(jì)教學(xué)設(shè)計(jì) 問題問題1 求多項(xiàng)式求多項(xiàng)式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)當(dāng) x=5時(shí)的值。時(shí)的值。 點(diǎn)評(píng)點(diǎn)評(píng):上述算法一共做了上述算法一共做了15次乘法運(yùn)算次乘法運(yùn)算,5 次加法運(yùn)算次加法運(yùn)算.優(yōu)點(diǎn)是簡(jiǎn)單優(yōu)點(diǎn)是簡(jiǎn)單,易懂易懂;缺點(diǎn)是不通用缺點(diǎn)是不通用,不不 能解決任意多項(xiàng)多求值問題能解決任意多項(xiàng)多求值問題,而且計(jì)算效率不高而且計(jì)算效率不高. （2677 ） 第1頁/共15頁 這析計(jì)算上述多項(xiàng)式的值這析計(jì)算上述多項(xiàng)式的值, ,一共需要一共需要9 9次乘法運(yùn)算次乘法運(yùn)算,5,

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

3、要長(zhǎng)得多, ,因此第二種做法能更快地得到結(jié)果因此第二種做法能更快地得到結(jié)果. . 第2頁/共15頁 問題問題3能否探索更好的算法能否探索更好的算法,來解決任意多項(xiàng)式來解決任意多項(xiàng)式 的求值問題的求值問題? 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+7 v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v

4、5=v4x+7=5345+7=2677 所以所以,當(dāng)當(dāng)x=5時(shí)時(shí),多項(xiàng)式的值是多項(xiàng)式的值是2677. 5 5次乘法運(yùn)算次乘法運(yùn)算,5,5次加法運(yùn)算次加法運(yùn)算 第3頁/共15頁 問題問題4 4 利用后一種算法求多項(xiàng)式利用后一種算法求多項(xiàng)式 f(x)=af(x)=an nx xn n+a+an-1 n-1x xn-1 n-1+ + +a+a1 1x+ax+a0 0的值，這個(gè)多項(xiàng)式的值，這個(gè)多項(xiàng)式 應(yīng)寫成哪種形式？應(yīng)寫成哪種形式？ f(x)=af(x)=an nx xn n+a+an-1 n-1x xn-1 n-1+ + +a+a1 1x+ax+a0 0 =(a=(an nx xn-1 n-1+a

5、+an-1 n-1x xn-2 n-2+ + +a+a2 2x+ax+a1 1)x+a)x+a0 0 =(a=(an nx xn-2 n-2+a +an-1 n-1x xn-3 n-3+ + +a+a2 2)x+a)x+a1 1)x+a)x+a0 0 = = =(=(a(an nx+ax+an-1 n-1)x+a )x+an-2 n-2)x+ )x+a+a1 1)x+a)x+a0 0. . 第4頁/共15頁 問題問題55對(duì)于對(duì)于多項(xiàng)式多項(xiàng)式 f(x)=(f(x)=(a(an nx+ax+an-1 n-1)x+ a )x+ an-2 n-2)x+ )x+a+a1 1)x+a)x+a0 0 由內(nèi)向

6、外逐層計(jì)算一次多項(xiàng)式的值，其算法步驟由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，其算法步驟 如何？如何？ 第一步，計(jì)算第一步，計(jì)算v v1 1=a=an nx+ax+an-1 n-1. . 第二步，計(jì)算第二步，計(jì)算v v2 2=v=v1 1x+ax+an-2 n-2. . 第三步，計(jì)算第三步，計(jì)算v v3 3=v=v2 2x+ax+an-3 n-3. . 第第n n步，計(jì)算步，計(jì)算v vn n=v=vn-1 n-1x+a x+a0 0. . 思考：在多項(xiàng)式的求值上，這是怎樣的一種轉(zhuǎn)化？思考：在多項(xiàng)式的求值上，這是怎樣的一種轉(zhuǎn)化？ 第5頁/共15頁 問題問題66對(duì)于多項(xiàng)式對(duì)于多項(xiàng)式 f(x)=af(x)=a

7、n nx xn n+a+an-1 n-1x xn-1 n-1+ + +a+a1 1x+ax+a0 0 這種將求一個(gè)這種將求一個(gè)n n次多項(xiàng)式次多項(xiàng)式f f(x)(x)的值轉(zhuǎn)化成求的值轉(zhuǎn)化成求n n 個(gè)一次多項(xiàng)式的值的方法，稱為個(gè)一次多項(xiàng)式的值的方法，稱為秦九韶算法秦九韶算法 。利用該算法求利用該算法求f(xf(x0 0) )的值，一共需要多少次的值，一共需要多少次 乘法運(yùn)算，多少次加法運(yùn)算？乘法運(yùn)算，多少次加法運(yùn)算？ 問題問題77在秦九韶算法中，記在秦九韶算法中，記v v0 0=a=an n，那么第，那么第k k步的步的 算式是什么？算式是什么？ v vk k=v=vk-1 k-1x+a x+

8、an-k n-k (k=1 (k=1，2 2，n)n) n次乘法運(yùn)算次乘法運(yùn)算, , n次加法運(yùn)算次加法運(yùn)算 第6頁/共15頁 秦九韶算法是求一元多項(xiàng)式的值的一種方法秦九韶算法是求一元多項(xiàng)式的值的一種方法. . 它的特點(diǎn)是它的特點(diǎn)是: :把求一個(gè)把求一個(gè)n n次多項(xiàng)式的值轉(zhuǎn)化為次多項(xiàng)式的值轉(zhuǎn)化為 求求n n個(gè)一次多項(xiàng)式的值個(gè)一次多項(xiàng)式的值, ,通過一次式的反復(fù)計(jì)通過一次式的反復(fù)計(jì) 算，逐步得出高次多項(xiàng)式的值，對(duì)于一個(gè)算，逐步得出高次多項(xiàng)式的值，對(duì)于一個(gè)n n次次 多項(xiàng)式，只需做多項(xiàng)式，只需做n n次乘法和次乘法和n n次加法即可，大次加法即可，大 大提高了運(yùn)算效率大提高了運(yùn)算效率. . 秦九韶

9、算法的特點(diǎn)：秦九韶算法的特點(diǎn)： 第7頁/共15頁 理論遷移理論遷移 例例: :用秦九韶算法求多項(xiàng)式用秦九韶算法求多項(xiàng)式 f(x)=5xf(x)=5x5 5+2x+2x4 4+3.5x+3.5x3 3- - 2.6x2.6x2 2+1.7x-0.8+1.7x-0.8當(dāng)當(dāng)x=5x=5時(shí)的值時(shí)的值. . f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x- 0.8.0.8. v v1 1=5=55+2=275+2=27 ； v v2 2=27=275+3.5=138.55+3.5=138.5； v v3 3=138.5=138.

10、55-2.6=689.95-2.6=689.9； v v4 4=689.9=689.95+1.7=3451.25+1.7=3451.2； v v5 5=3451.2=3451.25-0.8=17255.2.5-0.8=17255.2. 所以所以f(5)= f(5)= =17255.2.=17255.2. 解解: :首先將原多項(xiàng)式改寫成如下形式首先將原多項(xiàng)式改寫成如下形式 : : v0 0=5 你從中看到了怎樣的規(guī)律？怎么用程序框圖來描述呢？ 然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即即 第8頁/共15頁 1.1.已知多項(xiàng)式已知多項(xiàng)式f(x)=xf(x)=x5 5+

11、5x+5x4 4+10 x+10 x3 3+10 x+10 x2 2+5x+1+5x+1 用用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x=-2x=-2時(shí)的值。時(shí)的值。 練習(xí)： 2.2.已知多項(xiàng)式已知多項(xiàng)式f(x)=2xf(x)=2x6 6-6x-6x4 4-5x-5x2 2+4x-6+4x-6 用用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x=5x=5時(shí)的值。時(shí)的值。 3.3.已知多項(xiàng)式已知多項(xiàng)式f(x)=2xf(x)=2x6 6-5x-5x5 5-4x-4x3 3+3x+3x2 2-6x-6x 當(dāng)當(dāng) x=5x=5用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x=5x=5時(shí)

12、的值時(shí)的值 注意注意:n次多項(xiàng)式有次多項(xiàng)式有n+1項(xiàng)項(xiàng),因此缺少哪一項(xiàng)因此缺少哪一項(xiàng) 應(yīng)將其系數(shù)補(bǔ)應(yīng)將其系數(shù)補(bǔ)0. 你從中看到了怎樣的規(guī)律？怎么用程序框圖來描述呢？ 第9頁/共15頁 評(píng)價(jià)一個(gè)算法好壞的一個(gè)重要標(biāo)志是運(yùn)算的評(píng)價(jià)一個(gè)算法好壞的一個(gè)重要標(biāo)志是運(yùn)算的 次數(shù)，如果一個(gè)算法從理論上需要超出計(jì)算機(jī)允次數(shù)，如果一個(gè)算法從理論上需要超出計(jì)算機(jī)允 許范圍內(nèi)的運(yùn)算次數(shù)，那么這樣的算法就只能是許范圍內(nèi)的運(yùn)算次數(shù)，那么這樣的算法就只能是 一個(gè)理論算法一個(gè)理論算法. .在多項(xiàng)式求值的各種算法中，秦在多項(xiàng)式求值的各種算法中，秦 九韶算法是一個(gè)優(yōu)秀算法九韶算法是一個(gè)優(yōu)秀算法. . 課堂小結(jié)：課堂小結(jié)： 秦九

13、韶算法的方法和步驟秦九韶算法的方法和步驟 第10頁/共15頁 (1)(1)、算法步驟：、算法步驟： 第一步：輸入多項(xiàng)式次數(shù)第一步：輸入多項(xiàng)式次數(shù)n n、最高次項(xiàng)的系數(shù)、最高次項(xiàng)的系數(shù)a an n和和x x的值的值. . 第二步：將第二步：將v v的值初始化為的值初始化為a an n，將，將i i的值初始化為的值初始化為n-1.n-1. 第三步：輸入第三步：輸入i i次項(xiàng)的系數(shù)次項(xiàng)的系數(shù)a an n. . 第四步：第四步：v=vx+av=vx+ai i, i=i-1., i=i-1. 第五步：判斷第五步：判斷i i是否大于或等于是否大于或等于0 0，若是，則返回第三步；否則，輸出多項(xiàng)式的值，若是，則返回第三步；否則，輸出多項(xiàng)式的值v v。 課后思考：用秦九韶算法求多項(xiàng)式的值，可以用 什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì) ？程序框圖？程序呢？ 第11頁/共15頁 （2）程序框圖）程序框圖 ： 輸入輸入ai 開始開始 輸入輸入n,an,x i=0? 輸出輸出v 結(jié)束結(jié)束 v=v