13算法案例教學(xué)課公開課一等獎(jiǎng)?wù)n件省賽課獲獎(jiǎng)?wù)n件

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

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

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

n=