高中数学第一章算法初步1.3算法案例课件新人教A版.ppt

1 3算法案例 自主预习 主题1 辗转相除法如何求4557和1953的最大公约数 1 注意到4557 1953 2 651 那么4557和1953的公约数和1953与651的公约数有什么关系 提示 显然4557与1953的最大公约数也是651的约数同样1953与651的公约数也是4557的约数 2 又1953 3 651 0 因此1953和651的最大公约数为651 由此可得出4557和1953的最大公约数是多少 提示 4557和1953的最大公约数为651 结合以上的探究总结对辗转相除法的认识辗转相除法的算法步骤第一步 给定两个 第二步 计算 第三步 第四步 则m n的最大公约数等于 否则 返回 正整数m n m除以n所得的余数r m n n r 若r 0 m 第二步 主题2 更相减损术1 设两个正整数m n 若m n k 则m与n的最大公约数和n与k的最大公约数相等吗 提示 相等 2 反复利用上述原理如何求396与216的最大公约数 提示 由396 216 180 216 180 36 180 36 144 144 36 108 108 36 72 72 36 36 故36是396与216的最大公约数 总结以上探究归纳对更相减损术的理解 更相减损术第一步 任意给定两个 判断它们是否都是 若是 若不是 执行 正整数 偶数 用2约简 第二步 第二步 以 减去 接着把所得的差与较小的数比较 并以 继续这个操作 直到 为止 则这个数 等数 或这个数与约简的数的 就是所求的最大公约数 较大的数 较小的数 大数减小数 所得的数相等 乘积 主题3 秦九韶算法1 如何计算多项式f x x5 x4 x3 x2 x 1当x 5时的值呢 统计所做的计算的种类及计算次数分别是什么 提示 f 5 55 54 53 52 5 1 3906 由计算统计可得出共需做10次乘法运算 5次加法运算 2 若将多项式变形为f x x 1 x 1 x 1 x 1 x 1统计计算x 5时的计算的种类及计算次数分别是什么 提示 从里往外计算仅需4次乘法和5次加法运算即可得出结果 总结以上探究归纳秦九韶算法 秦九韶算法的步骤把一个n次多项式f x anxn an 1xn 1 a1x a0改写成如下形式 f x anx an 1 x an 2 x a1 x a0 求多项式的值时 首先计算 即v1 然后 逐层计算一次多项式的值 即v2 v3 vn 这样 求n次多项式f x 的值就转化为求n个一次多项式的值 最内层括号内一次多项式 的值 anx an 1 由内向外 v1x an 2 v2x an 3 vn 1x a0 主题4 进位制1 常见的进位制有 二进制 七进制 十进制 十二进制 六十进制 它们的基数分别是什么 提示 它们的基数分别是 2 7 10 12 60 2 k进制数的组成数字有哪些 如果k 8 那么在八进制中 组成的数字有哪些 组成规律是什么 提示 k进制数组成的数字有0 1 2 k 1共k个数 在八进制中 基数是8 一共有0 1 2 3 4 5 6 7这八个不同的数字 组成规律是 满八进一 如 7 1 10 8 通过以上探究概括你对进位制的理解 1 进位制的概念及其表示 概念 人们为了计数和运算方便而约定的记数系统 满二进一 就是二进制 满十进一 就是十进制 满k进一 就是 k进制的基数是k 因此k进制需要使用 数字 k进制 k个 表示 一般地 若k是一个大于1的整数 那么以k为基数的k进制数可以表示为一串数字连写在一起的形式 an an 1 a1 a0 N 0 an k 0 an 1 a1 a0 k anan 1 a1a0 k 2 进位制之间的转化 k进制的数转化为十进制 若anan 1 a1a0 k 表示一个k进制的数 则转化为十进制数为 anan 1 a1a0 k an kn an 1 kn 1 a1 k a0 非十进制的k进制数a 共有n位 化为十进制数b的算法步骤 第一步 输入a k n的值 第二步 将b的值初始化为0 i的值初始化为1 第三步 b b aiki 1 i i 1 第四步 判断 是否成立 若是 则执行第五步 否则 返回第三步 i n 第五步 输出b的值 将十进制化为k进制 用 用k连续去除十进制数所得的商 直到商为零为止 然后将所得的余数 即为相应的k进制数 除k取余法 倒序写出 深度思考 1 结合教材P36例1 你认为更相减损术的一般步骤是什么 第一步 第二步 给定两个正整数m n 不妨设m n 若m n都是偶数 则不断用2约简 使它们不 同时是偶数 约简后的两个数仍记为m n 第三步 第四步 d m n 判断 d n 是否成立 若是 则将n d中的 较大者记为m 较小者记为n 返回第三步 否则 2kd k是约简整数2的个数 为所求的最大公约数 2 结合教材P38例2 你认为利用秦九韶算法求值的一般步骤是什么 设Pn x anxn an 1xn 1 a1x a0 将其改写为Pn x anxn 1 an 1xn 2 a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 第一步 第二步 第三步 第四步 第五步 输入多项式次数n 最高次项的系数an和x的值 将v的值初始化为an 将i的值初始化为n 1 输入i次项的系数ai v vx ai i i 1 判断i是否大于或等于0 若是 则返回第三步 否则 输出多项式的值v 预习小测 1 用更相减损术可求得78与36的最大公约数是 A 24B 18C 12D 6 解析 选D 先用2约简得39 18 然后辗转相减得39 18 21 21 18 3 18 3 15 15 3 12 12 3 9 9 3 6 6 3 3 所以所求的最大公约数为3 2 6 2 用辗转相除法求294和84的最大公约数时 需要做除法的次数是 A 1B 2C 3D 4 解析 选B 因为294 84 3 42 84 42 2 所以选B 3 以下各数中有可能是五进制数的是 A 55B 106C 732D 2134 解析 选D 在5进制数中 所组成的数字为0 1 2 3 4 因此A B C不可能是5进制数 4 用秦九韶算法求多项式f x x5 5x4 10 x3 10 x2 5x 1 当x 2时的值为 解析 f x x5 5x4 10 x3 10 x2 5x 1 x 5 x 10 x 10 x 5 x 1 而x 2 所以有v0 1 v1 v0 x a4 1 2 5 3 v2 v1x a3 3 2 10 4 v3 v2x a2 4 2 10 2 v4 v3x a1 2 2 5 1 v5 v4x a0 1 2 1 1 故f 2 1 答案 1 5 将十进制数30化为二进制数为 解析 故30 10 11110 2 答案 11110 2 6 用秦九韶算法计算多项式f x x6 12x5 60 x4 160 x3 240 x2 192x 64在x 2时的值 仿照教材P38例2解析过程 解析 先将多项式f x 进行改写 f x x6 12x5 60 x4 160 x3 240 x2 192x 64 x 12 x 60 x 160 x 240 x 192 x 64 然后由内向外计算得 v0 1 v1 v0 x a5 1 2 12 10 v2 v1x a4 10 2 60 40 v3 v2x a3 40 2 160 80 v4 v3x a2 80 2 240 80 v5 v4x a1 80 2 192 32 v6 v5x a0 32 2 64 0 所以当x 2时 多项式的值为0 互动探究 1 在用秦九韶算法计算n次项式在x x0时的值 至多需要进行几次乘法和加法运算 提示 n次乘法运算和n次加法运算 2 7进制中 数3521中的3 5 2 1各表示什么意思 提示 3表示3个73 5表示5个72 2表示2个7 1表示1个1 3 如何进行两个非十进制数之间的转换 提示 以十进制数作为桥梁 先将一个进制的数转化为十进制数 再将十进制数用除k取余法转化为另一进制的数 探究总结 知识归纳 注意事项 1 用更相减损术求两正整数的最大公约数时 若两数为偶数 可先约去2 这时莫忘记求得的相等两数乘以约简的数才是所求最大公约数 2 除k取余法的注意点 要连续除 用k连续去除十进制数及所得的商 直到商为零为止 倒着写 把各步得到的余数倒写 即从下到上排列 就是相应的k进制数 题型探究 类型一 辗转相除法与更相减损术 典例1 1 98 28这两个数的最大公约数为 A 17B 16C 14D 8 2 1037和425的最大公约数是 A 51B 17C 9D 3 解题指南 1 因两数较小 可采用辗转相除法 也可用更相减损术求解 2 两数相差较大 用辗转相除法求最大公约数 解析 1 选C 方法一 98 28 3 14 28 14 2 所以98与28的最大公约数为14 方法二 因为98 28 70 70 28 42 42 28 14 28 14 14 所以98与28的最大公约数是14 2 选B 因为1037 425 2 187 425 187 2 51 187 51 3 34 51 34 1 17 34 17 2 即1037和425的最大公约数是17 规律总结 辗转相除法和更相减损术求最大公约数的注意点 1 辗转相除法是当大数被小数除尽时 结束除法运算 较小的数就是最大公约数 2 更相减损术是当大数减去小数的差等于小数时停止减法 较小的数就是最大公约数 巩固训练 1 两个整数490和910的最大公约数是 A 2B 10C 30D 70 解析 选D 910 91 10 490 49 10 因为91 49 1 42 49 42 1 7 42 7 6 所以91与49的最大公约数为7 故910与490的最大公约数为70 2 求5280与12155的最大公约数 解析 12155 5280 2 1595 5280 1595 3 495 1595 495 3 110 495 110 4 55 110 55 2 故12155与5280的最大公约数为55 类型二 秦九韶算法 典例2 1 用秦九韶算法计算f x 6x5 4x4 x3 2x2 9x 需要加法与乘法的运算次数分别为 A 5 4B 5 5C 4 4D 4 5 2 用秦九韶算法计算当x 5时 多项式f x 2x4 6x3 5x2 4x 6的值时 v3的值等于 解题指南 1 利用秦九韶算法写出多项式f x 可知加法 乘法的次数 2 利用秦九韶算法由内到外依次计算即可得答案 解析 1 选D f x 6x 4 x 1 x 2 x 9 x 所以加法4次 乘法5次 2 将多项式化成如下形式f x 2x 6 x 5 x 4 x 6 由内向外计算 v0 2 v1 2 5 6 4 v2 4 5 5 15 v3 15 5 4 79 答案 79 延伸探究 1 改变问法 典例2 2 中条件不变 求f 5 解析 v0 2 v1 2 5 6 4 v2 5 4 5 15 v3 15 5 4 79 v4 79 5 6 389 即f 5 389 2 改变问法 典例2 2 中 求f 5 的过程中有多少次加法 乘法运算 解析 由f x 2x 6 x 5 x 4 x 6 所以有4次乘法运算 4次加法运算 规律总结 利用秦九韶算法计算多项式的值的策略 1 正确地将多项式改写 若在多项式中有几项不存在 可将这些项的系数看成0 即把这些项看成0 xn 2 由内向外逐次计算 3 每一步计算结果准确 由于下一次计算用到上一次计算的结果 应认真 细致地计算每一步 巩固训练 用秦九韶算法计算多项式f x 12 35x 8x2 11x3 6x4 5x5 3x6当x 4时的值时 v2的值为 解析 将f x 变形为f x 3x 5 x 6 x 11 x 8 x 35 x 12 所以v0 3 v1 3 4 5 7 v2 7 4 6 34 答案 34 类型三 进位制 典例3 1 2016 郑州高二检测 将五进制数444 5 化为四进制数应表示为 2 把87化为二进制数 应表示为 解题指南 1 先将五进制数444 5 转化为十进制 再化为四进制 2 利用除2取余法求解 解析 1 444 5 4 52 4 51 4 50 124 再将十进制数124化为四进制数 所以124 1330 4 所以444 5 1330 4 答案 1330 4 2 所以87 1010111 2 答案 1010111 2 规律总结 1 将k进制转化为十进制的方法技巧 1 先将这个k进制数写成各位上的数字与k的幂的乘积之和的形式 再按照十进制数的运算规则计算出结果 如 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 2 k的幂的最高次数是该k进制数的位数减去1 然后逐个减少1 最后是零次幂 我们称这种方法为方幂法 2 将十进制化为k进制的步骤 1 用k连续去除十进制数及所得的商 直到商为零为止 2 把各步得到的余数倒写就是相应的k进制数 巩固训练 1 1 把67化为二进制数为 A 1100001 2 B 1000011 2 C 110000 2 D 1000111 2 2 将八进制数3726 8 化成十进制数为 解题指南 1 利用除2取余法求解 2 利用八进制数中各个数字的含义求解 解析 1 选B 所以67 1000011 2 2 因为3726 8 3 83 7 82 2 8 6 2006 所以3726 8 2006 答案 2006 2 把五进制数1234 5 转化为十进制数 再把它转化为八进制数 解析 1234 5 1 53 2 52 3 51 4 50 194 10 因为所以1234 5 194 10 302 8