福建省永安市高中数学算法初步1.3.2秦九韶算法课件新人教A版必修.pptx

秦九韶算法,算 法 案 例,第二课时,案例2 秦九韶算法,这节课我们主要研究的是秦九韶算法中的一种,情境引入,问题是数学的心脏。P.R.Halmos（波利亚） 带着问题我们一起去看看古代中国人的智慧吧！了解一下中国古代数学对现代世界数学发展的贡献吧！,新课探究:,思考1：怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？,知识探究(一):秦九韶算法的基本思想,计算多项式() = 当x = 5的值的算法：,算法1：,因为() =,所以(5)=55555,=3125625125255,= 3906,问：这种算法中各用了几次乘法运算？和几次加法运算？,共做了1+2+3+4=10次乘法运算，5次加法运算。,算法2:在上述问题中，若先计算x2的值，然后依次计算x2x，(x2x)x，(x2x)x)x的值，这样每次都可以利用上一次计算的结果.,问：这种算法中各用了几次乘法运算？和几次加法运算？,共做了4次乘法运算，5次加法运算。,第二种做法与第一种做法相比,乘法的运算次数减少了,因而能提高运算效率.而且对于计算机来说,做一次乘法所需的运算时间比做一次加法要长得多,因此第二种做法能更快地得到结果.,算法3：,我们把多项式 () = 变形为：,从而得：,问：这种算法中各用了几次乘法运算？和几次加法运算？,共做了4次乘法运算，5次加法运算。,一种更高效的算法,因为,思考2：怎样求多项式 当X=5时的值呢？,分析：将多项式变形为,令,这个算法共需多少次乘法运算？多少次加法运算？,这个算法过程就是秦九韶算法过？,思考3：如何用秦九韶算法完成一般多项式的求值问题？,数书九章秦九韶算法,对该多项式按下面的方式进行改写：,思考3：当知道了x的值后该如何求多项式的值？,这是怎样的一种改写方式？最后的结果是什么？,要求多项式的值，应该先算最内层的一次多项式的值，即,然后，由内到外逐层计算一次多项式的值，即,最后的一项是什么？,这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦九韶算法。,思考4：在求多项式的值上，这是怎样的一个转化？,把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数由至多n(n+1)/2次乘法运算和n次加法运算,减少为n次乘法运算和n次加法运算,大大提高了运算效率.,秦九韶算法的特点：,思考5 利用秦九韶算法算法n次多项式求f(x0)的值，一共需要多少次乘法运算，多少次加法运算？,(1)、算法步骤：,第一步：输入多项式次数n、最高次项的系数an和x的值.,第二步：将v的值初始化为an，将i的值初始化为n-1.,第三步：输入i次项的系数an.,第四步：v=vx+ai, i=i-1.,第五步：判断i是否大于或等于0，若是，则返回第三步；否则，输出多项式的值v。,思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,知识探究(二):秦九韶算法的程序设计,（2）程序框图：,思考2:该算法的程序框图如何表示？,程序：,INPUT “n=”；n INPUT “an=“;a INPUT “x=“;x v=a i=n-1 WHILE i=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1 WEND PRINT v END,思考3:该程序框图对应的程序如何表述？,例1： 已知一个五次多项式为,用秦九韶算法求这个多项式当x = 5的值。,解：,将多项式变形：,按由里到外的顺序，依此计算一次多项式当x = 5时的值：,所以，当x = 5时，多项式的值等于14130.2,理论迁移,另解：（秦九韶算法的另一种直观算法）,4 2 3.5 -2.6 1.7 -0.8,X5,22 113.5 564.9 2826.2 14130.2,+,多项式的系数,多项式的值,20 110 567.5 2824.5 14131,0,4,练习1：已知多项式f(x)=x5-3x4+3x3-5x2-5x+1当用秦九韶算法求这个多项式当x=5时的值。,并统计需要多少次乘法计算和多少次加法计算？,例2：已知多项式f(x)=3x4+2x2+4x+2 用秦九韶算法求这个多项式当x=-2时的值及V1,V3的值。,解：,这个解法正确吗？,理论迁移,解:原多项式先化为: f(x)=3x4+0x3+2x2+4x+2,注意:n次多项式有n+1项,因此缺少哪一项应将其系数补0.,2 -5 0 -4 3 -6 0,x=2,4,-1,-2,-2,-4,-8,-16,-13,-26,-32,所以,当x=2时,多项式的值是-64.,练习2:用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当x=2时的值.,解:原多项式先化为: f(x)=2x6-5x5 +0x4-4x3+3x2-6x+0 列表,2,-64,-64,注意:n次多项式有n+1项,因此缺少哪一项应将其系数补0.,已知多项式