秦九韶算法课堂教学ppt课件.pptx

1 3 3秦九韶算法 1 先做个计算 A 计算多项式 35 34 33 32 3 1 243 81 27 9 3 1 364B 计算多项式 3 1 3 1 3 1 3 1 3 1 12 1 3 1 3 1 3 1 39 1 3 1 3 1 121 3 1 364 哪种方法快 2 运算次数 A 35 34 33 32 3 1 364共做了1 2 3 4 10次乘法 5次加法 B 3 1 3 1 3 1 3 1 3 1 121 3 1 364共做了5次乘法 5次加法 直接求和法 3 A B f x x5 x4 x3 x2 x 1 x4 x3 x2 x 1 x 1 x3 x2 x 1 x 1 x 1 x2 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 秦九韶算法 4 秦九韶 秦九韶 1208年 1261年 南宋官员 数学家 与李冶 杨辉 朱世杰并称宋元数学四大家 字道古 自称鲁郡 今山东曲阜 人 生于普州安岳 今属四川 精研星象 音律 算术 诗词 弓剑 营造之学 历任琼州知府 司农丞 后遭贬 卒于梅州任所 著作 数书九章 其中的大衍求一术 三斜求积术和秦九韶算法是具有世界意义的重要贡献 霍纳算法 Horneralgorithm或Hornerscheme 5 数学九章 秦九韶算法 设f x 是一个n次多项式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 6 秦九韶算法 f x anx an 1 x an 2 x a1 x a0要求多项式的值 应先计算最内层多项式 v0 an v1 anx an 1然后 由内到外逐层计算一次多项式的值 v2 v1x an 2 7 秦九韶算法 v2 v1x an 2v3 v2x an 3 vn vn 1x a0这种将求一个n此多项式f x 的值转化成求n个一次多项式的值的方法 成为秦九韶算法 8 递推公式 v0 anvk vk 1x an k k 1 2 n 秦九韶算法的特点 通过一次式的反复计算 逐步得出高次多项式的值 对于一个n次多项式 只需做n次乘法和n次加法即可 9 例 已知一个五次多项式为f x 5x5 2x4 3 5x3 2 6x2 1 7x 0 8用秦九韶算法求这个多项式当x 5时的值 10 f x 5x5 2x4 3 5x3 2 6x2 1 7x 0 8 解 将多项式变形 f x 5x 2 x 3 5 x 2 6 x 1 7 x 0 8按由里到外的顺序 依此计算 v0 5v1 5 5 2 27v2 27 5 3 5 138 5v3 138 5 5 2 6 689 9v4 689 9 5 1 7 3451 2v5 3451 2 5 0 8 17255 2所以 当x 5时 多项式的值等于17255 2 11 算法步骤和程序框图 S1输入多项式次数n 最高次项的系数an和x的值 S2将v的值初始化为an 将i的值初始化为n 1 开始 输入n an x v an i n 1 1 12 算法步骤和程序框图 S3判断i是否大于或等于0 若是 输入i次项的系数an 否则 输出多项式的值v S4v vx ai i i 1 S5返回S3 输入ai v vx ai i i 1 i 0 1 输出v 结束 N Y 13 逐项求和法 逐项求和法在直接求和法的基础上做了改进 先把多项式写成f x an xn an 1 xn 1 a1 x1 a0的形式 这样多项式的每一含x的幂的项都是ak与xk的乘积 k 1 2 n 在计算ak xk项时把xk的值保存在变量c中 求ak 1 xk 1项时只需计算ak 1 x c 同时把x c xk 1的值保存入c中 继续下一项的运算 然后把这n 1项的值相加 14 计算机对于某程序的计算时间计算次数 主观 处理器内存及使用量计算计算机计算次数 真的快了 15 三种方法比较 乘法运算次数直接求和法 0 5n n 1 次逐项求和法 2n 1次秦九韶算法 n次 一般用不到 人工计算 高速算法 当n 3时 n 2n 1 0 5n n 1 秦九韶算法 逐项求和法 直接求和法 16 练习 已知多项式f x 3x4 2x3 10 x2 5x 1用秦九韶算法求这个多项式当x 2时的值 计算机程序实现 17 求函数近似根 f x anxn an 1xn 1 a1x a0 设根的精确度为d S1 给定自变量一个初值x0 给定自变量初始增量c c 0 S2 用秦九韶算法算出f x0 S3 若f x0 0 则c 0 1c 直到f xi c 0或c d 这时x xi c为方程的一个根 18 小结 一般高次