高中数学 第1部分 第一章 1.3 算法案例课件 新人教A版必修3.ppt

1 3算法案例 理解教材新知 把握热点考向 应用创新演练 第一章算法初步 知识点一 知识点二 考点一 考点二 考点三 知识点三 问题1 如何求18与54的最大公约数 提示 短除法问题2 要求6750与3492的最大公约数 上述法还好用吗 提示 数值太大 短除法不方便用问题3 还有没有其他方法 可用来解决问题2中的问题 提示 有 1 辗转相除法 1 辗转相除法 又叫欧几里得算法 是一种求两个正整数的的古老而有效的算法 2 辗转相除法的算法步骤第一步 给定 第二步 计算 第三步 最大公约数 两个正整数m n m除以n所得的余数r m n n r 第四步 若r 0 则m n的最大公约数等于 否则返回 2 更相减损术 1 更相减损术是我国古代数学专著 九章算术 中介绍的一种求的算法 m 第二步 两个正整数的最大公约数 2 其基本过程是 第一步 任意给定两个正整数 判断它们是否都是 若是 若不是 执行 第二步 以的数减去的数 接着把所得的差与的数比较 并以大数减小数 继续这个操作 直到所得的数为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 偶数 第二步 较小 相等 用2约简 较小 较大 已知多项或f x x5 3x4 3x3 4x2 x 1问题1 求f 1 提示 f 1 1 3 3 4 1 1 3问题2 若求f 39 再代入运算出现什么情况 提示 运算量太大 不易运算问题3 有没有好的方法求x数值较大时对应的函数值 提示 有 可将f x 转化为求一次多项式的值 秦九韶算法 一元n次多项式 anxn 1 an 1xn 2 a1 x a0 anx an 1 x an 2 x a1 x a0 v2x an 3 vn 1x a0 n个一次多 项式 我们从小到现在 学习的数都是十进制 而现代的电子计算机技术全部采用的是二进制 因为它只使用0 1两个数字符号 非常简单方便 问题1 除了十进制与二进制外还有其他进位制 能举例说明吗 提示 如六进制 八进制等问题2 其他进制与十进制可以互化吗 提示 可以 进位制是人们为了和而约定的记数系统 满k进一 就是 k进制的基数是k 把十进制数化为k进制数时 通常用除k取余法 计数 运算方便 k进制 1 辗转相除法与更相减损术的区别与联系 3 不同进位制的数照样可比较大小 但一般要转化到同一进位制下比较大小 例1 求228与1995的最大公约数 思路点拨 可以考虑用辗转相除法 也可考虑用更相减损术 精解详析 法一 辗转相除法 1995 8 228 171 228 1 171 57 171 3 57 所以228与1995的最大公约数为57 法二 更相减损术 1995 228 1767 1767 228 1539 1539 228 1311 1311 228 1083 1083 228 855 855 228 627 627 228 399 399 228 171 228 171 57 171 57 114 114 57 57 所以228与1995的最大公约数为57 一点通 辗转相除法计算次数少 步骤简捷 更相减损术计算次数多 步骤复杂 但是更相减损术每一步的计算都是减法 比做除法运算要简单一些 一般当数较小时可以考虑用更相减损术 当数较大时可以考虑用辗转相除法 1 用辗转相除法求72与120的最大公约数时 需要做除法次数为 a 4b 3c 5d 6解析 用辗转相除法 120 72 1 48 72 48 1 24 48 24 2 答案 b 2 用更相减损术求1515与600的最大公约数时 需要做减法的次数是 a 15b 14c 13d 12 解析 1515 600 915 915 600 315 600 315 285 315 285 30 285 30 255 255 30 225 225 30 195 195 30 165 165 30 135 135 30 105 105 30 75 75 30 45 45 30 15 30 15 15 1515与600的最大公约数是15 则共做14次减法 答案 b 3 求324 243 270三个数的最大公约数 解 324 243 1 81 243 81 3 所以324与243的最大公约数为81 270 81 3 27 81 27 3 所以81与270的最大公约数为27 综上可知 324 243 270三个数的最大公约数为27 精解详析 将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 一点通 秦九韶算法的步骤 4 用秦九韶算法求多项式f x 12 35x 8x2 79x3 6x4 5x5 3x6在x 4的值时 v4的值为 a 57b 220c 845d 3392解析 由秦九韶算法有 v0 3 v1 v0 x 5 7 v2 7x 6 34 v3 34x 79 57 v4 57x 8 220 答案 b 5 用秦九韶算法求多项式f x x5 0 11x3 0 15x 0 04当x 0 3时的值 解 根据秦九韶算法 将f x 写为 f x x 0 x 0 11 x 0 x 0 15 x 0 04 按照从内到外的顺序 依次计算一次多项式当x 0 3时的值 v0 1v1 v0 0 3 0 0 3 v2 v1 0 3 0 11 0 2 v3 v2 0 3 0 0 06 v4 v3 0 3 0 15 0 132 v5 v4 0 3 0 04 0 0796 所以 当x 0 3时 多项式的值为 0 0796 例3 1 将101111011 2 转化为十进制的数 2 将235 7 转化为十进制的数 3 将137 10 转化为六进制的数 4 将53 8 转化为二进制的数 思路点拨 其他进制化十进制时 利用求各位上的数与k的幂的乘积后再相加的方法 十进制化其他进制可采用除k取余法 精解详析 1 101111011 2 1 28 0 27 1 26 1 25 1 24 1 23 0 22 1 21 1 20 379 10 2 235 7 2 72 3 71 5 70 124 10 3 137 10 345 6 4 53 8 5 81 3 80 43 10 53 8 101011 2 一点通 1 k进制数化为十进制数的步骤 1 把k进制数写成不同数位上的数字与k的幂的乘积之和的形式 2 按十进制数的运算规则运算出结果 2 十进制数化为k进制数 除k取余法 的步骤 6 二进制数101110 2 转化为八进制数为 a 45 8 b 56 8 c 67 8 d 78 8 解析 先化成十进制 再化成八进制101110 2 1 25 0 24 1 23 1 22 1 2 0 46 46 56 8 答案 b 7 下列所给的四个数中 最小的是 a 3732 8 b 5555 7 c 2011d 133210 4 解析 将各项都化成十进制数再比较大小 3732 8 3 83 7 82 3 8 2 2010 5555 7 5 73 5 72 5 7 5 2000 133210 4 1 45 3 44 3 43 2 42 1 4 0 2020 答案 b 1 求两个正整数的最大公约数的问题 可以用辗转相除法 也可以用更相减损术 用辗转相除法 即根据a nb r这个式子 反复相除 直到r 0为止 用更相减损术 即根据r a b 这个式子 反复相减 直到r 0为止 2 秦九韶算法的关键在于把n次多项