算法案例時PPT學習教案

1、會計學1 算法案例時算法案例時 數(shù)書九章數(shù)書九章秦九韶算法秦九韶算法 01 1 1 )(axaxaxaxf n n n n 設設)(xf是一個是一個n次的多項式次的多項式. 對該多項式按下面的方式進行改寫：對該多項式按下面的方式進行改寫： 01 1 1 )(axaxaxaxf n n n n 01 2 1 1 )(axaxaxa n n n n 012 3 1 2 )(axaxaxaxa n n n n 0121 )(axaxaxaxa nnn 這是怎樣的 一種改寫方 式？最后的 結(jié)果是什么 ？ 第1頁/共13頁 012n1nn a)xa)xa)xax(a(f(x) 要求多項式的值，應該先算最

2、內(nèi)層的一次多項式要求多項式的值，應該先算最內(nèi)層的一次多項式 的值，即的值，即 1nn1 axav 然后，由內(nèi)到外逐層計算一次多項式的值，即然后，由內(nèi)到外逐層計算一次多項式的值，即 2n12 axvv 3n23 axvv 01nn axvv 最后的一 項是什么 ？ 這種將求一個這種將求一個n次多項式次多項式f（x）的值轉(zhuǎn)化成求的值轉(zhuǎn)化成求n個一個一 次多項式的值的方法，稱為次多項式的值的方法，稱為秦九韶算法秦九韶算法. 第2頁/共13頁 例例2 已知一個五次多項式為已知一個五次多項式為 0.81.7x2.6x3.5x2x5xf(x) 2345 用秦九韶算法求這個多項式當用秦九韶算法求這個多項式當

3、x = 5的值的值. 解：解： 將多項式變形：將多項式變形： 0.81.7)x2.6)x3.5)x2)x(5xf(x) 按由里到外的順序，依此計算一次多項式當按由里到外的順序，依此計算一次多項式當x = 5時的值：時的值： 27255v1 5v0 138.53.5527v2 689.92.65138.5v3 3451.21.75689.9v4 17255.20.853451.2v5 所以，當所以，當x = 5時，多項式的值等于時，多項式的值等于17255.2 你從中看到你從中看到 了怎樣的規(guī)律了怎樣的規(guī)律 ？怎么用程序？怎么用程序 框圖來描述呢框圖來描述呢 ？ 第3頁/共13頁 開始開始 輸入

4、輸入f (x)的系數(shù)：的系數(shù)： a0, a1, a2, a3, a4, a5 輸入輸入x0 n=0 v=a5 v= vx0+a5-n n=n+1 n 5? 輸出輸出v 結(jié)束結(jié)束 否否 是是 注意：要想使用檢驗功能，請使用前，先要減低宏的安全限制注意：要想使用檢驗功能，請使用前，先要減低宏的安全限制. 第4頁/共13頁 秦九韶算法檢驗 排序的算法排序的算法 將下面數(shù)字按由小到大的順序排列將下面數(shù)字按由小到大的順序排列 8，3，2，5，9，6 方法方法1：S1：比較第 ：比較第2個數(shù)與第個數(shù)與第1個數(shù)的大小，并排序得個數(shù)的大小，并排序得3，8 S2：將第：將第3個數(shù)與個數(shù)與S1中的數(shù)比較，插入適當

5、的位置，中的數(shù)比較，插入適當?shù)奈恢茫?得到得到 2，3，8 S3：將第：將第4個數(shù)與個數(shù)與S2中的數(shù)比較，并插入適當?shù)奈恢械臄?shù)比較，并插入適當?shù)奈?置，如此繼續(xù)下去，直到把最后一個數(shù)插入到上一置，如此繼續(xù)下去，直到把最后一個數(shù)插入到上一 步已排好步已排好 的數(shù)列的合適位置為止，得到：的數(shù)列的合適位置為止，得到： 2 ，3， 5， 8 2 ，3， 5， 8 ，9 2 ，3， 5， 6 ， 8 ， 9 S4： S5： 第5頁/共13頁 排序的算法排序的算法 將下面數(shù)字按由小到大的順序排列將下面數(shù)字按由小到大的順序排列 8，3，2，5，9，6 方法方法1： 過過 程程 演演 示示 832596 開始

6、開始 排第排第1次次 排第排第2次次 排第排第3次次 排第排第4次次 832596 382596 238596 235896 235896 排第排第5次次235689 第6頁/共13頁 排序的算法排序的算法 將下面數(shù)字按由小到大的順序排列將下面數(shù)字按由小到大的順序排列 8，3，2，5，9，6 方法方法2：S1： ：用第用第1個數(shù)與第個數(shù)與第2個數(shù)比較，若前者小個數(shù)比較，若前者小 則兩數(shù)不變，否則，交換這兩個數(shù)的位置則兩數(shù)不變，否則，交換這兩個數(shù)的位置. S2：按這樣的原則，比較第按這樣的原則，比較第2個數(shù)和第個數(shù)和第3個個 數(shù)，前者小則兩數(shù)不變，否則，交換這兩數(shù)，前者小則兩數(shù)不變，否則，交換這

7、兩 個數(shù)的位置個數(shù)的位置直到比完最后兩個數(shù)直到比完最后兩個數(shù).（稱（稱 為為“一趟一趟”） S3：如果前一趟的比較中交換的次數(shù)為如果前一趟的比較中交換的次數(shù)為0， 說明排序已完成，否則回到說明排序已完成，否則回到S2. 根據(jù)題意根據(jù)題意 ，一趟后，一趟后 的結(jié)果是的結(jié)果是 什么？什么？ 為什么說前為什么說前 一趟的比較一趟的比較 中交換為中交換為0 次時，排序次時，排序 完成？完成？ 3，2，5， 8， 6 ， 9 第7頁/共13頁 排序的算法排序的算法 將下面數(shù)字按由小到大的順序排列將下面數(shù)字按由小到大的順序排列 8，3，2，5，9，6 請將每一趟的結(jié)果寫出來請將每一趟的結(jié)果寫出來 第第1趟

8、趟 8 3 2 5 9 6 3 8 2 5 9 6 3 2 8 5 9 6 3 2 5 8 9 6 3 2 5 8 9 6 3 2 5 8 6 9 該趟中交換的次數(shù)為該趟中交換的次數(shù)為_次次4 第8頁/共13頁 排序的算法排序的算法 將下面數(shù)字按由小到大的順序排列將下面數(shù)字按由小到大的順序排列 8，3，2，5，9，6 請將每一趟的結(jié)果寫出來請將每一趟的結(jié)果寫出來 第第2趟趟 3 2 5 8 6 9 2 3 5 8 6 9 2 3 5 8 6 9 2 3 5 8 6 9 2 3 5 6 8 9 2 3 5 6 8 9 該趟中交換的次數(shù)為該趟中交換的次數(shù)為_次次 2 第9頁/共13頁 排序的算法排序的算法 將下面數(shù)字按由小到大的順序排列將下面數(shù)字按由小到大的順序排列 8，3，2，5，9，6 請將每一趟的結(jié)果寫出來請將每一趟的結(jié)果寫出來 第第3趟趟 2 3 5 6 8 9 2 3 5 6 8 9 2 3 5 6 8 9 2 3 5 6 8 9 2 3 5 6 8 9 2 3 5 6 8 9 該趟中交換的次數(shù)為該趟中交換的次數(shù)為_次，次，0 所以排序的結(jié)果為所以排序的結(jié)果為： 2，3，5，6，8，9 第10頁/共13頁 (1)秦九韶算法計算多項式的值及程序設計