高中數學必修3同步練習與單元檢測第一章 算法初步 §1.3

§1.3　算法案例 課時目標　通過三種算法案例：輾轉相除法與更相減損術，秦九韶算法，進位制，進一步體會算法的思想，提高算法設計水平，體會中國古代數學對世界的貢獻． 1．輾轉相除法 (1)輾轉相除法，又叫歐幾里得算法，是一種求兩個正整數的最大公約數的古老而有效的算法． (2)輾轉相除法的算法步驟 第一步，給定兩個正整數m，n. 第二步，計算m除以n所得的余數r. 第三步，m＝n，n＝r. 第四步，若r＝0，則m、n的最大公約數等于m；否則，返回第二步． 2．更相減損術 第一步，任意給定兩個正整數，判斷它們是否都是偶數．若是，用2約簡；若不是，執(zhí)行第二步． 第二步，以較大的數減去較小的數，接著把所得的差與較小的數比較，并以大數減小數，繼續(xù)這個操作，直到所得的數相等為止，則這個數(等數)或這個數與約簡的數的乘積就是所求的最大公約數． 3．秦九韶算法 把一個n次多項式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改寫成如下形式： (…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0， 求多項式的值時，首先計算最內層括號內一次多項式的值，即v1＝anx＋an－1，然后由內向外逐層計算一次多項式的值，即 v2＝v1x＋an－2， v3＝v2x＋an－3， … vn＝vn－1x＋a0 這樣，求n次多項式f(x)的值就轉化為求n個一次多項式的值． 4．進位制 進位制是人們?yōu)榱擞嫈岛瓦\算方便而約定的記數系統(tǒng)，“滿k進一”就是k進制，k進制的基數是k. 把十進制轉化為k進制數時，通常用除k取余法． 一、選擇題 1．下列說法中正確的個數為(　　) (1)輾轉相除法也叫歐幾里得算法； (2)輾轉相除法的基本步驟是用較大的數除以較小的數； (3)求最大公約數的方法，除輾轉相除法之外，沒有其他方法； (4)編寫輾轉相除法的程序時，要用到循環(huán)語句． A．1 B．2 C．3 D．4 答案　C 解析　(1)、(2)、(4)正確，(3)錯誤． 2．用更相減損術求294和84的最大公約數時，需做減法的次數是(　　) A．2 B．3 C．4 D．5 答案　C 解析　由于294和84都是偶數， 所以用2約簡： 294÷2＝147， 84÷2＝42， 又由于147不是偶數， 所以147－42＝105， 105－42＝63， 63－42＝21， 42－21＝21， 故需做4次減法，故選C. 3．1 037和425的最大公約數是(　　) A．51 B．17 C．9 D．3 答案　B 解析　∵1 037＝425×2＋187， 425＝187×2＋51， 187＝51×3＋34， 51＝34×1＋17， 34＝17×2， 即1 037和425的最大公約數是17. 4．用秦九韶算法計算多項式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4時的值時，需做加法和乘法的次數的和為(　　) A．10 B．9 C．12 D．8 答案　C 解析　f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x＋7 ∴加法6次，乘法6次， ∴6＋6＝12(次)，故選C. 5．已知f(x)＝x5＋2x3＋3x2＋x＋1，應用秦九韶算法計算x＝3時的值時，v3的值為(　　) A．27 B．11 C．109 D．36 答案　D 解析　將函數式化成如下形式． f(x)＝(((x＋0)x＋2)x＋3)x＋1)x＋1 由內向外依次計算： v0＝1， v1＝1×3＋0＝3， v2＝3×3＋2＝11， v3＝11×3＋3＝36， v4＝36×3＋1＝109， v5＝109×3＋1＝328. 6．下列有可能是4進制數的是(　　) A．5 123 B．6 542 C．3 103 D．4 312 答案　C 解析　4進制數每位上的數字一定小于4，故選C. 二、填空題 7．輾轉相除法程序中有一空請?zhí)钌希? 答案　a MOD b 解析　MOD用來表示a除以b的余數． 8．更相減損術程序中有兩空請?zhí)钌希? 答案　a＝b　b＝r 9．已知三個數12(16)，25(7)，33(4)，將它們按由小到大的順序排列為________． 答案　33(4)<12(16)<25(7) 解析　將三個數都化為十進制數． 12(16)＝1×16＋2＝18， 25(7)＝2×7＋5＝19， 33(4)＝3×4＋3＝15， ∴33(4)<12(16)<25(7)． 三、解答題 10．用兩種方法求210與98的最大公約數． 解　用輾轉相除法： 210＝98×2＋14， 98＝14×7. ∴210與98的最大公約數為14. 用更相減損術： ∵210與98都是偶數，用2約簡得 105和49， 105－49＝56,56－49＝7， 49－7＝42,42－7＝35， 35－7＝28,28－7＝21， 21－7＝14,14－7＝7. ∴210與98的最大公約數為2×7＝14. 11．用秦九韶算法計算多項式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64當x＝2時的值． 解　將f(x)改寫為 f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64 由內向外依次計算一次多項式當x＝2時的值 v0＝1， v1＝1×2－12＝－10， v2＝－10×2＋60＝40， v3＝40×2－160＝－80， v4＝－80×2＋240＝80， v5＝80×2－192＝－32， v6＝－32×2＋64＝0. ∴f(2)＝0，即x＝2時，原多項式的值為0. 能力提升 12．把111化為五進制數． 解　 ∴111化為五進制數為421(5)． 13．把10 231(5)化為四進制數． 解　先化成十進制數． 10 231(5)＝1×54＋0×53＋2×52＋3×51＋1 ＝625＋50＋15＋1 ＝691 再化為四進制數 ∴10 231(5)＝22 303(4). 1．輾轉相除法與更相減損術的區(qū)別和聯系 (1)都是求最大公約數的方法． (2)二者的實質都是遞歸的過程． (3)二者都要用循環(huán)結構來實現． 2．秦九韶算法的特點 秦九韶算法的特點在于把求一個n次多項式的值轉化為求n個一次多項式的值，即把求f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值轉化為求遞推公式： 這樣可以最多計算n次乘法和n次加法即可得多項式的值，和直接代入多項式相比減少了乘法的運算次數，提高了運算效率． 3．十進制與其他進制的轉化 (1)將k進制轉化為十進制的方法：先把k進制數寫成各位上的數字與k的冪的乘積的形 式，再按十進制的運算規(guī)則計算． (2)將十進制化成k進制的方法：用除k取余法，用k連續(xù)去除十進制數所得的商，直到商為零為止，然后將各步所得的余數倒序寫出，即為相應的k進制數．