《算法案例---秦九韶算法》課件（新人教A版必修3）.ppt

1、算 法 案 例-秦九韶算法,在數(shù)學(xué)的發(fā)展史上，從公元前2、3世紀(jì)公元14世紀(jì)，中國的數(shù)學(xué)雖有過高潮，也有過低落，但一直走在世界的前列，是世界數(shù)學(xué)的中心。中國古代數(shù)學(xué)對世界數(shù)學(xué)發(fā)展有著不可磨滅的貢獻。秦九韶算法就是中國古代數(shù)學(xué)的一枝奇葩。 今天這節(jié)課我們領(lǐng)略秦九韶算法的魅力。,（1）設(shè)計求多項式,當(dāng)x=5時的值的算法，并寫出程序。 （2）有沒有更高效的算法？能否探求更好的算法，來解決任意多項式的求解問題？,T引導(dǎo)學(xué)生把多項式變形為：,思考：從內(nèi)到外，如果把每一個括號都看成一個常數(shù)，那么變形后的式子中有哪些“一次式”？x的系數(shù)依次是什么？,（3）若將x的值代入變形后的式子中，那么求值的計算過程是怎

2、樣的？,將變形前x的系數(shù)乘以x的值，加上變形前的第2個系數(shù)，得到一個新的系數(shù)；將此系數(shù)繼續(xù)乘以x的值，再加上變形前的第3個系數(shù)，又得到一個新的系數(shù)；繼續(xù)對新系數(shù)做上面的變換，直到與變形前的最后一個系數(shù)相加，得到一個新的系數(shù)為止。這個系數(shù)即為所求多項式的值。這種算法即是“秦九韶算法”,（4）用秦九韶算法求多項式的值，與多項式組成有直接關(guān)系嗎？用秦九韶算法計算上述多項式的值，需要多少次乘法運算和多少次加法運算？,數(shù)書九章秦九韶算法,對該多項式按下面的方式進行改寫：,思考：當(dāng)知道了x的值后該如何求多項式的值？,這是怎樣的一種改寫方式？最后的結(jié)果是什么？,要求多項式的值，應(yīng)該先算最內(nèi)層的一次多項式的值

3、，即,然后，由內(nèi)到外逐層計算一次多項式的值，即,最后的一項是什么？,這種將求一個n次多項式f(x)的值轉(zhuǎn)化成求n個一次多項式的值的方法，稱為秦九韶算法。,思考：在求多項式的值上，這是怎樣的一個轉(zhuǎn)化？,通過一次式的反復(fù)計算，逐步得出高次多項式的值，對于一個n次多項式，只需做n次乘法和n次加法即可。,秦九韶算法的特點：,算法步驟：,第一步：輸入多項式次數(shù)n、最高次項的系數(shù)an和x的值.,第二步：將v的值初始化為an，將i的值初始化為1.,第三步：輸入i次項的系數(shù)an-i.,第四步：v=vx+an-i,i=i+1.,第五步：判斷i是否小于或等于n，若是，則返回第三步；否則，輸出多項式的值v。,程序框圖：,這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實現(xiàn)。,輸入an-i,（3）程序：,INPUT “n=”；n INPUT “an=“;a INPUT “x=“;x v=a i=n-1 WHILE i=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1 WEND PRINT v END,小結(jié)： （1）算法具有通用的特點，可以解決一類問題； （2）解決同一類問題，可以有不同