算法案例秦九韶算法.pptx

思考：思考：怎样求多项式怎样求多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值呢？时的值呢？计算多项式计算多项式()=当当x=5的值的算法：的值的算法：算法算法1：因为因为()=所以所以(5)=55555=3125625125255=3906算法算法2：(5)=55555=5(5555)=5(5(555 )=5(5(5(5+5+)+)+)+=5(5(5(5(5+)+)+)+)+算法算法1：因为因为()=所以所以(5)=55555=3125625125255=3906算法算法2：(5)=55555=5(5555)=5(5(555 )=5(5(5(5+5+)+)+)+=5(5(5(5(5+)+)+)+)+共做了共做了1+2+3+4=10次乘法运算，次乘法运算，5次加法运算。次加法运算。共做了共做了4次乘法运算，次乘法运算，5次加法运算。次加法运算。数书九章数书九章秦九韶算法秦九韶算法设设是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：这是怎样的一种改写方式？最后的结果是什么？要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一最后的一项是什么项是什么？这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。通过一次式的反复计算，逐步得出高次多项式的通过一次式的反复计算，逐步得出高次多项式的值，对于一个值，对于一个n次多项式，只需做次多项式，只需做n次乘法和次乘法和n次次加法即可。加法即可。秦九韶算法的特点：秦九韶算法的特点：例：例：已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解：解：将多项式变形：将多项式变形：按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当x=5时的值：时的值：所以，当所以，当x=5时，多项式的值等于时，多项式的值等于17255.2另解：（秦九韶算法的另一种直观算法）5 2 3.5 -2.6 1.7 -0.8 X5 27 138.5 689.9 3451.2 17255.2+多项式的系数多项式的值25 135 692.5 3449.5 1725605第一步：输入多项式次数第一步：输入多项式次数n n、最高次项的系数、最高次项的系数a an n和和x x的值的值算法步骤算法步骤第二步：将第二步：将v v的值初始化为的值初始化为a an n,将将i i的值初始化为的值初始化为n-1n-1第三步：输入第三步：输入i i次项的系数次项的系数a ai i第四步：第四步：v=vx+av=vx+ai i,i=i-1.,i=i-1.第五步：判断第五步：判断i i是否大于或等于是否大于或等于0,0,若是若是,则返回第三步则返回第三步;否则否则,输出多项式的值输出多项式的值v.v.思考：你能设计程序把“秦九韶算法”表示出来吗？第一步：输入多项式次数第一步：输入多项式次数n n、最、最高次项的系数高次项的系数a an n和和x x的值的值第二步：将第二步：将v v的值初始化为的值初始化为a an n,将将i i的值初始化为的值初始化为n-1n-1第三步：输入第三步：输入i i次项的系数次项的系数a ai i第四步：第四步：v=vx+av=vx+ai i,i=i-1.,i=i-1.第五步：判断第五步：判断i i是否大于或等于是否大于或等于0,0,若是若是,则返回第三步则返回第三步;否则否则,输输出多项式的值出多项式的值v.v.程序框图程序框图开始开始输入输入n,an,x的值的值v=ani=n-1i0？输出输出v输入输入aiv=vx+aii=i-1结束结束NY开始开始输入输入n,an,x的值的值v=ani=n-1i0？输出输出v输入输入aiv=vx+aii=i-1结束结束NYINPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE i=0 PRINT “i=”；i INPUT “ai=”;a v=v*x+a i=i-1WENDPRINT vEND程序程序1 1、已知多项式、已知多项式f(x)=xf(x)=x5 5+2x+2x4 4+x+x3 3-3x-3x2 2+5x+1+5x+1用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=2x=2时的值。时的值。练习：2 2、已知多项式、已知多项式f(x)=2xf(x)=2x4 4-x-x3 3-2x-2x2 2+3x-6+3x-6用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=2x=2时的值。时的值。