高中数学（人教版a版必修三）配套课时作业：第一章 算法初步 §1.3 算法案例 5页

§1.3 算法案例 课时目标 通过三种算法案例：辗转相除法与更相减损术，秦九韶算法，进位制，进一 步体会算法的思想，提高算法设计水平，体会中国古代数学对世界的贡献． 1．辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的 算法． (2)辗转相除法的算法步骤 第一步，给定两个正整数 m，n. 第二步，计算 m 除以 n 所得的余数 r. 第三步，m＝n，n＝r. 第四步，若 r＝0，则 m、n 的最大公约数等于 m；否则，返回第二步． 2．更相减损术 第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用 2 约简；若不是，执 行第二步． 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数， 继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是 所求的最大公约数． 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．进位制 进位制是人们为了计数和运算方便而约定的记数系统，“满 k 进一”就是 k 进制，k 进制 的基数是 k. 把十进制转化为 k 进制数时，通常用除 k 取余法． 一、选择题 1．下列说法中正确的个数为( ) (1)辗转相除法也叫欧几里得算法； (2)辗转相除法的基本步骤是用较大的数除以较小的数； (3)求最大公约数的方法，除辗转相除法之外，没有其他方法； (4)编写辗转相除法的程序时，要用到循环语句． 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．辗转相除法程序中有一空请填上． INPUT “a，b＝”；a，b DO r＝ a＝b b＝r LOOP UNTIL r＝0 PRINT a END 答案 a MOD b 解析 MOD 用来表示 a 除以 b 的余数． 8．更相减损术程序中有两空请填上． INPUT a，b WHILE a<>b r＝a－b IF b>r THEN ELSE a＝r END IF WEND PRINT b END 答案 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．辗转相除法与更相减损术的区别和联系 (1)都是求最大公约数的方法． (2)二者的实质都是递归的过程． (3)二者都要用循环结构来实现． 2．秦九韶算法的特点 秦九韶算法的特点在于把求一个 n 次多项式的值转化为求 n 个一次多项式的值，即把求 f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0 的值转化为求递推公式：v0＝an vk＝vk－1x＋an－kk＝1，2，…，n这样可以最多计算 n 次乘法和 n 次加法即可得多项式的值，和直接代入多项式相比减少 了乘法的运算次数，提高了运算效率． 3．十进制与其他进制的转化 (1)将 k 进制转化为十进制的方法：先把 k 进制数写成各位上的数字与 k 的幂的乘积的形 式，再按十进制的运算规则计算． (2)将十进制化成 k 进制的方法：用除 k 取余法，用 k 连续去除十进制数所得的商，直到 商为零为止，然后将各步所得的余数倒序写出，即为相应的 k 进制数．