2015高中數(shù)學(xué) 1.3算法案例 (2)ppt課件

1、1.3算法案例秦九韶算法問題1 某位同窗求多項式f(x)=x5+x4+x3+x2+x+1當(dāng)x=5時的值，設(shè)計一個算法后寫出程序如下：x=5f=x5 + x4 + x3 + x2 + x + 1PRINT fEND程序 上述算法一共做了 次乘法運算, 次加法運算.優(yōu)點是簡單,易懂;缺陷是不通用,不能處理恣意多項多求值問題,而且計算效率不高.105能否找到更高效的算法?問題2 怎樣找到更高效的算法?分析:計算x的冪時,應(yīng)充分利用前面的計算結(jié)果,以減少計算量,如：先計算x2,然后依次計算222,(),()xx xxxxxxx的值. 此時算法一共做了 次乘法運算, 次加法運算.45f(x)=x5+x4

2、+x3+x2+x+1可變形為f(x)=(x4+x3+x2+x+1)x+1 =(x3+x2+x+1)x+1)x+1 =(x2+x+1)x+1)x+1 )x+1 =(x+1)x+1)x+1)x+1)x+1f(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(

3、x)的值就轉(zhuǎn)化為求n個一次多項式的值.這種算法稱為秦九韶算法.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 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.這種求多項式值的方法就是秦九韶算法.例1:用秦九韶算法求多項式 f(x)=2x5-5x

4、4-4x3+3x2-6x+7當(dāng)x=5時的值.變形前的計算，變形前的計算，需求多少次乘法需求多少次乘法計算和多少次加計算和多少次加法計算？法計算？變形后利用秦九韶算法計算n次多項式當(dāng)x=x0時，需求多少次乘法計算和多少次加法計算？所以所以,當(dāng)當(dāng)x=5時時,多項式的值是多項式的值是2677.原多項式的系數(shù)例1:用秦九韶算法求多項式 f(x)=2x5-5x4-4x3+3x2-6x+7當(dāng)x=5時的值.2 -5 -4 3 -6 7x=5105252110510854053426702677多項式的值.解法二:列表2V0V1V2V3V4V5所以,當(dāng)x=5時,多項式的值是15170. 練:用秦九韶算法求多項

5、式 f(x)=2x6-5x5-4x3+3x2-6x當(dāng)x=5時的值.解:原多項式先化為: f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列表2 -5 0 -4 3 -6 0 x=510525251251216056083040303421517015170 留意:n次多項式有n+1項,因此短少哪一項應(yīng)將其系數(shù)補(bǔ)0.察看上述秦九韶算法中的n個一次式,可見vk的計算要用到vk-1的值.假設(shè)令v0=an,得遞推式v0=an,vK=vK-1x+an-k(k=1,2,n 這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟,因此可用循環(huán)構(gòu)造來實現(xiàn).試寫出程序框圖。變式訓(xùn)練，深化提高變式訓(xùn)練，深化提高程序框圖否開場輸入n, x, ani=0?v=ani=n-1i=i-1輸出v終了是v=vx+ai輸入ai程序：程序：對比課本對比課本第第39頁頁2.試搜索資料了解秦久韶，談?wù)勊麑υ囁阉髻Y料了解秦久韶，談?wù)勊麑λ膫ゴ笾幍恼J(rèn)識。他的偉大之處的認(rèn)識?！军c評】秦九韶算法是求一元多項式的值的一種方法.它的特點是:把求一個n次多項式的值轉(zhuǎn)化為求n個一次多項式的值,經(jīng)過這種轉(zhuǎn)化,把運算的次數(shù)由至多n(n+1)/2次乘法運算和n次加法運算,減少為n次乘法運算和n次