高中数学 1.3 算法案例配套课件 新人教A版必修3.ppt

1 3算法案例 学习目标 1 理解辗转相除法与更相减损术求最大公约数的方法 2 理解秦九韶算法中求多项式的值的步骤原理 3 能利用除k取余法把十进制数化为k进制数 1 辗转相除法的算法步骤第一步 给定两个正整数m n m n 第二步 计算 除以 所得的 数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于 否 则 返回第二步 m n 余 n 2 更相减损术的算法步骤第一步 任意给定两个正整数 判断它们是否都是偶数 若是用2约简 若不是 执行第二步 第二步 以较大的数减去较小的数 接着把所得的差与 比较 并以大数减小数 继续这个操作 直到所得的数 为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 较小的数 相等 3 秦九韶算法把一个n次多项式f x anxn an 1xn 1 a1x a0改写 成如下形式 anxn 1 an 1xn 2 a1 x a0 f x anxn an 1xn 1 a1x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 求多项式的值时 首先计算最内层括号内的一次多项式的值 即v1 anx an 1 然后由内向外逐层计算一次多项式的值 即 n 这样 求n次多项式f x 的值就转化为求 个一次多项式的值 v1 anx an 1 v2 v3 v2x an 3 vn v1x an 2 vn 1x a0 4 进位制 1 k进制数anan 1 a1a0 k 转化为十进制数为 2 把十进制数化为k进制数用 即把所给的十进制数除以 得到商数和余数 再用商数除以k 得到商数和余数 直到商数为 把上面各步所得的 从右到左排列 即得到k进制数 除k取余法 k 0 余数 ankn an 1kn 1 a1k a0 问题探究 用秦九韶算法求多项式的值有什么优点 答案 减少了做乘法运算的次数 优化了求多项式的值的 算法 题型1最大公约数的求法 例1 用辗转相除法求下面两数的最大公约数 并用更相减损术检验你的结果 1 80 36 2 294 84 思维突破 辗转相除法的结束条件是余数为0 更相减损术的结束条件是差与减数相等 解 1 80 36 2 8 36 8 4 4 8 4 2 0 即80与36的最大公约数是4 验证 80 36 44 44 36 8 36 8 28 28 8 20 20 8 12 12 8 4 8 4 4 80与36的最大公约数是4 2 294 84 3 42 84 42 2 即294与84的最大公约数是42 验证 294与84都是偶数可同时除以2 即取147与42 的最大公约数后再乘2 147 42 105 105 42 63 63 42 21 42 21 21 294与84的最大公约数为21 2 42 辗转相除法求最大公约数的步骤较少 而更相减 损术运算简易 因此解题时要灵活运用 变式与拓展 1 试用算法程序表示用辗转相除法求144与60的最大公约 数的算法 解 程序如下 m 144n 60 do r mmodnm nn r loopuntilr 0 printmend 题型2秦九韶算法的应用 例2 当x 3时 求多项式f x x5 x3 x2 x 1的 值 解 根据秦九韶算法 把多项式改写成如下形式 f x x5 0 x4 x3 x2 x 1 x 0 x 1 x 1 x 1 x 1 按照从内到外的顺序 依次计算一次多项式当x 3时的 值 v0 1 v1 1 3 0 3 v2 3 3 1 10 v3 10 3 1 31 v4 31 3 1 94 v5 94 3 1 283 所以当x 3时 多项式的值为283 当多项式函数的中间出现空项时 应先补上系数为0的相应项 解题时关键是能正确地改写多项式 然后由内向外逐项计算 由于后项计算用到前项的结果 故要认真确保每一项计算的准确性 变式与拓展 2 利用秦九韶算法计算多项式f x 11 5x 3x2 7x3在 x 23的值时 不会用到下列哪个值 d a 161 b 3772 c 86641 d 85169 解析 f x 11 5x 3x2 7x3 7x 3 x 5 x 11 所以当x 23时 v0 7 v1 7 23 3 161 3 164 v2 164 23 5 3772 5 3767 v3 3767 23 11 86641 11 86652 题型3进制数之间的转化 例3 1 将101111011 2 转化为十进制数 2 将1231 5 转化为七进制数 思维突破 k进制数anan 1 a2a1a0 k 0 ai k 转化为十进制数 anan 1 a2a1a0 k an kn an 1 kn 1 a2 k2 a1 k a0 1 要将k进制数转化为n进制数 n k 10 可先将k进制数转化为十进制数 然后再转化为所求的n进制数 解 1 101111011 2 1 28 0 27 1 26 1 25 1 24 1 23 0 22 1 21 1 20 379 10 2 1231 5 1 53 2 52 3 5 1 191 10 1231 5 362 7 变式与拓展 3 填空 248 130 1 11111000 2 10 2 154 6 7 例4 已知f x x5 2x4 3x3 4x2 5x 6 用秦九韶算法求这个多项式当x 2时的值时 做了几次乘法运算 几次加法运算 解 共做了5次乘法运算 5次加法运算 易错分析 用秦九韶算法计算多项式f x anxn an 1xn 1 a1x a0 当x x0时 首先将多项式改写成f x anx an 1 x an 2 x a1 x a0形式 然后再计算v1 anx an 1 v2 v1x an 2 vn vn 1x a0 因此 尽管an是1 但仍进行了5次乘法 方法 规律 小结 1 辗转相除法与更相减损术求最大公约数的区别与联系 2 秦九韶算法的优点 1 减少乘法运算的次数 2 规律性强 便于利用循环语句实现 3 不用对x做幂的运算 每次都是计算一个一次多项式的 值 提高了计算精度 3 进位制的理解 进位制是一种记数方式 用有限的数字在不同的位置表示不同的数值 使用数字符号的个数称为基数 基数为n 即称为n进位制 简称n进制 现在最常用的是十进制 通常使用10个阿拉伯数字0 9进行记数 对于任何一个数 我们可以用