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

算算 法法 案案 例例第二课时案例案例2 秦九韶算法秦九韶算法这节课我们主要研究的是秦九韶算法中的一种这节课我们主要研究的是秦九韶算法中的一种 情境引入情境引入§问题是数学的心脏——P.R.Halmos（波利亚）§带着问题我们一起去看看古代中国人的智慧吧！了解一下中国古代数学对现代世界数学发展的贡献吧！新课探究:思考思考1：：怎样求多项式怎样求多项式f(xf(x)=x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值呢？时的值呢？x=5f=x^5+x^4+x^3+x^2+x+1PRINT fEND程序程序知识探究知识探究( (一一):):秦九韶算法的基本思想秦九韶算法的基本思想 计算多项式计算多项式ｆｆ(ｘｘ) =ｘｘ５５＋＋ｘｘ４４＋＋ｘｘ３３＋＋ｘｘ２２＋＋ｘｘ＋１＋１当当x = 5的值的算法：的值的算法：算法算法1：：因为因为ｆｆ(ｘｘ) =ｘｘ５５＋＋ｘｘ４４＋＋ｘｘ３３＋＋ｘｘ２２＋＋ｘｘ＋１＋１所以所以ｆｆ(5)=5５５＋＋5４４＋＋5３３＋＋5２２＋＋5＋１＋１=3125＋＋625＋＋125＋＋25＋＋5＋１＋１= 3906共做了共做了1+2+3+4=10次乘法运算，次乘法运算，5次加法运算。

次加法运算算法算法2:2:在上述问题中，若先计算在上述问题中，若先计算x x2 2的值，的值，然后依次计算然后依次计算x x2 2··x x，，(x(x2 2··x)x)··x x，，((x((x2 2··x)x)··x)x)··x x的值，这样每次都可以的值，这样每次都可以利用上一次计算的结果利用上一次计算的结果. .共做了共做了4次乘法运算，次乘法运算，5次加法运算次加法运算第二种做法与第一种做法相比第二种做法与第一种做法相比,乘法的运算次数乘法的运算次数减少了减少了,因而能提高运算效率因而能提高运算效率.而且对于计算机来说而且对于计算机来说,做做一次乘法所需的运算时间比做一次加法要长得多一次乘法所需的运算时间比做一次加法要长得多,因此因此第二种做法能更快地得到结果第二种做法能更快地得到结果.算法算法3：：我们把多项式ｆｆ(ｘｘ) =ｘｘ５＋５＋ｘｘ４＋４＋ｘｘ３＋３＋ｘｘ２＋２＋ｘｘ＋１＋１变形为： 从而得： 共做了共做了4次乘法运算，次乘法运算，5次加法运算次加法运算一种更高效的算法因为因为思考2：怎样求多项式当X=5时的值呢？分析：将多项式变形为令这个算法过程就是秦九韶算法过？思考3：如何用秦九韶算法完成一般多项式的求值问题？《《数书九章数书九章》》——秦九韶算法秦九韶算法设设是一个是一个n 次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：这是怎样的一种改写方式？最后的结果是什么？要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一最后的一项是什么项是什么？？这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法，称为次多项式的值的方法，称为秦九韶算法秦九韶算法。

把求一个把求一个n次多项式的值转化为求次多项式的值转化为求n个一次多项个一次多项式的值式的值,通过这种转化通过这种转化,把运算的次数由至多把运算的次数由至多n(n+1)/2次乘法运算和次乘法运算和n次加法运算次加法运算,减少为减少为n次次乘法运算和乘法运算和n次加法运算次加法运算,大大提高了运算效率大大提高了运算效率.秦九韶算法的特点：秦九韶算法的特点：思考思考5 5 利用利用秦九韶算法秦九韶算法算法算法n n次多项式次多项式求求f(xf(x0 0) )的值，一共需要多少次乘法运算，的值，一共需要多少次乘法运算，多少次加法运算？多少次加法运算？ (1)、算法步骤：、算法步骤：第一步：输入多项式次数第一步：输入多项式次数n、最高次项的系数、最高次项的系数an和和x的值的值.第二步：将第二步：将v的值初始化为的值初始化为an，将，将i的值初始化为的值初始化为n-1.第三步：输入第三步：输入i次项的系数次项的系数an.第四步：第四步：v=vx+ai, i=i-1.第五步：判断第五步：判断i是否大于或等于是否大于或等于0，若是，则返回第，若是，则返回第三步；否则，输出多项式的值三步；否则，输出多项式的值v。

思考思考1:用秦九韶算法求多项式的值，可以用什么用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？逻辑结构来构造算法？其算法步骤如何设计？知识探究知识探究( (二二):):秦九韶算法的程序设计秦九韶算法的程序设计 （（2）程序框图：）程序框图：输入输入ai开始开始输入输入n,an,xi>=0?输出输出v结束结束v=vx+aii=i-1YNi=n-1V=an思考思考2:该算法的程序框图如何表示？该算法的程序框图如何表示？程序：程序：INPUT “n=”；nINPUT “an=“;aINPUT “x=“;xv=ai=n-1WHILE i>=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1WENDPRINT vEND思考思考3:该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？输入输入ai开始开始输入输入n,an,xi>=0?输出输出v结束结束v=vx+aii=i-1YNi=n-1V=an例例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 1413104练习练习1：：已知已知多项式多项式f(xf(x)=x)=x5 5-3x-3x4 4+3x+3x3 3-5x-5x2 2- -5x+15x+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 0x=24-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 +0×x4-4x3+3x2-6x+0列表列表2-64-64 注意注意:n次多项式有次多项式有n+1项项,因此缺少哪一项因此缺少哪一项应将其系数补应将其系数补0.已知多项式已知多项式f(x)=2x5-6x3-5x2+4x-6用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=5时的值。

时的值练习3：课堂小结：课堂小结：1、秦九韶算法的方法和步骤、秦九韶算法的方法和步骤2、秦九韶算法的程序框图、秦九韶算法的程序框图作业：作业：1、、P45 22、、P48 23、课后练习、课后练习。