高中数学 第一章 算法初步 1.3.1 辗转相除法与更相减损术、秦九韶算法课件 新人教A版必修3.ppt

1 3算法案例 第1课时辗转相除法与更相减损术 秦九韶算法 一 辗转相除法 问题思考 1 在小学时 我们利用找公约数的方法来求两个正整数的最大公约数 你能利用这种方法求出36与60的最大公约数是多少吗 提示首先用两个数公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来即为最大公约数 由于 2 如果两个正整数的公约数比较大 并且根据我们的观察又不能一下子得到它们的公约数 我们又该如何求出它们的最大公约数 比如 怎样求出8251与6105的最大公约数 观察等式8251 6105 1 2146 你发现8251与6105这两个数的公约数和6105与2146的公约数有什么关系 提示8251的最大约数是2146的约数 同样6105与2146的公约数也是8251的约数 故8251与6105的最大公约数也是6105与2146的最大公约数 3 又6105 2146 2 1813 同理 6105与2146的公约数和2146与1813的公约数相等 重复上述操作 你能得到8251与6105这两个数的最大公约数吗 提示8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 最后的除数37是148和37的最大公约数 也是8251与6105的最大公约数 4 填空 上述这种求两个正整数的最大公约数的方法就是辗转相除法 又叫欧几里得算法 是一种求两个正整数的最大公约数的古老而有效的算法 其算法步骤如下 第一步 给定两个正整数m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则 返回第二步 5 做一做1 求667与928的最大公约数 解 928 667 1 261 667 261 2 145 261 145 1 116 145 116 1 29 116 29 4 所以667与928的最大公约数是29 二 更相减损术 问题思考 1 设两个不都是偶数的正整数m n m n 若m n k 则m与n的最大公约数和n与k的最大公约数相等 反复利用这个原理 可求得98与63的最大公约数是多少 提示98 63 35 63 35 28 35 28 7 28 7 21 21 7 14 14 7 7 98与63的最大公约数为7 2 填空 上述求两个正整数的最大公约数的方法称为更相减损术 其算法步骤如下 第一步 任意给定两个正整数 判断它们是否都是偶数 若是 用2约简 若不是 执行第二步 第二步 以较大的数减去较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的差与减数相等为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 3 做一做2 342与589的最大公约数为 解析 589 342 247 342 247 95 247 95 152 152 95 57 95 57 38 57 38 19 38 19 19 所以342与589的最大公约数为19 答案 19 三 秦九韶算法 问题思考 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时f 5 的值 再统计一下这种计算求值的过程中乘法运算和加法运算的次数分别是多少 提示乘法运算4次 加法运算5次 3 填空 问题2中的算法比问题1中的算法少了6次乘法运算 大大简化了运算过程 问题2中的算法就叫秦九韶算法 一般地 f x anxn an 1xn 1 an 2xn 2 a1x a0 anxn 1 an 1xn 2 an 2xn 3 a1 x 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 然后由内向外逐层计算一次多项式的值 即v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 这样 求n次多项式f x 的值就转化为求n个一次多项式的值 4 做一做3 用秦九韶算法求f x 2x3 x 3 当x 3时的值v2 解析 f x 2x 0 x 1 x 3 v0 2 v1 2 3 0 6 v2 6 3 1 19 答案 19 思考辨析判断下列说法是否正确 正确的在后面的括号内打 错误的打 1 辗转相除法的基本步骤是用较大的数除以较小的数 2 用更相减损术求294和84的最大公约数时 需做减法的次数是3 3 用秦九韶算法计算f x 3x6 4x5 5x4 6x3 7x2 8x 1当x 0 4时的值 需要进行乘法运算和加法运算的次数均为6 4 利用秦九韶算法求f x 1 2x 3x2 4x3 5x4 6x5当x 2时的值时 先求6 2 5 第二步求2 6 2 5 4 答案 1 2 3 4 探究一 探究二 思维辨析 例1 求下列两数的最大公约数 1 228与2223 2 612与468 分析228与2223相差较大 用辗转相除法求最大公约数 612与468相差较小 用更相减损术求最大公约数 解 1 用辗转相除法求228与2223的最大公约数 2223 228 9 171 228 171 1 57 171 57 3 所以228和2223的最大公约数为57 探究一 探究二 思维辨析 2 首先612和468都是偶数 所以用2约简 得到306和234 还是偶数 需要再用2约简 得到153和117 最后用更相减损术计算 153 117 36 117 36 81 81 36 45 45 36 9 36 9 27 27 9 18 18 9 9 所以612和468的最大公约数是9 2 2 36 探究一 探究二 思维辨析 反思感悟1 利用辗转相除法求给定的两个数的最大公约数 即利用带余除法 用数对中较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的数对 再利用带余除法 直到大数被小数除尽 这时的较小数就是原来两个数的最大公约数 2 利用更相减损术求两个正整数的最大公约数时 首先判断两个正整数是否都是偶数 若是 用2约简 也可以不除以2 直接求最大公约数 这样不影响最后结果 3 当两个整数的差较大时 利用辗转相除法计算的次数较少 探究一 探究二 思维辨析 变式训练1分别用辗转相除法和更相减损术求779与209的最大公约数 解 辗转相除法 779 209 3 152 209 152 1 57 152 57 2 38 57 38 1 19 38 19 2 所以 779与209的最大公约数为19 探究一 探究二 思维辨析 更相减损术 779 209 570 570 209 361 361 209 152 209 152 57 152 57 95 95 57 38 57 38 19 38 19 19 所以779和209的最大公约数为19 探究一 探究二 思维辨析 例2 用秦九韶算法求多项式f x 7x7 6x6 4x4 3x3 2x2 x 5当x 3时的值 分析解答本题时首先要将原多项式化成f x 7x 6 x 0 x 4 x 3 x 2 x 1 x 5的形式 然后弄清v0 v1 v2 v7分别是多少 最后进行计算 探究一 探究二 思维辨析 解 f x 7x 6 x 0 x 4 x 3 x 2 x 1 x 5 v0 7 v1 7 3 6 15 v2 15 3 0 45 v3 45 3 4 139 v4 139 3 3 420 v5 420 3 2 1258 v6 1258 3 1 3775 v7 3775 3 5 11320 当x 3时 多项式的值为11320 探究一 探究二 思维辨析 反思感悟利用秦九韶算法计算多项式的值的步骤 探究一 探究二 思维辨析 变式训练2用秦九韶算法求多项式f x 2x4 6x3 5x2 4x 6在x 5时的值 解 由于f x 2x4 6x3 5x2 4x 6 2x 6 x 5 x 4 x 6 根据秦九韶算法 我们有v0 2 v1 2x 6 2 5 6 4 v2 4x 5 4 5 5 15 v3 15x 4 15 5 4 79 v4 79x 6 79 5 6 389 探究一 探究二 思维辨析 用秦九韶算法求多项式的值时忽略空项而致误 典例 已知f x x5 x3 x2 x 1 用秦九韶算法求f 3 的值 错解因为f x x 1 x 1 x 1 x 1 所以当x 3时 v0 1 v1 3 1 4 v2 4 3 1 13 v3 13 3 1 40 v4 40 3 1 120 1 121 所以当x 3时 f 3 121 以上错解中都有哪些错误 出错的原因是什么 你如何订正 你如何防范 错因分析忽视了函数f x 中x4项的系数为0这一点 导致结果错误 探究一 探究二 思维辨析 正解原多项式可化为f x 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时 f 3 283 防范措施当多项式中间出现空项时 用秦九韶算法求函数值要补上系数为0的相应项 即把这些项看成是0 xn 探究一 探究二 思维辨析 变式训练用秦九韶算法求多项式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 1 v1 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时 f x x5 0 11x3 0 15x 0 04的值为 0 0796 1 2 3 4 1 用辗转相除法求56与264的最大公约数 需要做除法的次数是 a 3b 4c 5d 6解析 264 56 4 40 56 40 1 16 40 16 2 8 16 8 2 即最大公约数为8 做了4次除法 故选b 答案 b 1 2 3 4 2 用更相减损术求123和48的最大公约数是 a 3b 7c 9d 12解析 123 48 75 75 48 27 48 27 21 27 21 6 21 6 15 15 6 9 9 6 3 6 3 3 所以123和48的最大公约数是3 答案 a 1 2 3 4 3 用秦九韶算法求多项式f x 12 35x 8x2 79x3 6x4 5x5 3x6当x 4时的值 v4的值为 a 57b 220c 845d 3392解析 由秦九韶算法有v0 3 v1 v0 x