算法案例秦九韶算法.pptx

《算法案例秦九韶算法.pptx》由会员分享，可在线阅读，更多相关《算法案例秦九韶算法.pptx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算多项式()=当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页/共12页算法算法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次加法运算。第2页

2、/共12页数书九章数书九章秦九韶算法秦九韶算法设设是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：这是怎样的一种改写方式？最后的结果是什么？第3页/共12页要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一最后的一项是什么项是什么？这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。第4页/共12页通过一次

3、式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。秦九韶算法的特点：第5页/共12页例：例：已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解：解：将多项式变形：将多项式变形：按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当x=5时的值：时的值：所以，当所以，当x=5时，多项式的值等于时，多项式的值等于17255.2第6页/共12页另解：（秦九韶算法的另一种直观算法）5 2 3.5 -2.6 1.7 -0.8 X5 27 138.5 689.9 3451.2 1725

4、5.2+多项式的系数多项式的值25 135 692.5 3449.5 1725605第7页/共12页第一步：输入多项式次数第一步：输入多项式次数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,若是若是,则返回第三步则返回第三步;否则否则,输出多项式的值

5、输出多项式的值v.v.思考：你能设计程序把“秦九韶算法”表示出来吗？第8页/共12页第一步：输入多项式次数第一步：输入多项式次数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.程序框图程

6、序框图开始开始输入输入n,an,x的值的值v=ani=n-1i0？输出输出v输入输入aiv=vx+aii=i-1结束结束NY第9页/共12页开始开始输入输入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程序程序第10页/共12页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时的值。时的值。第11页/共12页感谢您的观看！第12页/共12页