高中数学 1.3.1 辗转相除法与更相减损术、秦九韶算法课件2 新人教A版必修3.pptVIP

第1课时辗转相除法与更相减损术 秦九韶算法 1 理解三种算法的原理及应用 2 了解三种算法的框图的表示及程序 3 会用秦九韶算法求多项式的值 1 本节重点是三种算法的原理及应用和用秦九韶算法求多项式的值 2 本节难点是三种算法的应用和三种算法的框图的表示及程序 1 辗转相除法 1 概念 辗转相除法是用于求两个正整数 的一种算法 这种算法是由欧几里得在公元前300年左右首先提出的 因而又叫 最大公约数 欧几里得算法 2 程序 mmodn 2 更相减损术 1 相应概念及基本过程更相减损术是我国古代数学专著 中介绍的一种求两个正整数最大公约数的方法 2 运算过程第一步 任意给定两个正整数 判断它们是否都是偶数 若是 若不是 执行第二步 九章算术 用2约简 第二步 以较大的数减去较小的数 接着把所得的差与 比较 并以大数减小数 继续这个操作 直到所得的数 为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 较小的 数 相等 3 程序 r r a b 3 秦九韶算法 1 算法原理 把一个n次多项式f x anxn an 1xn 1 a1x a0改写成如下形式 f x anxn an 1xn 1 a1x a0 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 求多项式的值时 首先计算最内层括号内一次多项式的值 即v1 anx an 1 然后由内向外逐层计算一次多项式的值 即v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 这样 求n次多项式f x 的值就转化为求n个一次多项式的值 2 程序如下 v x0 a n i 1 实际应用更相减损术时要做的第一步工作是什么 提示 先判断a b是否为偶数 若是都除以2再进行 2 当所给的多项式按x的降幂排列 缺项 时 用秦九韶算法改写多项式时 应注意什么 提示 所缺的项写成系数为零的形式 即写成0 xn的形式 3 25与35的最大公约数为 解析 35 1 25 10 25 2 10 5 10 2 5 所以25与35的最大公约数为5 答案 5 4 用秦九韶算法计算多项式f x 3x6 4x5 5x4 6x3 7x2 8x 1 当x 0 4时 需要做乘法的次数是 解析 多项式变形为f x 3x6 4x5 5x4 6x3 7x2 8x 1 3x 4 x 5 x 6 x 7 x 8 x 1 其中乘法的次数为6 答案 6 1 比较辗转相除法与更相减损术的区别 1 都是求两个正整数最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0而得到 而更相减损术则以减数与差相等而得到 2 用秦九韶算法的注意点在计算vk k 0 1 2 n 时 逐级迭代提高了计算的速度 计算要准确 任何一步的失误 都会导致结果的错误 辗转相除法及其应用 技法点拨 辗转相除法 欧几里得算法 1 算理 所谓辗转相除法 就是对于给定的两个正整数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽 则这时较小的数就是原来两个数的最大公约数 2 算法步骤第一步 输入两个正整数m n m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则 返回第二步 第五步 输出最大公约数m 典例训练 1 378与90的最大公约数为 2 用辗转相除法求225和135的最大公约数 解析 1 辗转相除法 378 90 4 18 90 18 5 0 所以378与90的最大公约数是18 答案 18 2 225 135 1 90 135 90 1 45 90 45 2 所以45是225和135的最大公约数 想一想 为何辗转相除法总能求出最大公约数 提示 由除法的性质可以知道 对于任意两个正整数 上述除法步骤总可以在有限步之后完成 从而总可以用辗转相除法求出两个正整数的最大公约数 变式训练 用辗转相除法求123和48的最大公约数 解析 辗转相除法求最大公约数的过程如下 123 2 48 27 48 1 27 21 27 1 21 6 21 3 6 3 6 2 3 0 所以123和48的最大公约数为3 更相减损术及其应用 技法点拨 更相减损术的求解步骤第一步 给定两个正整数m n m n且m n不全是偶数 第二步 计算m n所得的差k 第三步 比较n与k的大小 其中大者用m表示 小者用n表示 第四步 若m n 则m n的最大公约数等于m 否则 返回第二步 典例训练 1 用更相减损术求294与84的最大公约数时 需做减法的次数是 2 用更相减损术求104与65的最大公约数 解析 1 294与84是偶数 首先除以2得到147 42 再求147与42的最大公约数147 42 105 105 42 63 63 42 21 42 21 21 共做了4次减法 答案 4 2 由于65不是偶数 把104和65以大数减小数 并辗转相减 即104 65 39 65 39 26 39 26 13 26 13 13 所以104和65的最大公约数为13 互动探究 本题2条件不变 如何用辗转相除法求解 解析 第一步 104 65 1 65 39第二步 65 1 39 26第三步 39 1 26 13第四步 26 2 13 0所以104和65的最大公约数为13 思考 更相减损术与辗转相除法比较有何运算特点 应用更相减损术的易错点是什么 提示 1 尽管两种算法分别来源于东 西方古代数学名著 但是二者的算理却是相似的 有异曲同工之妙 主要区别在于辗转相除法进行的是除法运算 即辗转相除 而更相减损术进行的是减法运算 即辗转相减 但是实质都是一个不断的递归过程 2 应用更相减损术要注意的是差和较小的数比较 然后再相减 变式训练 用更相减损术求1734 816的最大公约数 解析 因为两数皆为偶数 首先除以2得到867 408 再求867与408的最大公约数 867 408 459 459 408 51 408 51 357 357 51 306 306 51 255 255 51 204 204 51 153 153 51 102 102 51 51 所以1734与816的最大公约数是51 2 102 秦九韶算法及其应用 技法点拨 算法步骤第一步 输入多项式次数n 最高次项的系数an和x的值 第二步 将v的值初始化为an 将i的值初始化为n 1 第三步 输入i次项的系数ai 第四步 v vx ai i i 1 第五步 判断i是否大于或等于0 若是 则返回第三步 否则 输出多项式的值v 典例训练 1 已知f x x5 2x3 3x2 x 1 应用秦九韶算法计算当x 3时 v3的值为 a 27 b 11 c 109 d 362 2012 福州高一检测 用秦九韶算法写出当x 3时f x 2x5 4x3 3x2 5x 1的值 解析 1 选b 将多项式改写成如下形式 f x x 0 x 2 x 3 x 1 x 1 由内向外依次计算 v0 1 v1 1 3 0 3 v2 3 3 2 11 2 f x 2x 0 x 4 x 3 x 5 x 1 v0 2 v1 2 3 0 6 v2 6 3 4 14 v3 14 3 3 45 v4 45 3 5 130 v5 130 3 1 391 所以f 3 391 思考 怎样用程序框图表示秦九韶算法 用秦九韶算法解题的关键是什么 提示 1 程序框图 2 应用秦九韶算法解题的关键是把多项式转化成n个一次多项式 三个数的最大公约数 技法点拨 三个数的最大公约数的求解方法先从三个数中任取两个数 用辗转相除法或更相减损术求它们的最大公约数 然后再根据辗转相除法或更相减损术求所求得的最大公约数和第三个数的最大公约数 最后求得的最大公约数即为这三个数的最大公约数 典例训练 1 168 56 224的最大公约数是 2 用辗转相除法或者更相减损术求三个数324 243 135的最大公约数 解析 1 168 56 3 168 56的最大公约数是56 224 56 4 故56 224的最大公约数为56 三个数168 56 224的最大公约数是56 答案 56 2 辗转相除法 324 243 1 81 243 81 3 0 则324与243的最大公约数为81 又135 81 1 54 81 54 1 27 54 27 2 0 则81与135的最大公约数为27 所以三个数324 243 135的最大公约数为27 更相减损术 324 243 81 243 81 162 162 81 81 则324与243的最大公约数为81 135 81 54 81 54 27 54 27 27 则81与135的最大公约数为27 所以三个数324 243 135的最大公约数为27 易错误区 利用秦九韶算法求值的易错点 典例 利用秦九韶算法求多项式f x x6 5x5 6x4 x2 3x 2当x 2时的值 a 320 b 160 c 320 d 300 解题指导 解析 选a 将多项式变形为f x x 5 x 6 x 0 x 1 x 3 x 2 v0 1 v1 2 5 7 v2 7 2 6 20 v3 20 2 0 40 v4 40 2 1 81 v5 81 2 3 159 v6 159 2 2 320 所以多项式当x 2时的值是320 阅卷人点拨 通过阅卷后分析 对解答本题的常见错误及解题启示总结如下 即时训练 已知多项式f x 3x5 8x4 3x3 5x2 12x 6 则f 2 解析 根据秦九韶算法 把多项式改写成如下形式 f x 3x 8 x 3 x 5 x 12 x 6 按照从内到外的顺序 依次计算一次多项式当x 2时的值 v0 3 v1 3 2 8 14 v2 14 2 3 25 v3 25 2 5 55 v4 55 2 12 122 v5 122 2 6 238 所以当x 2时 多项式的值为238 答案 238 1 更相减损术可解决下列问题中的 a 求两个正整数的最大公约数 b 求多项式的值 c 进位制的转化计算 d 排序问题 解析 选a 更相减损术是解决求两个或两个以上的正整数的最大公约数的 2 用秦九韶算法求多项式f x 4x5 3x4 6x 9 当x 3时的值时 需要乘法运算和加法运算的次数为 a 4 2 b 5 3 c 5 5 d 5 4 解析 选b f x 4x5 3x4 6x 9 4x 3 x x x 6 x 9 3 求两个正整数840与1785的最大公约数 解析 1785 840 2 105 840 105 8 所以105为840与1785的最大公约数 答案 105 4 已知函数f x x3 2x2 5x 8 利用秦九韶算法求f