示范教案13算法案例(編輯修改稿)
2024-12-30 20:10 本頁面
【文章內(nèi)容簡介】 思路 2（直接導(dǎo)入） 前面我們學(xué)習了輾轉(zhuǎn)相除法與更相減損術(shù)， 今天我們開始學(xué)習秦九韶算法 . 推進新課 新知探究 提出問題 （ 1）求多項式 f(x)=x5+x4+x3+x2+x+1當 x=5時的值有哪些方法？比較它們的特點 . （ 2）什么是秦九韶算法？ （ 3）怎樣評價一個算法的好壞？ 討論結(jié)果： （ 1）怎樣求多項式 f(x)=x5+x4+x3+x2+x+1當 x=5時的值呢？ 一個自然的做法就是把 5代入多項式 f(x)，計算各項的值，然后把它們加起來，這時，我們一共做了 1+2+3+4=10次乘法運算， 5次加法運算 . 另一種做法是先計算 x2的值，然后依次計算 x2x ，（ x2x ） x ，（（ x2x ） x ） x 的值，這樣每次都可以利用上一次計算的結(jié)果，這時，我們一共做了 4次乘法運算， 5次加法運算 . 第二種做法與第一種做法 相比，乘法的運算次數(shù)減少了，因而能夠提高運算效率，對于計算機來說，做一次乘法運算所用的時間比做一次加法運算要長得多，所以采用第二種做法，計算機能更快地得到結(jié)果 . （ 2）上面問題有沒有更有效的算法呢？我國南宋時期的數(shù)學(xué)家秦九韶（約 1202~1261）在他的著作《數(shù)書九章》中提出了下面的算法： 把一個 n次多項式 f(x)=anxn+an1xn1+…+a 1x+a0改寫成如下形式： f(x)=anxn+an1xn1+…+a 1x+a0 =（ anxn1+an1xn2+…+a 1） x+ a0 =（（ anxn2+an1xn3+…+a 2） x+a1)x+a0 =… =（ … （（ anx+an1） x+an2） x+…+a 1） x+a0. 求多項式的值時，首先計算最內(nèi)層括號內(nèi)一次多項式的值，即 v1=anx+an1， 然后由內(nèi)向外逐層計算一次多項式的值，即 v2=v1x+an2， v3=v2x+an3， … vn=vn1x+a0， 這樣，求 n次多項式 f（ x）的值就轉(zhuǎn)化為求 n個一次多項式的值 . 上述方法稱為秦九韶算法 .直到今天，這種算法仍是多項式求值比較先進的算法 . （ 3）計算機的一個很重要的特點就是運算速 度快，但即便如此，算法好壞的一個重要標志仍然是運算的次數(shù) .如果一個算法從理論上需要超出計算機允許范圍內(nèi)的運算次數(shù)，那么這樣的算法就只能是一個理論的算法 . 應(yīng)用示例 例 1 已知一個 5次多項式為 f（ x） =5x5+2x4++， 用秦九韶算法求這個多項式當 x=5時的值 . 解： 根據(jù)秦九韶算法，把多項式改寫成如下形式： f(x)=（ (((5x+2)x+))x+)， 按照從內(nèi)到外的順序，依次計算一次多項式當 x=5時的值： v0=5； v1=55+2=27。 v2=275+=。 v3==。 v4=5+=3 。 v5=3 =17 。 所以，當 x=5時，多項式的值等于 17 . 算法分析： 觀察上述秦九韶算法中的 n個一次式，可見 vk的計算要用到 vk1的值，若令 v0=an，我們可以得到下面的公式： ??? ?????? ).,2,1(,10 nkaxvv avknkkn ? 這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟，因此可用循環(huán)結(jié)構(gòu)來實現(xiàn) . 算法步驟如下： 第一步，輸 入多項式次數(shù) n、最高次的系數(shù) an和 x的值 . 第二步，將 v的值初始化為 an，將 i的值初始化為 n1. 第三步，輸入 i次項的系數(shù) ai. 第四步， v=vx+ai,i=i1. 第五步，判斷 i是否大于或等于 ，則返回第三步；否則，輸出多項式的值 v. 程序框圖如下圖 ： 程序 ： INPUT “n=”； n INPUT “an=”； a INPUT “x=”； x v=a i=n1 WHILE i＞ =0 PRINT “i=”； i INPUT “ai=”； a v=v*x+a i=i1 WEND PRINT v END 點評： 本題是古老算法與現(xiàn)代計算機語言的完美結(jié)合，詳盡介紹了思想方法、算法步驟、程序框圖和算法語句 ,是一個典型的算法案例 . 變式訓(xùn)練 請以 5次多項式函數(shù)為例說明秦九韶算法，并畫出程序框圖 . 解： 設(shè) f（ x） =a5x5+a4x4+a3x3+a2x2+a1x+a0 首先，讓我們以 5次多項式一步步地進行改寫： f（ x） =（ a5x4+a4x3+a3x2+a2x+a1） x+a0 =（（ a5x3+a4x2+ a3x+a2） x+a1） x+a0 =（（（ a5x2+a4x+ a3） x+a2） x+a1） x+a0 =（（（（ a5x+a4） x+ a3） x+a2） x+a1） x+a0. 上面的分層計算 ,只用了小括號，計算時，首先計算最內(nèi)層的括號，然后由里向外逐層計算，直到最外層的括號，然后加上常數(shù)項即可 . 程序框圖如下圖： 例 2 已知 n次多項式 Pn(x)=a0xn+a1xn1+…+a n1x+an，如果在一種算法中，計算 kx0 （ k=2， 3，4， … ， n）的值需要 k－ 1次乘法，計算 P3(x0)的值共需要 9次運算（ 6次乘法， 3次加法），那么計算 P10(x0)的值共需要 __________次運算 .下面給出一種減少運算次數(shù)的算法：P0(x)=a0,Pk+1(x)=xPk(x)+ak+1（ k＝ 0， 1， 2， … ， n－ 1）．利用該算法，計算 P3(x0)的值共需要6次運算，計算 P10(x0)的值共需要 ___________次運算 . 答案： 65 20 點評： 秦九韶算法適用一般的多項式 f(x)=anxn+an1xn1+…+a 1x+a0的求值問題 .直接法乘法運算的次數(shù)最多可到達 2)1( nn? ，加法最多 n 次 .秦九韶算法通過轉(zhuǎn)化把乘法運算的次數(shù)減少到最多 n次， 加法最多 n次 . 例 3 已知多項式函數(shù) f(x)=2x5－ 5x4－ 4x3+3x2－ 6x+7，求當 x=5時的函數(shù)的值
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1