资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.3算法案例,案例2 秦九韶算法,教学设计,问题1设计求多项式f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7当x=5时的值的算法,并写出程序.,x=5,f=2x5-5x4-4x3+3x2-6x+7,PRINT f,END,程序,点评:上述算法一共做了15次乘法运算,5次加法运算.优点是简单,易懂;缺点是不通用,不能解决任意多项多求值问题,而且计算效率不高.,这析计算上述多项式的值,一共需要9次乘法运算,5次加法运算.,问题2有没有更高效的算法,分析:计算x的幂时,可以利用前面的计算结果,以减少计算量,即先计算x,2,然后依次计算,的值.,第二种做法与第一种做法相比,乘法的运算次数减少了,因而能提高运算效率.而且对于计算机来说,做一次乘法所需的运算时间比做一次加法要长得多,因此第二种做法能更快地得到结果.,问题3能否探索更好的算法,来解决任意多项式的求值问题,f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,=(,2x,4,-5x,3,-4x,2,+3x-6)x+7,=(2x,3,-5x,2,-4x+3)x-6)x+7,=(2x,2,-5x-4)x+3)x-6)x+7,=(2x-5)x-4)x+3)x-6)x+7,v,0,=2,v,1,=v,0,x-5=25-5=5,v,2,=v,1,x-4=55-4=21,v,3,=v,2,x+3,=215+3=108,v,4,=v,3,x-6,=1085-6=534,v,5,=v,4,x+7=5345+7=2677,所以,当x=5时,多项式的值是2677.,这种求多项式值的方法就叫,秦九韶算法.,例3:用秦九韶算法求多项式 f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7当x=5时的值.,解法一:首先将原多项式改写成如下形式 : f(x),=(2x-5)x-4)x+3)x-6)x+7,v,0,=2 v,1,=v,0,x-5=25-5=5,v,2,=v,1,x-4=55-4=21,v,3,=v,2,x+3=215+3=108,v,4,=v,3,x-6=1085-6=534,v,5,=v,4,x+7=5345+7=2677,所以,当x=5时,多项式的值是2677.,然后由内向外逐层计算一次多项式的值,即,2 -5 -4 3 -6 7,x=5,10,5,25,21,105,108,540,534,2670,2677,所以,当x=5时,多项式的值是2677.,原多项式的系数,多项式的值.,例3:用秦九韶算法求多项式 f(x)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7当x=5时的值.,解法二:列表,2,2 -5 0 -4 3 -6 0,x=5,10,5,25,25,125,121,605,608,3040,3034,所以,当x=5时,多项式的值是15170.,练一练:用秦九韶算法求多项式 f(x)=2x,6,-5x,5,-4x,3,+3x,2,-6x当x=5时的值.,解:原多项式先化为:,f(x)=2x,6,-5x,5,+,0,x,4,-4x,3,+3x,2,-6x+,0,列表,2,15170,15170,注意:n次多项式有n+1项,因此缺少哪一项应将其系数补0.,f(x)=a,n,x,n,+a,n-1,x,n-1,+a,n-2,x,n-2,+a,1,x+a,0,.,我们可以改写成如下形式:,f(x)=(a,n,x+a,n-1,)x+a,n-2,)x+a,1,)x+a,0,.,求多项式的值时,首先计算最内层括号内一次多项式的值,即,v,1,=a,n,x+a,n-1,然后由内向外逐层计算一次多项式的值,即,一般地,对于一个n次多项式,v,2,=v,1,x+a,n-2,v,3,=v,2,x+a,n-3, ,v,n,=v,n-1,x+a,0,.,这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.这种算法称为,秦九韶算法.,点评:秦九韶算法是求一元多项式的值的一种方法.,它的特点是:把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数由至多n(n+1)/2次乘法运算和n次加法运算,减少为n次乘法运算和n次加法运算,大大提高了运算效率.,v,1,=a,n,x+a,n-1,v,2,=v,1,x+a,n-2,v,3,=v,2,x+a,n-3, ,v,n,=v,n-1,x+a,0,.,观察上述秦九韶算法中的n个一次式,可见v,k,的计算要用到v,k-1,的值.,假设令v0=an,得,v,0,=a,n,v,K,=v,K-1,x+a,n-k,(k=1,2,n,这是一个在秦九韶算法中反复执行的步骤,因此可用循环构造来实现.,问题画出程序框图,表示用秦九韶算法求5次多项式f(x)=a,5,x,5,+a,4,x,4,+a,3,x,3,+a,2,x,2,+a,1,x+a,0,当x=x,0,(x,0,是任意实数)时的值的过程,然后写出程序.,否,程序框图,开场,输入a,0,a,1,a,2,a,3,a,4,a,5,输入x,0,n5,n=1,v=a,5,v=vx,0,+a,5-n,n=n+1,输出v,完毕,是,INPUT a,0, a,1, a,2, a,3, a,4, a,5,INPUT x,0,n=1,v=a,WHILE n=5,v=vx,0,+a,5-n,n=n+1,WEND,PRINT v,END,程序,作业:,课本P48页练习T2,
展开阅读全文