高中数学 算法案例课件（2）新人教A版必修3.ppt

第一章算法初步 1 3算法案例 2 分别用辗转相除法与更相减损术求1037与425的最大公约数 怎样求多项式f x x5 x4 x3 x2 x 1当x 5时的值呢 算法1 因为 所以 5 5 5 5 5 5 3125 625 125 25 5 3906 思考 在这种算法中共进行了多少次乘方运算与加法运算 一共做了4 3 2 1 10次乘法运算 5次加法运算 计算多项式 当x 5的值的算法 算法2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 思考 在这种算法中共进行了多少次乘方运算与加法运算 一共做了4次乘法运算 5次加法运算 以上两种算法 相对计算机来说哪一种运算效率更高 第二种算法与第一种算法相比 乘法的运算次数减少了 能够提高运算效率 对于计算机来说 做一次乘法运算所用的时间比做一次加法运算要长得多 所以采用第二种算法 计算机能更快得到结果 效率更高 用第二种算法 我们可以从最里层的括号开始逐步向外层括号计算 最终得到结果 这就是我国南宋数学家秦九韶提出的 秦九韶算法 秦九韶 1208年 1261年 南宋官员 数学家 与李冶 杨辉 朱世杰并称宋元数学四大家 主要成就 1247年完成了数学名著 数学九章 其中的大衍求一术 三斜求积术和秦九韶算法是具有世界意义的重要贡献 秦九韶算法就是中国古代数学的一枝奇葩 直到今天 这种算法仍是多项式求值比较先进的算法 美国著名科学史家萨顿说过 秦九韶是 他那个民族 他那个时代 并且确实也是所有时代最伟大的数学家之一 所以我们的先贤孜孜不倦的治学与研究精神 是我们学习的楷模 对该多项式按下面的方式进行改写 思考 当知道了x的值后该如何求多项式的值 案例2秦九韶算法 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 最后的一项是什么 这种将求一个n次多项式f x 的值转化成求n个一次多项式的值的方法 称为秦九韶算法 已知一个五次多项式为 用秦九韶算法求这个多项式当x 5的值 解 将多项式变形 按由里到外的顺序 依此计算一次多项式当x 5时的值 所以 当x 5时 多项式的值等于17255 2 把求一个n次多项式f x 的值转化成求n个一次多项式的值 即把求 的值转化为求递推公式 在求多项式的值上 用秦九韶算法是怎样的一个转化 通过这种转化 把运算的次数由至多次乘法运算和n次加法运算 减少为至多n次乘法运算和n次加法运算 大大提高了运算效率 用秦九韶算法求多项式的值 可以用什么逻辑结构来构造算法 你能设计出它的运算程序吗 第一步 输入多项式的次数n 最高次项的系数an和x的值 第二步 令v an i n 1 第三步 输入i次项的系数ai 第四步 v vx ai i i 1 第五步 判断 i 0 是否成立 若是 则返回第三步 否则输出多项式的值v 用循环结构构造算法 其算法步骤为 程序框图 已知多项式f x x5 5x4 10 x3 10 x2 5x 1 用秦九韶算法求这个多项式当x 2时的值 解 原多项式改写成为 本节