福建省永安市高中数学 第一章 算法初步 1.3.2 秦九韶算法课件 新人教A版必修3.ppt

秦九韶算法 算法案例 第二课时 案例2秦九韶算法 这节课我们主要研究的是秦九韶算法中的一种 情境引入 问题是数学的心脏 p r halmos 波利亚 带着问题我们一起去看看古代中国人的智慧吧 了解一下中国古代数学对现代世界数学发展的贡献吧 新课探究 思考1 怎样求多项式f x x5 x4 x3 x2 x 1当x 5时的值呢 知识探究 一 秦九韶算法的基本思想 计算多项式 当x 5的值的算法 算法1 因为 所以 5 5 5 5 5 5 3125 625 125 25 5 3906 问 这种算法中各用了几次乘法运算 和几次加法运算 共做了1 2 3 4 10次乘法运算 5次加法运算 算法2 在上述问题中 若先计算x2的值 然后依次计算x2 x x2 x x x2 x x x的值 这样每次都可以利用上一次计算的结果 问 这种算法中各用了几次乘法运算 和几次加法运算 共做了4次乘法运算 5次加法运算 第二种做法与第一种做法相比 乘法的运算次数减少了 因而能提高运算效率 而且对于计算机来说 做一次乘法所需的运算时间比做一次加法要长得多 因此第二种做法能更快地得到结果 算法3 我们把多项式 变形为 从而得 问 这种算法中各用了几次乘法运算 和几次加法运算 共做了4次乘法运算 5次加法运算 一种更高效的算法 因为 思考2 怎样求多项式当x 5时的值呢 分析 将多项式变形为 令 这个算法共需多少次乘法运算 多少次加法运算 这个算法过程就是秦九韶算法过 思考3 如何用秦九韶算法完成一般多项式的求值问题 数书九章 秦九韶算法 对该多项式按下面的方式进行改写 思考3 当知道了x的值后该如何求多项式的值 这是怎样的一种改写方式 最后的结果是什么 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 最后的一项是什么 这种将求一个n次多项式f x 的值转化成求n个一次多项式的值的方法 称为秦九韶算法 思考4 在求多项式的值上 这是怎样的一个转化 把求一个n次多项式的值转化为求n个一次多项式的值 通过这种转化 把运算的次数由至多n n 1 2次乘法运算和n次加法运算 减少为n次乘法运算和n次加法运算 大大提高了运算效率 秦九韶算法的特点 思考5利用秦九韶算法算法n次多项式求f x0 的值 一共需要多少次乘法运算 多少次加法运算 1 算法步骤 第一步 输入多项式次数n 最高次项的系数an和x的值 第二步 将v的值初始化为an 将i的值初始化为n 1 第三步 输入i次项的系数an 第四步 v vx ai i i 1 第五步 判断i是否大于或等于0 若是 则返回第三步 否则 输出多项式的值v 思考1 用秦九韶算法求多项式的值 可以用什么逻辑结构来构造算法 其算法步骤如何设计 知识探究 二 秦九韶算法的程序设计 2 程序框图 思考2 该算法的程序框图如何表示 程序 input n ninput an ainput x xv ai n 1whilei 0print i iinput ai av v x ai i 1wendprintvend 思考3 该程序框图对应的程序如何表述 例1 已知一个五次多项式为 用秦九韶算法求这个多项式当x 5的值 解 将多项式变形 按由里到外的顺序 依此计算一次多项式当x 5时的值 所以 当x 5时 多项式的值等于14130 2 理论迁移 另解 秦九韶算法的另一种直观算法 423 5 2 61 7 0 8 x5 22113 5564 92826 214130 2 多项式的系数 多项式的值 20110567 52824 514131 0 4 练习1 已知多项式f x x5 3x4 3x3 5x2 5x 1当用秦九韶算法求这个多项式当x 5时的值 并统计需要多少次乘法计算和多少次加法计算 例2 已知多项式f x 3x4 2x2 4x 2用秦九韶算法求这个多项式当x 2时的值及v1 v3的值 解 这个解法正确吗 理论迁移 解 原多项式先化为 f x 3x4 0 x3 2x2 4x 2 注意 n次多项式有n 1项 因此缺少哪一项应将其系数补0 2 50 43 60 x 2 4 1 2 2 4 8 16 13 26 32 所以 当x 2时 多项式的值是 64 练习2 用秦九韶算法求多项式f x 2x6 5x5 4x3 3x2 6x当x 2时的值 解 原多项式先化为 f x 2x6 5x5 0 x4 4x3 3x2 6x 0列表 2 64 64 注意 n次多项式有n 1项 因此缺少哪一项应将其系数补0 已知