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

1 3算法案例第1课时辗转相除法与更相减损术 秦九韶算法 1 通过辗转相除法与更相减损术 秦九韶算法的学习 进一步体会算法思想 2 通过古代著名的算法 理解掌握辗转相除法与更相减损术 秦九韶算法的含义 重点 3 了解其计算过程 重点 4 了解其算法程序框图和程序 难点 1 回顾算法的三种表述 自然语言程序框图 三种逻辑结构 程序语言 五种基本语句 2 小学学过的求两个数最大公约数的方法 先用两个公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来 例如 求两个正整数的最大公约数 1 求25和35的最大公约数 2 求49和63的最大公约数 所以 25和35的最大公约数为5 所以 49和63的最大公约数为7 除了用这种方法外还有没有其他方法吗 辗转相除法 欧几里得算法 思考 算出8251和6105的最大公约数 第一步 用两数中较大的数除以较小的数 求得商和余数8251 6105 1 2146 结论 8251和6105的公约数就是6105和2146的公约数 求8251和6105的最大公约数 只要求出6105和2146的最大公约数就可以了 为什么 第二步 对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 算法步骤第一步 输入两个正整数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 更相减损术算理 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 第一步 任意给定两个正整数 判断它们是否都是偶数 若是 则用2约简 若不是则执行第二步 第二步 以较大的数减较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的数相等为止 则这个数 等数 或其与约简的数的乘积就是所求的最大公约数 更相减损术 1 算理 所谓更相减损术 就是对于给定的两个数 用较大的数减去较小的数 然后将差和较小的数构成新的一对数 再用较大的数减去较小的数 反复执行此步骤 直到差数和较小的数相等 此时相等的两数便为原来两个数的最大公约数 2 算法步骤第一步 输入两个正整数a b a b 第二步 若a不等于b 则执行第三步 否则转到第五步 第三步 把a b的差赋予r 第四步 如果b r 那么把b赋给a 把r赋给b 否则把r赋给a 执行第二步 第五步 输出最大公约数b 3 程序框图 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 秦九韶算法的基本思想对于求n次多项式的值 在我国古代数学中有一个优秀算法 即秦九韶算法 我们将对这个算法作些了解和探究 思考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 的值 一共需要多少次乘法运算 多少次加法运算 思考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 思考2 该算法的程序框图如何表示 开始 输入n an x的值 v an v vx ai 输入ai i 0 i n 1 i i 1 结束 是 输出v 否 思考3 该程序框图对应的程序如何表述 开始 输入n an x的值 v an v vx ai 输入ai i 0 i n 1 i i 1 结束 是 输出v 否 input n ninput an ainput x xv ai n 1whilei 0print i iinput ai av v x ai i 1wendprintvend 例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 用辗转相除法求225和135的最大公约数 显然45是90和45的最大公约数 也就是225和135的最大公约数 225 135 1 90 135 90 1 45 90 45 2 2 利用辗转相除法求两数4081与20723的最大公约数 20723 4081 5 318 4081 318 12 265 318 265 1 53 265 53 5 0 所以4081与20723的最大公约数是53 3 用秦九韶算法求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值 解 首先将原多项式改写成如下形式 f x 2x 5 x 4 x 3 x 6 x 7然后由内向外逐层计算一次多项式当x 5时的值 即v0 2v1 v0 x 5 2 5 5 5v2 v1x 4 5 5 4 21v3 v2x 3 21 5 3 108v4 v3x 6 108 5 6 534v5 v4x 7 534 5 7 2677所以 当x 5时 多项式的值是2677 1 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上