132算法案例(第二課時(shí))(1)

1、算算 法法 案案 例例(第二課時(shí))1、求兩個(gè)數(shù)的最大公約數(shù)的兩種方法分別是、求兩個(gè)數(shù)的最大公約數(shù)的兩種方法分別是（ ）和（）和（ ）。）。2、兩個(gè)數(shù)、兩個(gè)數(shù)21672，8127的最大公約數(shù)是的最大公約數(shù)是 （ ）A、2709 B、2606 C、2703 D、2706案例2、秦九韶算法怎樣求多項(xiàng)式怎樣求多項(xiàng)式f(x)=xf(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í)的值呢？計(jì)算多項(xiàng)式計(jì)算多項(xiàng)式() =當(dāng)當(dāng)x = 5的值的值算法算法1：因?yàn)橐驗(yàn)?) =所以所以(5)=55555=3125625125255= 3906算法算法2：(5)=55

2、555=5(5555 ) =5(5(555 ) ) =5(5(5(5+5 +) + ) + ) +=5(5(5(5 (5 +) + )+)+) +算法算法1：因?yàn)橐驗(yàn)?) =所以所以(5)=55555=3125625125255= 3906算法算法2：(5)=55555=5(5555 ) =5(5(555 ) ) =5(5(5(5+5 +) + ) + ) +=5(5(5(5 (5 +) + )+)+) +共做了共做了1+2+3+4=10次乘法運(yùn)算，次乘法運(yùn)算，5次加法運(yùn)算。次加法運(yùn)算。共做了共做了4次乘法運(yùn)算，次乘法運(yùn)算，5次加法運(yùn)算。次加法運(yùn)算。數(shù)書九章數(shù)書九章秦九韶算法秦九韶算法0111

3、)(axaxaxaxfnnnn設(shè)設(shè))(xf是一個(gè)是一個(gè)n 次的多項(xiàng)式次的多項(xiàng)式對該多項(xiàng)式按下面的方式進(jìn)行改寫：對該多項(xiàng)式按下面的方式進(jìn)行改寫：0111)(axaxaxaxfnnnn01211)(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)式的值，即212naxvv323n

4、axvv01axvvnn最后的一最后的一項(xiàng)是什么？項(xiàng)是什么？這種將求一個(gè)這種將求一個(gè)n次多項(xiàng)式次多項(xiàng)式f(x)的值轉(zhuǎn)化成求的值轉(zhuǎn)化成求n個(gè)一個(gè)一次多項(xiàng)式的值的方法，稱為次多項(xiàng)式的值的方法，稱為秦九韶算法秦九韶算法。算法步驟：算法步驟：第一步：輸入多項(xiàng)式次數(shù)第一步：輸入多項(xiàng)式次數(shù)n、最高次項(xiàng)的系數(shù)、最高次項(xiàng)的系數(shù)an和和x的值的值.第二步：將第二步：將v的值初始化為的值初始化為an，將，將i的值初始化為的值初始化為1.第三步：輸入第三步：輸入i次項(xiàng)的系數(shù)次項(xiàng)的系數(shù)an-i.第四步：第四步：v=vx+an-i,i=i+1.第五步：判斷第五步：判斷i是否小于或等于是否小于或等于n，若是，則返回第，若

5、是，則返回第三步；否則，輸出多項(xiàng)式的值三步；否則，輸出多項(xiàng)式的值v。程序框圖：程序框圖：這是一個(gè)在這是一個(gè)在秦九韶算法秦九韶算法中反復(fù)執(zhí)行的步驟，因中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。輸入輸入an-i開始開始輸入輸入n,an,xi=n?輸出輸出v結(jié)束結(jié)束v=vx+an-ii=i+1YNi=1V=an ),(nkaxvvavknkkn2110特點(diǎn)：特點(diǎn)：通過一次式的反復(fù)計(jì)算，逐步得出高次多通過一次式的反復(fù)計(jì)算，逐步得出高次多項(xiàng)式的值，對于一個(gè)項(xiàng)式的值，對于一個(gè)n次多項(xiàng)式，只需做次多項(xiàng)式，只需做n次乘次乘法和法和n次加法即可。次加法即可。例例2 已知一個(gè)五次多項(xiàng)式為已知

6、一個(gè)五次多項(xiàng)式為8 . 07 . 16 . 25 . 325)(2345xxxxxxf用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x = 5的值。的值。解：解： 將多項(xiàng)式變形：將多項(xiàng)式變形：8 . 0)7 . 1)6 . 2)5 . 3)25()(xxxxxxf按由里到外的順序，依此計(jì)算一次多項(xiàng)式當(dāng)按由里到外的順序，依此計(jì)算一次多項(xiàng)式當(dāng)x = 5時(shí)的值：時(shí)的值：272551v50v5 .1385 . 35272v9 .6896 . 255 .1383v2 .34517 . 159 .6894v2 .172558 . 052 .34515v所以，當(dāng)所以，當(dāng)x = 5時(shí)，多項(xiàng)式的值等于時(shí)，多項(xiàng)式的值等于17255.2你從中看到了怎樣的規(guī)律？怎么用程序框圖來描述呢？程序框圖：開始輸入f(x)的系數(shù)：a0,a1,a2,a3,a4a5輸入x0n5?輸出v結(jié)束v=vx0+a5-nn=n+1YN n=1 v=a5 ),(nkaxvvavknkkn2110這是一個(gè)在這是一個(gè)在秦九韶算法秦九韶算法中反復(fù)執(zhí)行的步驟，因中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。此可用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。練習(xí)、已知多項(xiàng)式練習(xí)、已知多項(xiàng)式f(x)=x5+5x4+10 x3+