1.3算法案例(二).ppt

《1.3算法案例(二).ppt》由会员分享，可在线阅读，更多相关《1.3算法案例(二).ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、怎样求多项式怎样求多项式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+)

2、+)+)+=5(5(5(5(5+)+)+)+)+共做了共做了1+2+3+4=10次乘法运算，次乘法运算，5次加法运算。次加法运算。共做了共做了4次乘法运算，次乘法运算，5次加法运算。次加法运算。秦九韶（秦九韶（1202-1261年），年），字道古，安岳县人。其父秦字道古，安岳县人。其父秦季栖，进士出身，官至工部季栖，进士出身，官至工部郎中、秘书少监。秦九韶性郎中、秘书少监。秦九韶性敏慧，勤奋好学，幼年随父敏慧，勤奋好学，幼年随父居中都（今北京），受到名居中都（今北京），受到名师指导，学习日益增进。及师指导，学习日益增进。及长，随父迁湖州（今浙江吴长，随父迁湖州（今浙江吴兴县），在西门外修建住房

3、，兴县），在西门外修建住房，由秦九韶设计施工，堂分由秦九韶设计施工，堂分7间，间，后为列室，仅中堂后为列室，仅中堂1间，纵横间，纵横7丈，极其宏伟宽敞，显示出丈，极其宏伟宽敞，显示出他在建筑方面的才能他在建筑方面的才能 数书九章数书九章秦九韶算法秦九韶算法数书九章数书九章秦九韶算法秦九韶算法设设是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：这是怎样的一种改写方式？最后的结果是什么？要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算

4、一次多项式的值，即最后的一最后的一项是什么项是什么？这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。算法步骤算法步骤：第一步：输入多项式次数第一步：输入多项式次数n、最高次项的系数、最高次项的系数an和和x的值的值.第二步：将第二步：将v的值初始化为的值初始化为an，将，将i的值初始化为的值初始化为n-1.第三步：输入第三步：输入i次项的系数次项的系数ai第四步：第四步：v=vx+ai,i=i-1.第五步：判断第五步：判断i是否是否大大于或等于于或等于0，若是，则返回第，若是，则返回第三步

5、；否则，输出多项式的值三步；否则，输出多项式的值v。程序框图：程序框图：这是一个在这是一个在秦九韶算法中秦九韶算法中反复执行的步骤，因此可反复执行的步骤，因此可用循环结构来实现。用循环结构来实现。输入输入ai开始开始输入输入n,an,xi 0?输出输出v结束结束v=vx+aii=i-1YNi=n-1V=an输入输入ai开始开始输入输入n,an,xi 0?输出输出v结束结束v=vx+aii=i-1YNi=n-1V=anINPUT n=;nINPUT an=;aINPUT x=;xv=ai=n-1WHILE i=0 PRINT i=;i INPUT ai=;a v=v*x+a i=i-1WENDP

6、RINT vEND程序程序特点：特点：通过一次式的反复计算，逐步得出高次多通过一次式的反复计算，逐步得出高次多项式的值，对于一个项式的值，对于一个n次多项式，只需做次多项式，只需做n次乘次乘法和法和n次加法即可。次加法即可。例例1:用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值.解法一解法一:首先将原多项式改写成如下形式首先将原多项式改写成如下形式:f(x)=(2x-5)x-4)x+3)x-6)x+7v0=2 v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=

7、1085-6=534v5=v4x+7=5345+7=2677所以所以,当当x=5时时,多多项式的值是项式的值是2677.然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即2 -5 -4 3 -6 7x=5105252110510854053426702677所以所以,当当x=5时时,多项式的值是多项式的值是2677.原多项式原多项式的系数的系数多项式多项式的值的值.例例1:用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值.解法二解法二:列表列表22 -5 0 -4 3 -6 0 x=51052525125

8、12160560830403034所以所以,当当x=5时时,多项式的值是多项式的值是15170.练一练练一练:用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当当x=5时的值时的值.解解:原多项式先化为原多项式先化为:f(x)=2x6-5x5+0 x4-4x3+3x2-6x+0列表列表21517015170 注意注意:n次多项式有次多项式有n+1项项,因此缺少哪一项因此缺少哪一项应将其系数补应将其系数补0.例例2 已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解：解：将多项式变形：将多项式变

9、形：按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当x=5时的值：时的值：所以，当所以，当x=5时，多项式的值等于时，多项式的值等于14130.2你从中看到了怎样的规律？怎么用程序框图来描述呢？程序框图：程序框图：开始输入f(x)的系数：a0,a1,a2,a3,a4,a5输入x0n5?输出v结束v=vx0+a5-nn=n+1NY n=1 v=a5这是一个在这是一个在秦九韶算法中秦九韶算法中反复执行的步骤，因此可反复执行的步骤，因此可用循环结构来实现。用循环结构来实现。练习、已知多项式练习、已知多项式f(x)=x5+5x4+10 x3+10 x2+5x+1用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=-2时的值。时的值。答案：1课堂小结：课堂小结：1、秦九韶算法的方法和步骤、秦九韶算法的方法和步骤2、秦九韶算法的程序框图、秦九韶算法的程序框图