示范教案13算法案例

示范教案13算法案例内容摘要：

思路 2（直接导入） 前面我们学习了辗转相除法与更相减损术， 今天我们开始学习秦九韶算法 . 推进新课 新知探究 提出问题 （ 1）求多项式 f(x)=x5+x4+x3+x2+x+1当 x=5时的值有哪些方法。 比较它们的特点 . （ 2）什么是秦九韶算法。 （ 3）怎样评价一个算法的好坏。 讨论结果： （ 1）怎样求多项式 f(x)=x5+x4+x3+x2+x+1当 x=5时的值呢。 一个自然的做法就是把 5代入多项式 f(x)，计算各项的值，然后把它们加起来，这时，我们一共做了 1+2+3+4=10次乘法运算， 5次加法运算 . 另一种做法是先计算 x2的值，然后依次计算 x2x ，（ x2x ） x ，（（ x2x ） x ） x 的值，这样每次都可以利用上一次计算的结果，这时，我们一共做了 4次乘法运算， 5次加法运算 . 第二种做法与第一种做法 相比，乘法的运算次数减少了，因而能够提高运算效率，对于计算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以采用第二种做法，计算机能更快地得到结果 . （ 2）上面问题有没有更有效的算法呢。 我国南宋时期的数学家秦九韶（约 1202~1261）在他的著作《数书九章》中提出了下面的算法： 把一个 n次多项式 f(x)=anxn+an1xn1+…+a 1x+a0改写成如下形式： f(x)=anxn+an1xn1+…+a 1x+a0 =（ anxn1+an1xn2+…+a 1） x+ a0 =（（ anxn2+an1xn3+…+a 2） x+a1)x+a0 =… =（ … （（ anx+an1） x+an2） x+…+a 1） x+a0. 求多项式的值时，首先计算最内层括号内一次多项式的值，即 v1=anx+an1， 然后由内向外逐层计算一次多项式的值，即 v2=v1x+an2， v3=v2x+an3， … vn=vn1x+a0， 这样，求 n次多项式 f（ x）的值就转化为求 n个一次多项式的值 . 上述方法称为秦九韶算法 .直到今天，这种算法仍是多项式求值比较先进的算法 . （ 3）计算机的一个很重要的特点就是运算速 度快，但即便如此，算法好坏的一个重要标志仍然是运算的次数 .如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论的算法 . 应用示例 例 1 已知一个 5次多项式为 f（ x） =5x5+2x4++， 用秦九韶算法求这个多项式当 x=5时的值 . 解： 根据秦九韶算法，把多项式改写成如下形式： f(x)=（ (((5x+2)x+))x+)， 按照从内到外的顺序，依次计算一次多项式当 x=5时的值： v0=5； v1=55+2=27。 v2=275+=。 v3==。 v4=5+=3。 v5=3 =17。 所以，当 x=5时，多项式的值等于 17 . 算法分析： 观察上述秦九韶算法中的 n个一次式，可见 vk的计算要用到 vk1的值，若令 v0=an，我们可以得到下面的公式：   ).,2,1(,10 nkaxvv avknkkn  这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现 . 算法步骤如下： 第一步，输 入多项式次数 n、最高次的系数 an和 x的值 . 第二步，将 v的值初始化为 an，将 i的值初始化为 n1. 第三步，输入 i次项的系数 ai. 第四步， v=vx+ai,i=i1. 第五步，判断 i是否大于或等于 ，则返回第三步；否则，输出多项式的值 v. 程序框图如下图 ： 程序 ： INPUT “n=”； n INPUT “an=”； a INPUT “x=”； x v=a i=n1 WHILE i＞ =0 PRINT “i=”； i INPUT “ai=”； a v=v*x+a i=i1 WEND PRINT v END 点评： 本题是古老算法与现代计算机语言的完美结合，详尽介绍了思想方法、算法步骤、程序框图和算法语句 ,是一个典型的算法案例 . 变式训练 请以 5次多项式函数为例说明秦九韶算法，并画出程序框图 . 解： 设 f（ x） =a5x5+a4x4+a3x3+a2x2+a1x+a0 首先，让我们以 5次多项式一步步地进行改写： f（ x） =（ a5x4+a4x3+a3x2+a2x+a1） x+a0 =（（ a5x3+a4x2+ a3x+a2） x+a1） x+a0 =（（（ a5x2+a4x+ a3） x+a2） x+a1） x+a0 =（（（（ a5x+a4） x+ a3） x+a2） x+a1） x+a0. 上面的分层计算 ,只用了小括号，计算时，首先计算最内层的括号，然后由里向外逐层计算，直到最外层的括号，然后加上常数项即可 . 程序框图如下图： 例 2 已知 n次多项式 Pn(x)=a0xn+a1xn1+…+a n1x+an，如果在一种算法中，计算 kx0 （ k=2， 3，4， … ， n）的值需要 k－ 1次乘法，计算 P3(x0)的值共需要 9次运算（ 6次乘法， 3次加法），那么计算 P10(x0)的值共需要 __________次运算 .下面给出一种减少运算次数的算法：P0(x)=a0,Pk+1(x)=xPk(x)+ak+1（ k＝ 0， 1， 2， … ， n－ 1）．利用该算法，计算 P3(x0)的值共需要6次运算，计算 P10(x0)的值共需要 ___________次运算 . 答案： 65 20 点评： 秦九韶算法适用一般的多项式 f(x)=anxn+an1xn1+…+a 1x+a0的求值问题 .直接法乘法运算的次数最多可到达 2)1( nn ，加法最多 n 次 .秦九韶算法通过转化把乘法运算的次数减少到最多 n次， 加法最多 n次 . 例 3 已知多项式函数 f(x)=2x5－ 5x4－ 4x3+3x2－ 6x+7，求当 x=5时的函数的值。