13算法案例教案1(完整版)
【正文】 b=b+t*k^(i1) a=a\10 t= a MOD 10 i=i+1 LOOP UNTIL in PRINT b END a 轉(zhuǎn)化為非十進(jìn)制的 k 進(jìn)制數(shù) b 的方法 (1)算法步驟 : 第一步 ,輸入 ka, 的值 . 第二步 ,求出 a 除以 k 所得的商 q ,余數(shù) r . 第三步 ,若 0?q ,則 qa? ,返回第二步 。而更 相 減損術(shù)進(jìn)行的是減法運算 ,即輾轉(zhuǎn)相減 ,但是實質(zhì)都是一個不斷的遞歸過程 . 例 2 請 用輾轉(zhuǎn)相除法和更相減損術(shù)求 1734 和 816 的最大公約數(shù) . 解： (1)輾轉(zhuǎn)相除法 第一步 , 10281621734 ??? 第二步 , 1028816 ?? 因此 ,102 是 1734 和 816 的最大公約數(shù) . (2)更相減損術(shù) 第一步 ,因為兩個數(shù)皆為偶數(shù) ,首先除以 2 得到 408,867 ,在求這兩個數(shù)的最大公約數(shù) 第二步 , 459408867 ?? , 51408459 ?? 第三步 , 35751408 ?? , 30651357 ?? 第四步 , 25551306 ?? , 20451255 ?? 第五步 , 15351204 ?? , 10251153 ?? 第六步 , 5151102 ?? 因此 , 102251 ?? 是 1734 和 816 的最大公約數(shù) . 例 3 用輾轉(zhuǎn)相除法和更相減損術(shù)求三個數(shù) 135,234,324 的最大公約數(shù) . 解： (1)輾轉(zhuǎn)相除法 812431324 ??? , 813243 ?? 則 324 與 243 的最大公約數(shù)為 81 又 54811135 ??? , 2754181 ??? , 27254 ?? 則 81與 135 的最大公約數(shù)為 27 因此 ,三個數(shù) 135,234,324 的最大公約數(shù)為 27 . (2)更相減損術(shù) 81243324 ?? , 16281243 ?? , 8181162 ?? 則 324 與 243 的最大公約數(shù)為 81 又 5481135 ?? , 275481 ?? , 272754 ?? 則 81與 135 的最大公約數(shù)為 27 因此 ,三個數(shù) 135,234,324 的最大公約數(shù)為 27 . 練習(xí) : 123 和 48 的最大公約數(shù) .(答案 :3 ) 80 和 36 的最大公約數(shù) .(答案 :4 ) 116,377,319 的最大公約數(shù) .(答案 :29 ) (二 )秦九韶算法 例 1 已知 n 次多項式 nnnnn axaxaxaxP ????? ?? 1110)( ?,如果 在一種算法 中 ,計算 ),4,3,2(0 nkx k ?? 的值需要 1?k 次乘法 ,計算 )( 03 xP 的值共需要 9 次運算(6 次乘法 3 次加法 ),那么計算 )( 010xP 的值需要 _________次運算 .下面給出一種減少運算次數(shù)的算法 : 00 )( axP ? , )1,2,1,0()()( 11 ???? ?? nkaxxPxP kkk ?.利用該算法 ,計算 )( 03 xP 的值共需要 6 次運算 ,計算 )( 010xP 的值共需要 _____次運算 . 答案 : 20,65 點評 : 秦九 韶 算法使用一般的多項式 0111)( axaxaxaxf nnnn ????? ?? ?的求值問題 .直接法乘法運算的次數(shù)最多可到達(dá) 2 )1( ?nn ,加法最多 n 次 .秦九 韶 算法通過轉(zhuǎn)化把乘法運算的次數(shù)減少到最多 n 次 ,加法最多 n 次 . 例 2 已知一個 5 次多項式為 )( 2345 ?????? xxxxxxf ,用秦九韶 算法求這個多項式當(dāng) 5?x 時的值 . 解 : 根據(jù)秦九 韶 算法 ,把多項式改寫成如下形式 : ))))25(((()( ?????? xxxxxxf 按照從內(nèi)到外的順序 ,一 次計算一次多項式當(dāng) 5?x 時的值 : 50?v , 272551 ????v , 3 ????v , 8 3 83 ????v , 4 5 8 94 ????v 7 2 5 4 5 15 ????v 所以 ,當(dāng) 5?x 時 ,多項式的值為 點評 : 如果多項式函 數(shù)中又缺項的畫 ,要以系數(shù)為 0 的項補齊后再計算 . 練習(xí) : 763452)( 2345 ?????? xxxxxxf ,求 )5(f . 2?x 時 ,用秦九 韶 算法求多項式 6125383)( 2345 ?????? xxxxxxf 的值 . 韶 算法求多項式 xxxxxxxxf ??????? 224567 234567)( 當(dāng)3?x 時的值 . 答案 : 。 例 3 某城市 2021 年末汽車保有量為 30 萬輛 ,預(yù)計此后每年報廢上一年末汽車保有量的 %6 ,并且每年新增 汽車 3 萬輛 .設(shè)計算法 ,計算經(jīng)過多少年可使汽車保有量達(dá)到 40 萬輛 .將此算法用程序 語言給出 . 解： 設(shè) %61 ???c ,經(jīng)過幾年的汽車保有量為 na ,則 300 ??ba 301 ?? caa 3)3(3 012 ????? ccaca
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1