13算法案例教学课公开课一等奖课件省赛课获奖课件

§§1.3算法案例(二)案例2秦九韶算法问题如何求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？计算多项式ｆ(ｘ)

=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x=5的值算法1：由于ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１因此ｆ(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906算法2：ｆ(5)=5５＋5４＋5３＋5２＋5＋１=5×(5４＋5３＋5２＋5＋１)＋１=5×(5×(5３＋5２＋5＋１)＋１)＋１=5×(5×(5×(5２+5+１)+１)+１)+１=5×(5×(5×(5×(5+１)+１)+１)+１)+１分析：两种算法中各用了几次乘法运算？和几次加法运算？算法1：因为ｆ(ｘ)

=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906算法2：ｆ(5)=5５＋5４＋5３＋5２＋5＋１=5×(5４＋5３＋5２＋5＋１)＋１=5×(5×(5３＋5２＋5＋１)＋１)＋１=5×(5×(5×(5２+5+１)+１)+１)+１=5×(5×(5×(5×(5+１)+１)+１)+１)+１共做了1+2+3+4=10次乘法运算，5次加法运算。共做了4次乘法运算，5次加法运算。秦九韶（1202--1261年），字道古，安岳县人。其父秦季栖，进士出身，官至工部郎中、秘书少监。秦九韶性敏慧，勤奋好学，幼年随父居中都（今北京），受到名师指导，学习日益增进。及长，随父迁湖州（今浙江吴兴县），在西门外修建住房，由秦九韶设计施工，堂分7间，后为列室，仅中堂1间，纵横7丈，极其宏伟宽敞，显示出他在建筑方面的才干《数书九章》——秦九韶算法《数书九章》——秦九韶算法设是一个n次的多项式对该多项式按下面的方式进行改写：思考：当懂得了x的值后该如何求多项式的值？这是如何的一种改写方式？最后的成果是什么？规定多项式的值，应当先算最内层的一次多项式的值，即然后，由内到外逐级计算一次多项式的值，即最后的一项是什么？这种将求一种n次多项式f(x)的值转化成求n个一次多项式的值的办法，称为秦九韶算法。思考：在求多项式的值上，这是如何的一种转化？算法环节：第一步：输入多项式次数n、最高次项的系数an和x的值.第二步：将v的值初始化为an，将i的值初始化为n-1.第三步：输入i次项的系数ai第四步：v=vx+ai,i=i-1.第五步：判断i与否不不大于或等于0，若是，则返回第三步；否则，输出多项式的值v。程序框图：这是一种在秦九韶算法中重复执行的环节，因此可用循环构造来实现。输入ai开始输入n,an,xi0?输出v结束v=vx+aii=i-1YNi=n-1V=an输入ai开始输入n,an,xi0?输出v结束v=vx+aii=i-1YNi=n-1V=anINPUT"n=";nINPUT"an=";aINPUT"x=";xv=ai=n-1WHILEi>=0PRINT"i=";iINPUT"ai=";av=v*x+ai=i-1WENDPRINTvEND程序特点：通过一次式的重复计算，逐步得出高次多项式的值，对于一种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=2v1=v0x-5=2×5-5=5v2=v1x-4=5×5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677因此,当x=5时,多项式的值是2677.然后由内向外逐级计算一次多项式的值,即2-5-43-67x=5105252110510854053426702677因此,当x=5时,多项式的值是2677.原多项式的系数多项式的值.例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.解法二:列表22-50-43-60x=5105252512512160560830403034因此,当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的值。解：将多项式变形：按由里到外的次序，依此计算一次多项式当x=5时的值：因此，当x=5时，多项式的值等于14130.2你从中看到了如何的规律？怎么用程序框图来描述呢？程序框图：开始输入f(x)的系数：a0,a1,a2,a3,a4,a5输入x0n≤5?输出v结束v=vx0+a5-nn=n+1NY

n=