1.3算法案例—(2)秦九韶算法.ppt

1 3算法案例 案例2秦九韶算法 复习 1 求两个数的最大公约数的两种方法分别是 和 2 两个数21672 8127的最大公约数是 A 2709B 2606C 2703D 27063 用更相减损术求140和80的最大公约数是 A 4B 5C 10D 20 更相减损术 辗转相除法 A D 21672 8127 2 54188127 5418 1 27095418 2709 2 0 辗转相除法与更相减损术的比较 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 问题1 怎样求多项式f x x5 x4 x3 x2 x 1当x 5时的值 并写出程序 算法1 3906 因为f x x5 x4 x3 x2 x 1 所以 5 5 5 5 5 5 1 3125 625 125 25 5 1 一共做了多少次乘法运算和多少次加法运算 上述算法一共做了1 2 3 4 10次乘法运算 5次加法运算 优点是简单易懂 但计算效率不高 算法2 5 5 5 5 5 5 1 5 5 5 5 5 1 1 5 5 5 5 5 1 1 1 5 5 5 5 5 1 1 1 1 5 5 5 5 5 1 1 1 1 1 这种算法中用了几次乘法运算 和几次加法运算 计算多项式f x x5 x4 x3 x2 x 1当x 5的值 共做了4次乘法运算 5次加法运算 问题2 能否探索一个算法 来解决任意多项式的求值问题 f x 2x5 5x4 4x3 3x2 6x 7 2x4 5x3 4x2 3x 6 x 7 2x3 5x2 4x 3 x 6 x 7 2x2 5x 4 x 3 x 6 x 7 2x 5 x 4 x 3 x 6 x 7 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 这种求多项式值的方法就叫秦九韶算法 当x 5时 多项式的值是多少 数书九章 秦九韶算法 对该多项式按下面的方式进行改写 思考 当知道了x的值后该如何求多项式的值 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 最后的一项是什么 这种将求一个n次多项式f x 的值转化成求n个一次多项式的值的方法 称为秦九韶算法 思考 在求多项式的值上 这是怎样的一个转化 f x anxn an 1xn 1 an 2xn 2 a1x a0 我们可以改写成如下形式 f x anx an 1 x an 2 x a1 x a0 求多项式的值时 首先计算最内层括号内一次多项式的值 即 v1 anx an 1 然后由内向外逐层计算一次多项式的值 即 一般地 对于一个n次多项式 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 这样 求n次多项式f x 的值就转化为求n个一次多项式的值 这种算法称为秦九韶算法 特点 通过一次式的反复计算 逐步得出高次多项式的值 注 对于一个n次多项式 秦九韶算法把运算的次数由最多1 2 3 n n n 1 2次乘法和n次加法的运算 减少为最多只需做n次乘法和n次加法运算 大大提高了运算效率 例1 用秦九韶算法求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值 解法一 首先将原多项式改写成如下形式 f x 2x 5 x 4 x 3 x 6 x 7 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 然后由内向外逐层计算一次多项式的值 即 2 5 43 67 x 5 10 5 25 21 105 108 540 534 2670 2677 所以 当x 5时 多项式的值是2677 原多项式的系数 多项式的值 例1 用秦九韶算法求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值 解法二 列表 2 v0 v1 v2 v3 v4 v5 2 50 43 60 x 5 10 5 25 25 125 121 605 608 3040 3034 所以 当x 5时 多项式的值是15170 练一练 用秦九韶算法求多项式f x 2x6 5x5 4x3 3x2 6x当x 5时的值 解 原多项式先化为 f x 2x6 5x5 0 x4 4x3 3x2 6x 0 列表如下 2 15170 15170 注意 n次多项式有n 1项 因此缺少哪一项应将其系数补0 v1 anx an 1 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 观察上述秦九韶算法中的n个一次式 可见vk的计算要用到vk 1的值 若令v0 an 得 这是一个在秦九韶算法中反复执行的步骤 因此可用循环结构来实现 因此可用循环结构来实现 算法步骤 第一步 输入多项式次数n 最高次项的系数an和x的值 第二步 将v的值初始化为an 将i的值初始化为1 第三步 输入n i次项的系数an i 第四步 v vx an i i i 1 第五步 判断i是否小于或等于n 若是 则返回第三步 否则 输出多项式的值v 否 开始 输入a0 a1 a2 a3 a4 a5 输入x0 n 5 n 1 v a5 v vx0 a5 n n n 1 输出v 结束 是