人教B版)(必修三)1.3中国古代数学中的算法案例(二)

1.3中国古代数学中的算法案例（二）秦九韶算法设计求多项式f(x)=2x5－5x4－4x3+3x2－6x+7当x=5时的值的算法，并写出程序。一般的解决方案x=5;f=2*x^5–5*x^4–4*x^3+3*x^2–6*x+7;f上述算法一共做了解15次乘法运算，5次加法运算.优点是简单，易懂;缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高。有没有更高效的算法？用提取公因式的方法多项式变形为f(x)=2x5－5x4－4x3+3x2－6x+7=((((2x－5)x－4)x+3)x－6)x+7这样共作了5次加法，5次乘法.从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？x的系数依次是什么？若将x的值代入变形后的式子中，那么求值的计算过程是怎样的?计算的过程可以列表表示为：多项式x系数2－5－43－67变形后x的系数25211085342677f(x)=((((2x－5)x－4)x+3)x－6)x+7,x=5秦九韶算法适用一般的多项式P(x)=anxn+an－1xn－1+……+a1x+a0的求值问题令vk=(…(anx+an－1)x+…+an－(k－1))x+an－k则递推公式为knkknaxvvav10k=1,2,…,n由此我们得到v1=v0x+an－1；v2=v1x+an－2；v3=v2x+an－3；……..vn=vn－1x+a0.这种计算方法，称之为秦九韶方法。直到今天，这种算法仍是世界上多项式求值的最先进的算法。这种方法的计算量仅为：乘法n次，加法n次.直接求和法：直接计算P(x)=anxn+an－1xn－1+…+a1x+a0的值需要进行n次加法，而乘法需要1+2+3+……+n=n(n+1)/2次。逐项求和法在直接求和法的基础上作了改进，先把多项式写成P(x)=an·xn+an－1·xn－1+…+a1·x1+a0的形式.逐项求和法所用的乘法的次数是2n－1,加法是n次。当n≥3时，2)1(12nnnn通过比较，我们知道秦九韶的算法比其它的算法要优越得多。怎样用程序框图表示秦九韶算法？观察秦九韶算法的数学模型，计算vk时要用到vk－1的值，若令v0=an，我们可以得到下面的递推公式：v0=anvk=vk－1·x+an－k(k=1,2,…,n)这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。k=k－1s=ak+s*x输出S结束k=n,s=an开始输入x,n;a0,a1,a2,…,ank0是否Scilab语言：x=input(x=);n=input(n=);result=input(Thefirstxishu);fori=1:1:na=input(xishu:);result=result*x+a;enddisp(result,Theresultis:);n=input(n=);//输入多项式次数a=zeros(1,n+1);//定义带下标的变量fori=1:1:n+1a(i)=input(a(i)=);//顺次输入系数a0,a1,...,anendx=input(x=);//输入自变量的值y=a(n+1);fori=1:1:ny=y*x+a(n+1－i);endy例1.用秦九韶方法求多项式f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5在x=－0.2时的值。解：在Scilab中运行上面的语句得到v0=a5v1=v0x+a4v2=v1x+a3v3=v2x+a2v4=v3x+a1v5=v4x+a0