第一章 算法初步 §1.3

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 60 x4 160 x3 240 x2 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的值转化为求递推公式 Error 这样可以最多计算 n 次乘法和 n 次加法即可得多项式的值 和直接代入多项式相比减 少了乘法的运算次数 提高了运算效率 3