課時算法案例秦九韶算法

1、作業(yè)：開始輸入m,nM-n0R=m-nM=max(n,r)N=min(n,r)輸出n結(jié)束Input “m,n=”;m,nWhile mnR=m-nM=max(n,r)N=min(n,r)WendPrint n End1課時2 秦九韶算法2教學(xué)設(shè)計問題1設(shè)計求多項式f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時的值的算法,并寫出程序.x=5f=2x5-5x4-4x3+3x2-6x+7PRINT fEND程序點評:上述算法一共做了15次乘法運算,5次加法運算.優(yōu)點是簡單,易懂;缺點是不通用,不能解決任意多項多求值問題,而且計算效率不高.3 這析計算上述多項式的值,一共需要9次乘法運算

2、,5次加法運算.問題2有沒有更高效的算法?分析:計算x的冪時,可以利用前面的計算結(jié)果,以減少計算量,即先計算x2,然后依次計算的值.第二種做法與第一種做法相比,乘法的運算次數(shù)減少了,因而能提高運算效率.而且對于計算機來說,做一次乘法所需的運算時間比做一次加法要長得多,因此第二種做法能更快地得到結(jié)果.4問題3能否探索更好的算法,來解決任意多項式的求值問題?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0

3、 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所以,當(dāng)x=5時,多項式的值是2677.這種求多項式值的方法就叫秦九韶算法.5例1:用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時的值.解法一:首先將原多項式改寫成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=

4、5345+7=2677所以,當(dāng)x=5時,多項式的值是2677.然后由內(nèi)向外逐層計算一次多項式的值,即6f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我們可以改寫成如下形式:f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求多項式的值時,首先計算最內(nèi)層括號內(nèi)一次多項式的值,即 v1=anx+an-1,然后由內(nèi)向外逐層計算一次多項式的值,即一般地,對于一個n次多項式v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.這樣,求n次多項式f(x)的值就轉(zhuǎn)化為求n個一次多項式的值.這種算法稱為秦九韶算法.7點評:秦九韶算法是求一元多項式的值

5、的一種方法.它的特點是:把求一個n次多項式的值轉(zhuǎn)化為求n個一次多項式的值,通過這種轉(zhuǎn)化,把運算的次數(shù)由至多n(n+1)/2次乘法運算和n次加法運算,減少為n次乘法運算和n次加法運算,大大提高了運算效率.f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.8練一練:用秦九韶算法求多項式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)x=5時的值.解:原多項式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+09v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.觀察上述秦九韶算法中的n個一次式,可見vk的計算

6、要用到vk-1的值.若令v0=an,得v0=an,vK=vK-1x+an-k(k=1,2,n這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟,因此可用循環(huán)結(jié)構(gòu)來實現(xiàn).10第一步，輸入多項式次數(shù)n,最高項系數(shù)an和x的值第二步，將v的值初始化為an，將i的值初始化為n-1第三步，輸入i次項的系數(shù)ai第四步，v=vx+ai,i=i-1第五步判斷i是否大于等于，若是，則返回第二步，否則輸出多項式的值v否開始輸入n,x,an ,輸入v=ani=0?i=n-1i=i-1輸出v結(jié)束是v=vx+ai輸入ai算法：程序框圖11程序：Input “n=”;nInput “an=”;aInput “x=”;xV=ai=n-1While i=0Print “i=”;IInput “ai=”;aV=v*x+ai=i-1WendPrint vend12問題畫出程序框圖,表示用秦九韶算法求5次多項式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0當(dāng)x=x0 (x0是任意實數(shù))時的值的過程,然后寫出程序.13否程序框圖開始輸入a0,a1,a2,a3,a4,a5輸入x0n5?n=1v=a