1、1.3算法案例,秦九韶算法,石家莊市第十九中學(xué) 岳儒芳,算法1：,問(wèn)題1,4次乘法運(yùn)算,5次加法運(yùn)算.,問(wèn)題2有沒(méi)有更高效的算法?,計(jì)算x的冪時(shí),可以利用前面的計(jì)算結(jié)果,以減少計(jì)算量,例1、已知多項(xiàng)式 , 求 的值,10次乘法運(yùn)算，5次加法運(yùn)算.,先計(jì)算x2，,然后依次計(jì)算,想法1：,想法2：,例2、已知 ，求,分析:,將 代入上式，從內(nèi)往外依次計(jì)算,問(wèn)題3,就是按照一定規(guī)則，解決某一類問(wèn)題的明確的有限的步驟.,例1、已知 , 求 .,例2、已知 , 求 .,算法：,我們可以改寫成如下形式:,f(x)=(anx+an-1)x+an-2)x+a1)x+a0.,求多項(xiàng)式的值時(shí),首先計(jì)算最內(nèi)層括號(hào)內(nèi)

2、一次多項(xiàng)式的值,即,然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值,即,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,這樣,求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值.這種算法稱為秦九韶算法.,v0=an,v1=anx+an-1,秦九韶（1208年1261年）南宋官員、數(shù)學(xué)家，與李冶、楊輝、朱世杰并稱宋元數(shù)學(xué)四大家。主要成就:1247年完成了數(shù)學(xué)名著數(shù)學(xué)九章，其中的大衍求一術(shù)、三斜求積術(shù)和秦九韶算法是具有世界意義的重要貢獻(xiàn)。秦九韶算法就是中國(guó)古代數(shù)學(xué)的一枝奇葩。直到今天，這種算法仍是多項(xiàng)式求值比較先進(jìn)的算法 。 美國(guó) 著名科學(xué)史家薩頓說(shuō)過(guò)，秦九韶是“他那個(gè)民族，他

3、那個(gè)時(shí)代，并且確實(shí)也是所有時(shí)代最偉大的數(shù)學(xué)家之一”。,v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟,因此可用 循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn).,f(x)=(anx+an-1)x+an-2)x+a1)x+a0.,v0=an,(k=1,2,n),根據(jù) “初始化變量、設(shè)定循環(huán)控制條件、確定循環(huán)體”來(lái)構(gòu)造循環(huán)結(jié)構(gòu),寫算法步驟,畫程序框圖,編程,研究步驟：,知識(shí)探究(二):秦九韶算法的程序設(shè)計(jì),思考:用秦九韶算法求多項(xiàng)式的值，可以用當(dāng)型循環(huán)結(jié)構(gòu)來(lái)構(gòu)造算法.其算法步驟如何設(shè)計(jì)？,第一步，輸入多項(xiàng)式的次數(shù)n， 最高次項(xiàng)的系數(shù)an和

4、x的值.,第二步，令v=an，i=n-1.,第三步，判斷“i0”是否成立. 若是，執(zhí)行第四步，否則，輸出多項(xiàng)式的值v.,第四步，輸入ai，v=vx+ai，i=i-1； 返回第三步.,根據(jù) “初始化變量、設(shè)定循環(huán)控制條件、確定循環(huán)體”來(lái)構(gòu)造循環(huán)結(jié)構(gòu),思考2:該算法的程序框圖如何表示？,是,第一步，輸入多項(xiàng)式的次數(shù)n， 最高次項(xiàng)的系數(shù)an和x的值.,第二步，令v=an，i=n-1.,第三步，判斷“i0”是否成立. 若是，執(zhí)行第四步， 否則，輸出多項(xiàng)式的值v.,第四步，輸入ai，v=vx+ai， i=i-1；返回第三步.,思考3:程序？,INPUT “n=”；n,INPUT “an=”；a,INPUT “x=”；x,v=a,i=n-1,WHILE i=0,INPUT “ai=”；a,v=v*x+a,i=i-1,WEND,PRINT v,END,是,PRINT “i=”；i,小結(jié):,1、秦九韶算法；,2、轉(zhuǎn)化思想和算法思想；,作業(yè)： 4、P45練習(xí)：2. 5、P48習(xí)題1.3A組：2.,3、用直到型循環(huán)結(jié)構(gòu)寫出秦九韶算法的算法步驟、畫出其程序框圖并編制程序