高一数学必修3算法案例之秦九韶算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法案例之,秦九韶算法,选自,数书九章,学习目标,:,1.,理解秦九韶算法的原理,;(,难点,),2.,了解该算法提高计算效率的实质,;,3.,会用秦九韶算法计算高次多项式的值,.(,重点,),问题,1:,设计求多项式,f(x,)=2x,5,-5x,4,-4x,3,+3x,2,-6x+7,当,x=5,时的值的算法,并写出程序,.,x=5,f=2,x5-5,x4-4,x3+3,x2-6,x+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.,这种求多项式值的方法就叫,秦九韶算法,.,例,1:,用秦九韶算法求多项式,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.,原多项式的系数,多项式的值,.,例,1:,用秦九韶算法求多项式,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,个一次多项式的值,.,这种算法称为,秦九韶算法,.,点评,:,秦九韶算法有哪些优点？,（,1,）大大减少了乘法的次数，使计算量减小，可以提高计算的效率；,（,2,）规律性强，便于利用循环语句来实现算法；,(3),避免了对自变量,X,单独做幂的计算，每次都是计算一个一次因式的值，从而可以提高计算的精度。,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,的值,.,若令,v,0,=a,n,得,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,n5?,n=1,v=a(5),v=vx+a(5-n),n=n+1,输出,v,结束,是,INPUT,a(0),a(1),a(2),a(3),a(4),a(5),INPUT,x,n=1,v=a(5),WHILE n=5,v=vx+a(5-n),n=n+1,WEND,PRINT v,END,程序,演示程序,随堂应用练习,课堂小结：,用秦九韶算法可大大降低乘法的运算次数,提高了运算速度,.,用此方法求值,关键是正确地将所给多项式改写,然后由内向外计算,由于后项计算需要用到前项结果,故应,认真,、,细心,、,确保结果的准确性,.,作业,:,课本,P48,页习题,1.3A,组,T2.,