1.3-2秦九韶算法.ppt

1.3算法案例,第二课时,问题提出,对于求n次多项式的值，比如函数f(x)=x5+x4+x3+x2+x+1,求f(5)的值.在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.,知识探究(一):秦九韶算法的基本思想,思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值.若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？,乘法运算:,10次,4+3+2+1=,5次,加法运算:,思考2:在上述问题中，若先计算x2的值，然后依次计算,多项式f(x)=x5+x4+x3+x2+x+1，求f(5).,x2x，,(x2x)x)x的值，,(x2x)x，,4,5,思考3:利用后一种算法求多项式f(x)=anxn+an-1xn-1+a1x+a0的值，这个多项式应写成哪种形式？,f(x)=anxn+an-1xn-1+a1x+a0,(anxn-1+an-1xn-2+a2x+a1)x+a0,=(anxn-2+an-1xn-3+a2)x+a1)x+a0,=,=,=(anx+an-1)x+an-2)x+a1)x+a0,f(x)=,(2x+3.5),x-0.8,x,-2.6),(,+1.7),x,(,4,4,f(x)=,(4x+3),x-3),x,-1),(,+2),x,(,(,x+5,5,5,f(x)=anxn+an-1xn-1+a1x+a0,=(anx+an-1)x+an-2)x+a1)x+a0,思考3:利用后一种算法求多项式f(x)=anxn+an-1xn-1+a1x+a0的值，这个多项式应写成哪种形式？,f(x)=anxn+an-1xn-1+a1x+a0,(anxn-1+an-1xn-2+a2x+a1)x+a0,=(anxn-2+an-1xn-3+a2)x+a1)x+a0,=,=,=(anx+an-1)x+an-2)x+a1)x+a0,n,n,上述求多项式f(x)=anxn+an-1xn-1+a1x+a0的值的方法称为秦九韶算法，利用该算法可求f(x0)的值.,例1已知一个5次多项式为用秦九韶算法求f(5)的值.,f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.,v1=,v2=,v3=,v4=,v5=,f(5)=14130.2.,解：根据秦九韶算法，把多项式改写成,v0=,4,45+2=,22,225+3.5=,113.5,113.55-2.6=,564.9,2826.2,564.95+1.7=,14130.2.,2826.25-0.8=,求f(4)的值.,f(x)=(3x+2)x-9)x-11)x+1,解：根据秦九韶算法，把多项式改写成,v1=,v2=,v3=,v4=,f(4)=709.,v0=,3；,34+2=,14；,144-9=,47；,474-11=,177；,709；,1774+1=,练习1:,f(x)=3x4+2x3-9x2-11x+1,当x=-2时的值.,f(x)=(x+5)x+10)x+10)x)+5)x+1,解：根据秦九韶算法，把多项式改写成,v1=,v2=,v3=,v4=,f(-2)=-1.,v0=,1,1(-2)+5=,3,3(-2)+10=,4,4(-2)+10=,2,1,2(-2)+5=,练习2:,f(x)=x5+5x4+10 x3+10 x2+5x+1,v5=,-1.,1(-2)+1=,f(x)=,(x+3),x-3),x,-1),(,+2),x,(,(,x+5,4,5,秦九韶算法的特点及注意事项：,特点：,通过一次式的反复计算，有规律的推算出下一个值，从而计算高次多项式的值，这种算法也称为“递推法”.对于一个n次多项式当最高次项的系数不为1时，需进行次乘法；若各项均不为零，则需进行次加法（或减法），缺几项减去几.,n,n,注意：,若多项式函数中间出现空项，,要以系数为0补齐此项，即0xm,应用秦九韶算法计算x=3时的值时，v3的值为(),3.已知,A27B11C109D36,f(x)=(x+0)x+2)x+3)x+1)x+1,v1=,v2=,v3=,v0=,1；,13+0=,3；,33+2=,11；,113+3=,36.,D,f(x)=x5+0 x4+2x3+3x2+x+1,f(x)=x5+2x3+3x2+x+1,4.用秦九韶算法计算多项式,A6,6B5,6C5,5D6,5,A,D,当x=0.4时的值时，需要做乘法和加法的次数分别是(),6.用秦九韶算法计算下列多项式当x=2时,(1)f(x)=x5+2x4-3x3+x2-x+1,(2)f(x)=2x5+2x4-3x3+x2-x+1,乘法,加法,(3)f(x)=2x5+2x3-3x2+x-1,(4)f(x)=x5+2x3-3x2+x-1,(5)f(x)=2x6+2x4-3x2+x,(6)f(x)=x6+2x4-3x2+x,4,5,5,5,5,4,4,4,6,4,5,4,所需乘法和加法的次数,知识探究(二):秦九韶算法的程序设计,思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，输入多项式的次数n，最高次项的系数an和x的值.,第二步，令v=an，i=n-1.,第三步，输入i次项的系数ai.,第四步，v=vx+ai，i=i-1.,第五步，判断“i0”是否成立.若是，则,循环结构,(当型),返回第三步，否则，,输出多项式的值v.,思考2:该算法的程序框图如何表示？,是,输入n,an和x的值.,令v=an，i=n-1.,输入ai,v=vx+ai，i=i-1.,判断“i0”是否成立,若是，则,否则,输出v.,思考3:程序？,INPUT“n=”；n,INPUT“an=”；a,INPUT“x=”；x,v=a,i=n-1,WHILEi=0,INPUT“ai=