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

1 3算法案例第1课时辗转相除法与更相减损术 秦九韶算法 回顾算法的三种表述 自然语言程序框图 三种逻辑结构 程序语言 五种基本语句 希腊人常以线段代数 甲乙两数可以看成长度分别为甲乙两数的直尺拿短尺去量长尺 若有剩余 再用剩余部分为尺 去量原来的短尺 如此继续下去 如果两尺长度之比为有理数 经过辗转相量 在有限次内 总会有量尽的时候 若最后量尽时所用的尺回头分别来量原来的两把尺 也会量尽的 希腊人就说这两把尺 两个线段 两个数 是可共度的 这就是辗转相除法 希腊人以为任何两段都是可共度的 后来发现问题不那么简单 除了辗转相处法 古代还有什么类似的成就呢 1 通过辗转相除法与更相减损术 秦九韶算法的学习 进一步体会算法思想 2 会用辗转相除法与更相减损术求两个数的最大公约数 重点 3 会用秦九韶算法求多项式的值 重点 4 了解三种算法的程序框图和程序 难点 915 18和30的最大公约数是2 3 6 先用两个数公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来 问题1 在小学 我们已经学过求最大公约数的知识 你能求出18与30的最大公约数吗 2 3 1830 问题2 我们都是利用找公约数的方法来求最大公约数 如果公约数比较大而且根据我们的观察又不能得到一些公约数 我们又应该怎样求它们的最大公约数 比如求8251与6105的最大公约数 一 辗转相除法 欧几里得算法 思考 算出8251和6105的最大公约数 第一步 用两数中较大的数除以较小的数 求得商和余数8251 6105 1 2146 结论 8251和6105的公约数就是6105和2146的公约数 求8251和6105的最大公约数 只要求出6105和2146的最大公约数就可以了 1 课堂探究 第二步 对6105和2146重复第一步的做法 6105 2146 2 1813 同理6105和2146的最大公约数也是2146和1813的最大公约数 完整的过程 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的最大公约数 1 算理 所谓辗转相除法 就是对于给定的两个正整数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽 则这时较小的数就是原来两个数的最大公约数 2 辗转相除法 2 算法步骤第一步 输入两个正整数m n m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则转到第二步 第五步 输出最大公约数m 3 程序框图 4 程序 inputm ndor mmodnm nn rloopuntilr 0printmend 开始 输入m n 求m除以n的余数r m n n r r 0 是 输出m 结束 否 除了辗转相除法 还有其他的方法求两正整数的最大公约数吗 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 更相减损术 第一步 任意给定两个正整数 判断它们是否都是偶数 若是 用2约简 若不是 执行第二步 第二步 以较大的数减去较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的数相等为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 1 课堂探究 二 更相减损术 2 更相减损术 1 算理 所谓更相减损术 就是对于给定的两个数 用较大的数减去较小的数 然后将差和较小的数构成新的一对数 再用较大的数减去较小的数 反复执行此步骤 直到差数和较小的数相等 此时相等的两数便为原来两个数的最大公约数 2 算法步骤第一步 输入两个正整数a b 第二步 若a不等于b 则执行第三步 否则转到第五步 第三步 把a b的差赋给r 第四步 如果b r 那么把b赋给a 把r赋给b 否则把r赋给a 执行第二步 第五步 输出最大公约数b 3 程序框图 开始 输入a b b r a b 是 输出b 结束 a b r a b 是 否 b r a r 否 4 程序 input a b a bwhilea br a bifb rthena bb relsea rendifwendprintbend 例1用辗转相除法与更相减损术求98与63的最大公约数 解 更相减损术由于63不是偶数 把98和63以大数减小数 并辗转相减 三 例题选讲 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7所以 98与63的最大公约数等于7 辗转相除法98 63 1 3563 35 1 2835 28 1 728 7 4 0所以 98与63的最大公约数等于7 辗转相除法与更相减损术的比较 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 除了上述算法 下面学习另外一种古代优秀的算法 对于求n次多项式的值 在我国古代数学中有一个优秀算法 即秦九韶算法 我们将对这个算法作些了解和探究 1 课堂探究 四 秦九韶算法 思考1 对于多项式f x x5 x4 x3 x2 x 1 求f 5 的值 若先计算各项的值 然后再相加 那么一共要做多少次乘法运算和多少次加法运算 4 3 2 1 10次乘法运算 5次加法运算 思考2 在上述问题中 若先计算x2的值 然后依次计算x2 x x2 x x x2 x x x的值 这样每次都可以利用上一次计算的结果 再将这些数与x相乘和1相加 那么一共做了多少次乘法运算和多少次加法运算 4次乘法运算 5次加法运算 思考3 利用后一种算法求多项式f x anxn an 1xn 1 a1x a0的值 这个多项式应写成哪种形式 f x anxn an 1xn 1 a1x a0 anxn 1 an 1xn 2 a2x a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 这是怎样的一种改写方式 最后的结果是什么 思考4 对于f x anx an 1 x an 2 x a1 x a0 由内向外逐层计算一次多项式的值 其算法步骤如何 第一步 计算v1 anx an 1 第二步 计算v2 v1x an 2 第三步 计算v3 v2x an 3 第n步 计算vn vn 1x a0 最后的一项是什么 思考5 上述求多项式f x anxn an 1xn 1 a1x a0的值的方法称为秦九韶算法 利用该算法求f x0 的值 一共需要多少次乘法运算 多少次加法运算 n次乘法运算 n次加法运算思考6 在秦九韶算法中 记v0 an 那么第k步的算式是什么 vk vk 1x an k k 1 2 n 秦九韶算法的程序设计思考1 用秦九韶算法求多项式的值 其算法步骤如何设计 第一步 输入多项式的次数n 最高次项的系数an和x的值 第二步 令v an i n 1 第三步 输入i次项的系数ai 第四步 v vx ai i i 1 第五步 判断i 0是否成立 若是 则返回第三步 否则 输出多项式的值v 算法步骤 开始 输入n an x的值 v an v vx ai 输入ai i 0 i n 1 i i 1 结束 是 输出v 否 思考2 该算法的程序框图如何表示 input n ninput an ainput x xv ai n 1whilei 0print i iinput ai av v x ai i 1wendprintvend 思考3 该程序框图对应的程序如何表述 例2 已知一个5次多项式为f x 4x5 2x4 3 5x3 2 6x2 1 7x 0 8 用秦九韶算法求这个多项式当x 5时的值 解 根据秦九韶算法把多项式改写成如下形式 f x 4x 2 x 3 5 x 2 6 x 1 7 x 0 8 按照从内到外的顺序 依次计算一次多项式当x 5时的值 v0 4 v1 4 5 2 22 v2 22 5 3 5 113 5 v3 113 5 5 2 6 564 9 v4 564 9 5 1 7 2826 2 v5 2826 2 5 0 8 14130 2 所以f 5 14130 2 阅读右面程序 说明它解决的实际问题是什么 解 求多项式f x 1 2x 3x2 4x3 5x4在x a时的值 input x an 0y 0whilen 5y y n 1 a nn n 1wendprintyend 变式练习 1 下列对辗转相除法的说法错误的是 a 辗转相除法也叫欧几里得算法 但比欧几里得算法早b 辗转相除法的基本步骤是用较大的数除以较小的数c 在对两个数求最大公约数时 除辗转相除法之外还有更相减损术d 在用辗转相除法时 需要用到循环语句编写程序 a 2 秦九韶算法与直接计算相比较 下列说法错误的是 a 秦九韶算法与直接计算相比 大大节省了乘法的次数 使计算量减小 逻辑结构简单b 秦九韶算法减少做乘法的次数 在计算机上也就加快了计算的速度c 秦九韶算法减少做乘法的次数 在计算机上也就降低了计算的速度d 秦九韶算法避免对自变量x单独作幂的计算 而是与系数一起逐次增长幂次 从而可提高计算的精度 c 3 利用辗转相除法求两数4081与20723的最大公约数 解 20723 4081 5 318 4081 318 12 265 318 265 1 53 265 53 5 0 所以4081与20723的最大公约数是53 4 已知f x 3x4 2x2 4x 2 利用秦九韶算法求f 2 的值 解 f x 3x4 0 x3 2x2 4x 2 3x 0 x 2 x 4 x 2 v1 3 2 0 6 v2 6 2 2 14 v3 14 2 4 24 v4 24 2 2 50 故f 2