§§1.3算法案例(二)案例2秦九韶算法問題如何求多項式f(x)=x5+x4+x3+x2+x+1當x=5時的值呢？計算多項式ｆ(ｘ)

=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１當x=5的值算法1：由于ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１因此ｆ(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+１)+１)+１)+１)+１分析：兩種算法中各用了幾次乘法運算？和幾次加法運算？算法1：因為ｆ(ｘ)

=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ(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+１)+１)+１)+１)+１共做了1+2+3+4=10次乘法運算，5次加法運算。共做了4次乘法運算，5次加法運算。秦九韶（1202--1261年），字道古，安岳縣人。其父秦季棲，進士出身，官至工部郎中、秘書少監(jiān)。秦九韶性敏慧，勤奮好學，幼年隨父居中都（今北京），受到名師指導，學習日益增進。及長，隨父遷湖州（今浙江吳興縣），在西門外修建住房，由秦九韶設計施工，堂分7間，后為列室，僅中堂1間，縱橫7丈，極其宏偉寬敞，顯示出他在建筑方面的才干《數(shù)書九章》——秦九韶算法《數(shù)書九章》——秦九韶算法設是一個n次的多項式對該多項式按下面的方式進行改寫：思考：當懂得了x的值后該如何求多項式的值？這是如何的一種改寫方式？最后的成果是什么？規(guī)定多項式的值，應當先算最內層的一次多項式的值，即然后，由內到外逐級計算一次多項式的值，即最后的一項是什么？這種將求一種n次多項式f(x)的值轉化成求n個一次多項式的值的辦法，稱為秦九韶算法。思考：在求多項式的值上，這是如何的一種轉化？算法環(huán)節(jié)：第一步：輸入多項式次數(shù)n、最高次項的系數(shù)an和x的值.第二步：將v的值初始化為an，將i的值初始化為n-1.第三步：輸入i次項的系數(shù)ai第四步：v=vx+ai,i=i-1.第五步：判斷i與否不不大于或等于0，若是，則返回第三步；否則，輸出多項式的值v。程序框圖：這是一種在秦九韶算法中重復執(zhí)行的環(huán)節(jié)，因此可用循環(huán)構造來實現(xiàn)。輸入ai開始輸入n,an,xi0?輸出v結束v=vx+aii=i-1YNi=n-1V=an輸入ai開始輸入n,an,xi0?輸出v結束v=vx+aii=i-1YNi=n-1V=anINPUT"n=";nINPUT"an=";aINPUT"x=";xv=ai=n-1WHILEi>=0PRINT"i=";iINPUT"ai=";av=v*x+ai=i-1WENDPRINTvEND程序特點：通過一次式的重復計算，逐步得出高次多項式的值，對于一種n次多項式，只需做n次乘法和n次加法即可。例1:用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當x=5時的值.解法一:首先將原多項式改寫成以下形式: f(x)=((((2x-5)x-4)x+3)x-6)x+7v0=2v1=v0x-5=2×5-5=5v2=v1x-4=5×5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677因此,當x=5時,多項式的值是2677.然后由內向外逐級計算一次多項式的值,即2-5-43-67x=5105252110510854053426702677因此,當x=5時,多項式的值是2677.原多項式的系數(shù)多項式的值.例1:用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當x=5時的值.解法二:列表22-50-43-60x=5105252512512160560830403034因此,當x=5時,多項式的值是15170.練一練:用秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當x=5時的值.解:原多項式先化為:

f(x)=2x6-5x5+0×x4-4x3+3x2-6x+0列表21517015170注意:n次多項式有n+1項,因此缺少哪一項應將其系數(shù)補0.例2已知一種五次多項式為用秦九韶算法求這個多項式當x=5的值。解：將多項式變形：按由里到外的次序，依此計算一次多項式當x=5時的值：因此，當x=5時，多項式的值等于14130.2你從中看到了如何的規(guī)律？怎么用程序框圖來描述呢？程序框圖：開始輸入f(x)的系數(shù)：a0,a1,a2,a3,a4,a5輸入x0n≤5?輸出v結束v=vx0+a5-nn=n+1NY

n=