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

1.3.2案例2、秦九韶算法2021/5/91復(fù)習(xí)1、求兩個(gè)數(shù)的最大公約數(shù)的兩種方法分別是（）和（）.2、兩個(gè)數(shù)21672，8127的最大公約數(shù)是（）A、2709B、2606C、2703D、2706輾轉(zhuǎn)相除法更相減損術(shù)A2021/5/92

案例2、秦九韶算法秦九韶算法是求一元多項(xiàng)式的值的一種方法。問(wèn)題怎樣求多項(xiàng)式f(x)=x5+x4+x3+x2+x+1當(dāng)x=5時(shí)的值呢？算法一：把5代入，計(jì)算各項(xiàng)的值，然后把它們加起來(lái)。算法二：先計(jì)算x2的值，然后依次計(jì)算x2·x、（x2·x）·x、（（x2·x）·x）·x的值。2021/5/93

計(jì)算多項(xiàng)式ｆ（ｘ）=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１當(dāng)x=5的值因?yàn)椋妫ǎ?ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ（5）=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906分析：算法1中用了幾次乘法運(yùn)算？和幾次加法運(yùn)算？算法一：把5代入，計(jì)算各項(xiàng)的值，然后把它們加起來(lái)。=5x5x5x5x5＋5x5x5x5＋5x5x5＋5x5＋5＋１算法1：2021/5/94算法2：ｆ（5）=5５＋5４＋5３＋5２＋5＋１=5×（5４＋5３＋5２＋5＋１）＋１=5×（5×（5３＋5２＋5＋１）＋１）＋１=5×（5×（5×（5２＋5＋１）＋１）＋１）＋１=5×（5×（5×（5×（5＋１）＋１）＋１）＋１）＋１算法二：先計(jì)算x2的值，然后依次計(jì)算

x2·x、（x2·x）·x、（（x2·x）·x）·x的值分析：算法2中用了幾次乘法運(yùn)算？和幾次加法運(yùn)算？

計(jì)算多項(xiàng)式ｆ（ｘ）=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１當(dāng)x=5的值2021/5/95計(jì)算多項(xiàng)式ｆ（ｘ）=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１當(dāng)x=5的值算法1：因?yàn)椋妫ǎ?ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ（5）=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906算法2：ｆ（5）=5５＋5４＋5３＋5２＋5＋１=5×（5４＋5３＋5２＋5＋１）＋１=5×（5×（5３＋5２＋5＋１）＋１）＋１=5×（5×（5×（5２＋5＋１）＋１）＋１）＋１=5×（5×（5×（5×（5＋１）＋１）＋１）＋１）＋１10次的乘法運(yùn)算,5次的加法運(yùn)算4次的乘法運(yùn)算,5次的加法運(yùn)算顯然，采用第二種算法，計(jì)算機(jī)能夠更快地得到結(jié)果。那么，有沒(méi)有更有效的算法呢？2021/5/96《數(shù)書(shū)九章》——秦九韶算法對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫設(shè)是一個(gè)n次的一元多項(xiàng)式省略了若干個(gè)半括號(hào)省略了若干項(xiàng)2021/5/97要求多項(xiàng)式的值，應(yīng)該先算最內(nèi)層的一次多項(xiàng)式的值，即然后，由內(nèi)到外逐層計(jì)算一次多項(xiàng)式的值，即

這種將求一個(gè)n次多項(xiàng)式f(x)的值轉(zhuǎn)化成求n個(gè)一次多項(xiàng)式的值的方法,稱為秦九韶算法分析：秦九韶算法中用了幾次乘法運(yùn)算？和幾次加法運(yùn)算？2021/5/98解：按由里到外的順序,依此計(jì)算一次多項(xiàng)式當(dāng)x=5時(shí)的值：所以,x=5時(shí)，多項(xiàng)式的值為17255.2例2已知一個(gè)五次多項(xiàng)式為用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x=5的值.練習(xí)：教材P48、22021/5/99課后必做作業(yè)：

請(qǐng)同學(xué)們課后閱讀教材38頁(yè)，理解并能識(shí)別秦九韶算法的程序。2021/5/910第一步：輸入多項(xiàng)式次數(shù)n、最高次項(xiàng)的系數(shù)an和x的值算法步驟第二步：將v的值初始化為an,將i的值初始化為n-1第三步：輸入i次項(xiàng)的系數(shù)ai第四步：v=vx+ai,i=i-1.第五步：判斷i是否大于或等于0,若是,則返回第三步;否則,輸出多項(xiàng)式的值v.秦九韶算法的程序設(shè)計(jì)2021/5/911第一步：輸入多項(xiàng)式次數(shù)n、最高次項(xiàng)的系數(shù)an和x的值第二步：將v的值初始化為an,將i的值初始化為n-1第三步：輸入i次項(xiàng)的系數(shù)ai第四步：v=vx+ai,i=i-1.第五步：判斷i是否大于或等于0,若是,則返回第三步;否則,輸出多項(xiàng)式的值v.程序框圖開(kāi)始輸入n,an,x的值v=ani=n-1i≥0？輸出v輸入aiv=vx+aii=i-1結(jié)束NY秦九韶算法的程序設(shè)計(jì)2021/5/912開(kāi)始輸入n,an,x的值v=ani=n-1i≥0？輸出v輸入aiv=vx+aii=i-1結(jié)束NYINPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILEi>=0PRINT“i=”；