1.3.2 算法案例-秦九韶算法 課件2.ppt

算法案例 第二課時(shí) 計(jì)算多項(xiàng)式 當(dāng)x 5的值 算法1 因?yàn)?所以 5 5 5 5 5 5 3125 625 125 25 5 3906 算法2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 分析 兩種算法中各用了幾次乘法運(yùn)算 和幾次加法運(yùn)算 數(shù)書(shū)九章 秦九韶算法 對(duì)該多項(xiàng)式按下面的方式進(jìn)行改寫(xiě) 思考 當(dāng)知道了x的值后該如何求多項(xiàng)式的值 這是怎樣的一種改寫(xiě)方式 最后的結(jié)果是什么 要求多項(xiàng)式的值 應(yīng)該先算最內(nèi)層的一次多項(xiàng)式的值 即 然后 由內(nèi)到外逐層計(jì)算一次多項(xiàng)式的值 即 最后的一項(xiàng)是什么 這種將求一個(gè)n次多項(xiàng)式f x 的值轉(zhuǎn)化成求n個(gè)一次多項(xiàng)式的值的方法 稱(chēng)為秦九韶算法 思考 在求多項(xiàng)式的值上 這是怎樣的一個(gè)轉(zhuǎn)化 例2已知一個(gè)五次多項(xiàng)式為 用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x 5的值 解 將多項(xiàng)式變形 按由里到外的順序 依此計(jì)算一次多項(xiàng)式當(dāng)x 5時(shí)的值 所以 當(dāng)x 5時(shí) 多項(xiàng)式的值等于17255 2 你從中看到了怎樣的規(guī)律 怎么用程序框圖來(lái)描述呢 開(kāi)始 輸入f x 的系數(shù) a0 a1 a2 a3 a4 a5 輸入x0 n 0 v a5 v v x0 a5 n n n 1 n 5 輸出v 結(jié)束 否 是 注意 要想使用檢驗(yàn)功能 請(qǐng)使用前 先要減低宏的安全限制 排序的算法 將下面數(shù)字按由小到大的順序排列 8 3 2 5 9 6 方法1 S1 比較第2個(gè)數(shù)與第1個(gè)數(shù)的大小 并排序得3 8 S2 將第3個(gè)數(shù)與S1中的數(shù)比較 插入適當(dāng)?shù)奈恢?得到2 3 8 S3 將第4個(gè)數(shù)與S2中的數(shù)比較 并插入適當(dāng)?shù)奈恢?如此繼續(xù)下去 直到把最后一個(gè)數(shù)插入到上一步已排好的數(shù)列的合適位置為止 得到 2 3 5 8 2 3 5 8 9 2 3 5 6 8 9 S4 S5 排序的算法 將下面數(shù)字按由小到大的順序排列 8 3 2 5 9 6 方法1 過(guò)程演示 開(kāi)始 排第1次 排第2次 排第3次 排第4次 排第5次 排序的算法 將下面數(shù)字按由小到大的順序排列 8 3 2 5 9 6 方法2 S1 用第1個(gè)數(shù)與第2個(gè)數(shù)比較 若前者小則兩數(shù)不變 否則 交換這兩個(gè)數(shù)的位置 S2 按這樣的原則 比較第2個(gè)數(shù)和第3個(gè)數(shù) 前者小則兩數(shù)不變 否則 交換這兩個(gè)數(shù)的位置 直到比完最后兩個(gè)數(shù) 稱(chēng)為 一趟 S3 如果前一趟的比較中交換的次數(shù)為0 說(shuō)明排序已完成 否則回到S2 根據(jù)題意 一趟后的結(jié)果是什么 為什么說(shuō)前一趟的比較中交換為0次時(shí) 排序完成 3 2 5 8 6 9 排序的算法 將下面數(shù)字按由小到大的順序排列 8 3 2 5 9 6 請(qǐng)將每一趟的結(jié)果寫(xiě)出來(lái) 第1趟 該趟中交換的次數(shù)為 次 4 排序的算法 將下面數(shù)字按由小到大的順序排列 8 3 2 5 9 6 請(qǐng)將每一趟的結(jié)果寫(xiě)出來(lái) 第2趟 該趟中交換的次數(shù)為 次 2 排序的算法 將下面數(shù)字按由小到大的順序排列 8 3 2 5 9 6 請(qǐng)將每一趟的結(jié)果寫(xiě)出來(lái) 第3趟 該趟中交換的次數(shù)為 次 0 所以排序的結(jié)果為 2 3