示范教案13算法案例(編輯修改稿)
2024-12-30 20:10 本頁面
【文章內容簡介】 思路 2（直接導入） 前面我們學習了輾轉相除法與更相減損術， 今天我們開始學習秦九韶算法 . 推進新課 新知探究 提出問題 （ 1）求多項式 f(x)=x5+x4+x3+x2+x+1當 x=5時的值有哪些方法？比較它們的特點 . （ 2）什么是秦九韶算法？ （ 3）怎樣評價一個算法的好壞？ 討論結果： （ 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 的值，這樣每次都可以利用上一次計算的結果，這時，我們一共做了 4次乘法運算， 5次加法運算 . 第二種做法與第一種做法 相比，乘法的運算次數減少了，因而能夠提高運算效率，對于計算機來說，做一次乘法運算所用的時間比做一次加法運算要長得多，所以采用第二種做法，計算機能更快地得到結果 . （ 2）上面問題有沒有更有效的算法呢？我國南宋時期的數學家秦九韶（約 1202~1261）在他的著作《數書九章》中提出了下面的算法： 把一個 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. 求多項式的值時，首先計算最內層括號內一次多項式的值，即 v1=anx+an1， 然后由內向外逐層計算一次多項式的值，即 v2=v1x+an2， v3=v2x+an3， … vn=vn1x+a0， 這樣，求 n次多項式 f（ x）的值就轉化為求 n個一次多項式的值 . 上述方法稱為秦九韶算法 .直到今天，這種算法仍是多項式求值比較先進的算法 . （ 3）計算機的一個很重要的特點就是運算速 度快，但即便如此，算法好壞的一個重要標志仍然是運算的次數 .如果一個算法從理論上需要超出計算機允許范圍內的運算次數，那么這樣的算法就只能是一個理論的算法 . 應用示例 例 1 已知一個 5次多項式為 f（ x） =5x5+2x4++， 用秦九韶算法求這個多項式當 x=5時的值 . 解： 根據秦九韶算法，把多項式改寫成如下形式： f(x)=（ (((5x+2)x+))x+)， 按照從內到外的順序，依次計算一次多項式當 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 ? 這是一個在秦九韶算法中反復執(zhí)行的步驟，因此可用循環(huán)結構來實現 . 算法步驟如下： 第一步，輸 入多項式次數 n、最高次的系數 an和 x的值 . 第二步，將 v的值初始化為 an，將 i的值初始化為 n1. 第三步，輸入 i次項的系數 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 點評： 本題是古老算法與現代計算機語言的完美結合，詳盡介紹了思想方法、算法步驟、程序框圖和算法語句 ,是一個典型的算法案例 . 變式訓練 請以 5次多項式函數為例說明秦九韶算法，并畫出程序框圖 . 解： 設 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. 上面的分層計算 ,只用了小括號，計算時，首先計算最內層的括號，然后由里向外逐層計算，直到最外層的括號，然后加上常數項即可 . 程序框圖如下圖： 例 2 已知 n次多項式 Pn(x)=a0xn+a1xn1+…+a n1x+an，如果在一種算法中，計算 kx0 （ k=2， 3，4， … ， n）的值需要 k－ 1次乘法，計算 P3(x0)的值共需要 9次運算（ 6次乘法， 3次加法），那么計算 P10(x0)的值共需要 __________次運算 .下面給出一種減少運算次數的算法：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的求值問題 .直接法乘法運算的次數最多可到達 2)1( nn? ，加法最多 n 次 .秦九韶算法通過轉化把乘法運算的次數減少到最多 n次， 加法最多 n次 . 例 3 已知多項式函數 f(x)=2x5－ 5x4－ 4x3+3x2－ 6x+7，求當 x=5時的函數的值
教學課件相關推薦
鄂ICP備17016276號-1