必修3-1.3.2算法案例

1、特級教師 王新敞 源頭學(xué)子 125 九月 2022 王新敞 (必修3)第一 章 算法初步1.3算法案例案例2秦九韶算法特級教師 王新敞 源頭學(xué)子 2問題提出 1.輾轉(zhuǎn)相除法和更相減損術(shù)，是求兩個正整數(shù)的最大公約數(shù)的優(yōu)秀算法，我們將算法轉(zhuǎn)化為程序后，就可以由計(jì)算機(jī)來執(zhí)行運(yùn)算，實(shí)現(xiàn)了古代數(shù)學(xué)與現(xiàn)代信息技術(shù)的完美結(jié)合. 2.對于求n次多項(xiàng)式的值，在我國古代數(shù)學(xué)中也有一個優(yōu)秀算法，即秦九韶算法，本節(jié)對這個算法作些了解和探究.特級教師 王新敞 源頭學(xué)子 3怎樣求多項(xiàng)式當(dāng)x=5時的值？計(jì)算統(tǒng)計(jì)可以得出我們共需要10次乘法運(yùn)算，5次加法運(yùn)算 . 再統(tǒng)計(jì)一下計(jì)算當(dāng)時的值時需要的計(jì)算次數(shù)，可以得出僅需4次乘法和

2、5次加法運(yùn)算即可得出結(jié)果。顯然少了6次乘法運(yùn)算。我們把多項(xiàng)式變形為：這種算法就叫秦九韶算法。4+3+2+1=10次乘法運(yùn)算， 5次加法運(yùn)算. 特級教師 王新敞 源頭學(xué)子 4把一個多項(xiàng)式改寫為：一般計(jì)算步驟如下：秦九韶算法=特級教師 王新敞 源頭學(xué)子 5對于f(x)=(anx+an-1)x+ an-2)x+a1)x+a0，由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，其算法步驟： 第一步，計(jì)算v1=anx+an-1. 第二步，計(jì)算v2=v1x+an-2.第三步，計(jì)算v3=v2x+an-3. 第n步，計(jì)算vn=vn-1x+a0.一般計(jì)算步驟如下：秦九韶算法這樣將求n次多項(xiàng)式f(x)的值轉(zhuǎn)化為求n個一次多項(xiàng)式的值

3、。特級教師 王新敞 源頭學(xué)子 6秦九韶算法的程序設(shè)計(jì)及程序框圖 用秦九韶算法求多項(xiàng)式的值，其算法步驟設(shè)計(jì)：第一步，輸入多項(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.第五步，判斷i0是否成立.若是，則返回第二步；否則，輸出多項(xiàng)式的值v. 開始輸入n，an，x的值v=anv=vx+ai輸入aii0？i=n-1i=i-1結(jié)束是輸出v否特級教師 王新敞 源頭學(xué)子 7秦九韶算法的程序框圖對應(yīng)的程序開始輸入n，an，x的值v=anv=vx+ai輸入aii0？i=n-1i=i-1結(jié)束是輸出v否INPUT “

4、n=”；nINPUT “an=”；aINPUT “x=”；x v=ai=n-1WHILE i=0INPUT “ai=”；a v=v*x+ai=i-1 WENDPRINT vENDPRINT “i=”;i秦九韶算法的演示特級教師 王新敞 源頭學(xué)子 8 練習(xí)1 已知一個5次多項(xiàng)式為 用秦九韶算法求f(5)的值.f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=55+2=27；v2=275+3.5=138.5；v3=138.55-2.6=689.9；v4=689.95+1.7=3451.2；v5=3451.25-0.8=17255.2.所以f(5)= =17255.2.秦九韶算法演示特級教師 王新敞 源頭學(xué)子 9 練習(xí)2 閱讀下列程序，說明它解決的實(shí)際問題是什么？INPUT “x=”；an=0y=0WHLE n5 y=y+(n+1)*an n=n+1WENDPRINT yEND求多項(xiàng)式 在x=a時的值. 特級教師 王新敞 源頭學(xué)子 10小結(jié) 評價一個算法好壞的一個重要標(biāo)志是運(yùn)算的次數(shù)，如果一個算法從理論上需要超出計(jì)算機(jī)允許范圍內(nèi)的運(yùn)算次數(shù)，那么這樣的