【高中數(shù)學(xué)必修三】秦九韶算法(課堂PPT)

1、1 1.3.2 案例案例2、秦九韶算法、秦九韶算法2復(fù)習(xí)復(fù)習(xí)1 1、求兩個(gè)數(shù)的最大公約數(shù)的兩種方法分別是（、求兩個(gè)數(shù)的最大公約數(shù)的兩種方法分別是（ ）和（和（ ）. .2 2、兩個(gè)數(shù)、兩個(gè)數(shù)2167221672，81278127的最大公約數(shù)是（的最大公約數(shù)是（ ）A A、2709 B2709 B、2606 C2606 C、2703 D2703 D、27062706輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 更相減損術(shù)更相減損術(shù)A3 案例案例2、秦九韶算法、秦九韶算法秦九韶算法是求一元多項(xiàng)式的值的一種方法。秦九韶算法是求一元多項(xiàng)式的值的一種方法。怎樣求多項(xiàng)式怎樣求多項(xiàng)式f(x)=xf(x)=x5 5+x+x4 4+x

2、+x3 3+x+x2 2+x+1+x+1當(dāng)當(dāng)x=5x=5時(shí)的值呢？時(shí)的值呢？算法一：把算法一：把5代入，計(jì)算各項(xiàng)的值，然后把它們加起來(lái)。代入，計(jì)算各項(xiàng)的值，然后把它們加起來(lái)。算法二：先計(jì)算算法二：先計(jì)算x2的值，然后依次計(jì)算的值，然后依次計(jì)算x2x、（ x2x）x、（、（ （ x2x）x）x的值。的值。4 計(jì)算多項(xiàng)式計(jì)算多項(xiàng)式（） =當(dāng)當(dāng)x = 5的值的值因?yàn)橐驗(yàn)椋ǎ?=所以所以（5）=55555=3125625125255= 3906算法一：把算法一：把5代入，計(jì)算各項(xiàng)的值，然后把它們加起來(lái)。代入，計(jì)算各項(xiàng)的值，然后把它們加起來(lái)。=5x5x5x5x55x5x5x55x5x55x55算法算法1

3、：5算法算法2：（5）=55555=5（5555） =5（5（555 ） ） =5（5（ 5 （55 ） ） ） =5（5（ 5 （5 （5 ） ） ） ） 算法二：先計(jì)算算法二：先計(jì)算x2的值，然后依次計(jì)算的值，然后依次計(jì)算 x2x、（、（ x2x）x、（、（ （ x2x）x）x 的值的值 計(jì)算多項(xiàng)式計(jì)算多項(xiàng)式（） =當(dāng)當(dāng)x = 5的值的值6計(jì)算多項(xiàng)式計(jì)算多項(xiàng)式（） =當(dāng)當(dāng)x = 5的值的值算法算法1：因?yàn)橐驗(yàn)椋ǎ?=所以所以（5）=55555=3125625125255= 3906算法算法2：（5）=55555=5（5555） =5（5（555 ） ） =5（5（ 5 （55 ） ） ）

4、=5（5（ 5 （5 （5 ） ） ） ） 10次的乘法運(yùn)算次的乘法運(yùn)算,5次的加法運(yùn)算次的加法運(yùn)算4次的乘法運(yùn)算次的乘法運(yùn)算,5次的加法運(yùn)算次的加法運(yùn)算顯然，采用第二種算法，計(jì)算機(jī)能夠更快地得到結(jié)果。顯然，采用第二種算法，計(jì)算機(jī)能夠更快地得到結(jié)果。那么，有沒(méi)有更有效的算法呢？那么，有沒(méi)有更有效的算法呢？7數(shù)書(shū)九章數(shù)書(shū)九章秦九韶算法秦九韶算法對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫(xiě)對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫(xiě)設(shè)設(shè))(xf是一個(gè)是一個(gè)n n 次的一元多項(xiàng)式次的一元多項(xiàng)式1110( )nnnnf xa xaxa xa 1110( )nnnnf xa xaxa xa 12110()nnnna xaxaxa

5、231210()nnnna xaxaxa xa 1210()nnna xaxaxa xa 省略了若干省略了若干個(gè)半括號(hào)個(gè)半括號(hào)省略了若干項(xiàng)省略了若干項(xiàng)8要求多項(xiàng)式的值，應(yīng)該先算最內(nèi)層的一次多項(xiàng)式的值，即要求多項(xiàng)式的值，應(yīng)該先算最內(nèi)層的一次多項(xiàng)式的值，即然后，由內(nèi)到外逐層計(jì)算一次多項(xiàng)式的值，即然后，由內(nèi)到外逐層計(jì)算一次多項(xiàng)式的值，即 這種將求一個(gè)這種將求一個(gè)n n次多項(xiàng)式次多項(xiàng)式f(x)f(x)的值轉(zhuǎn)化成的值轉(zhuǎn)化成求求n n個(gè)個(gè)一次多項(xiàng)式一次多項(xiàng)式的值的方法的值的方法, ,稱為稱為秦九韶算法秦九韶算法1210( )()nnnf xa xaxaxaxa11nnva xa 212nvv xa 323

6、nvv xa 10nnvvxa 01(1,2, )nkkn kvavvxakn 9解：解：按由里到外的順序按由里到外的順序,依此計(jì)算一次多項(xiàng)式當(dāng)依此計(jì)算一次多項(xiàng)式當(dāng)x = 5時(shí)的值：時(shí)的值：所以所以,x = 5時(shí)，多項(xiàng)式的值為時(shí)，多項(xiàng)式的值為17255.2例例2 已知一個(gè)五次多項(xiàng)式為已知一個(gè)五次多項(xiàng)式為用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x = 5的值的值.5432( )523.52.61.70.8f xxxxxx 05v 15 5227v 22753.5138.5v 3138.5 52.6689.9v 4689.9 51.73451.2v 53451.2 50.817255.

7、2v 練習(xí)：教材練習(xí)：教材P48、 201(1,2, )nkkn kvavvxakn 10課后必做作業(yè)：課后必做作業(yè)： 請(qǐng)同學(xué)們課后閱讀教材請(qǐng)同學(xué)們課后閱讀教材38頁(yè)，理解并能識(shí)別秦九韶頁(yè)，理解并能識(shí)別秦九韶算法的程序。算法的程序。1101(1,2, )nkkn kvavvxakn 11101210( )()nnnnnnnf xa xaxa xaa xaxaxaxa 11nnva xa 212nvv xa 323nvv xa 10nnvvxa 第一步：輸入多項(xiàng)式次數(shù)第一步：輸入多項(xiàng)式次數(shù)n n、最高次項(xiàng)的系數(shù)、最高次項(xiàng)的系數(shù)a an n和和x x的值的值算法步驟算法步驟第二步：將第二步：將v

8、v的值初始化為的值初始化為a an n, ,將將i i的值初始化為的值初始化為n-1n-1第三步：輸入第三步：輸入i i次項(xiàng)的系數(shù)次項(xiàng)的系數(shù)a ai i第四步：第四步：v=vx+av=vx+ai i,i=i-1.,i=i-1.第五步：判斷第五步：判斷i i是否大于或等于是否大于或等于0,0,若是若是, ,則返回第三步則返回第三步; ;否則否則, ,輸出多項(xiàng)式的值輸出多項(xiàng)式的值v.v.秦九韶算法的程序設(shè)計(jì)秦九韶算法的程序設(shè)計(jì)12第一步：輸入多項(xiàng)式次數(shù)第一步：輸入多項(xiàng)式次數(shù)n n、最、最高次項(xiàng)的系數(shù)高次項(xiàng)的系數(shù)a an n和和x x的值的值第二步：將第二步：將v v的值初始化為的值初始化為a an

9、 n, ,將將i i的值初始化為的值初始化為n-1n-1第三步：輸入第三步：輸入i i次項(xiàng)的系數(shù)次項(xiàng)的系數(shù)a ai i第四步：第四步：v=vx+av=vx+ai i,i=i-1.,i=i-1.第五步：判斷第五步：判斷i i是否大于或等于是否大于或等于0,0,若是若是, ,則返回第三步則返回第三步; ;否則否則, ,輸輸出多項(xiàng)式的值出多項(xiàng)式的值v.v.程序框圖程序框圖開(kāi)始開(kāi)始輸入輸入n,an,x的值的值v=ani=n-1i0？輸出輸出v輸入輸入aiv=vx+aii=i-1結(jié)束結(jié)束NY秦九韶算法的程序設(shè)計(jì)秦九韶算法的程序設(shè)計(jì)13開(kāi)始開(kāi)始輸入輸入n,an,x的值的值v=ani=n-1i0？輸出輸出v輸入輸入aiv=vx+aii=i-1結(jié)束結(jié)束NYINPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE