132《算法案例——秦九韶算法》（新人教A版必修3）课件.ppt

v主讲老师 潘学国思考：思考：怎样求多项式怎样求多项式f(x)=x5+x4+x3+x2+x+1当当x=5时的时的值呢？值呢？一个自然的做法是把一个自然的做法是把5代入多项式代入多项式f(x)，计算各，计算各项的值，然后把它们加起来。项的值，然后把它们加起来。这时，我们一共做了这时，我们一共做了1+2+3+4=10次乘法，次乘法，5次次加法运算。加法运算。优点是简单，易懂；缺点是不通用，不能解决优点是简单，易懂；缺点是不通用，不能解决任意多项式求值问题，而且计算效率不高。任意多项式求值问题，而且计算效率不高。温故知新温故知新思考：思考：在上述问题中，若先计算在上述问题中，若先计算x2的值，然后依次的值，然后依次计算计算x2x，(x2x)x，(x2x)x)x的值，这样每次都的值，这样每次都可以利用上一次计算的结果，一共做了多少次乘法可以利用上一次计算的结果，一共做了多少次乘法运算和多少次加法运算？运算和多少次加法运算？4次乘法运算，次乘法运算，5 5次加法运算次加法运算.第二种做法与第一种做法相比，乘法的运算次数第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高运算效率。而且对于计算机来说，减少了，因而能提高运算效率。而且对于计算机来说，做一次乘法所需的运算时间比做一次加法要长得多，做一次乘法所需的运算时间比做一次加法要长得多，因此第二种做法计算机能更快地得到结果。因此第二种做法计算机能更快地得到结果。思考：思考：有没有更有效的的算法呢有没有更有效的的算法呢?f(x)=x5+x4+x3+x2+x+1=(x4+x3+x2+x+1)x+1=(x3+x2+x+1)x+1)x+1=(x2+x+1)x+1)x+1)x+1=(x+1)x+1)x+1)x+1)x+1v0=1v1=v0 x+1=5+1=6v2=v1x+1=65+1=31v3=v2x+1=315+1=156v4=v3x+1=1565+1=781v5=v4x+1=7815+1=3906所以，当所以，当x=5时，多项式的值是时，多项式的值是3906.这种求多项式值的方法就叫这种求多项式值的方法就叫秦九韶算法秦九韶算法.我国南宋时期的数学家秦九韶在他的著作我国南宋时期的数学家秦九韶在他的著作数数学九章学九章提到了下面的算法。提到了下面的算法。秦九韶（秦九韶（秦九韶（秦九韶（1208120812081208年年年年1261126112611261年）南宋年）南宋年）南宋年）南宋官员、数学家，与李冶、杨辉、官员、数学家，与李冶、杨辉、官员、数学家，与李冶、杨辉、官员、数学家，与李冶、杨辉、朱世朱世朱世朱世杰并称宋元数学四大家。主要成就：杰并称宋元数学四大家。主要成就：杰并称宋元数学四大家。主要成就：杰并称宋元数学四大家。主要成就：1247124712471247年完成了数学名著年完成了数学名著年完成了数学名著年完成了数学名著数学九章数学九章数学九章数学九章，其中的大衍求一术、三斜求积术和秦其中的大衍求一术、三斜求积术和秦其中的大衍求一术、三斜求积术和秦其中的大衍求一术、三斜求积术和秦九韶算法是具有世界意义的重要贡献。九韶算法是具有世界意义的重要贡献。九韶算法是具有世界意义的重要贡献。九韶算法是具有世界意义的重要贡献。秦九韶算法就是中国古代数学的一枝秦九韶算法就是中国古代数学的一枝秦九韶算法就是中国古代数学的一枝秦九韶算法就是中国古代数学的一枝奇葩。直到今天，这种算法仍是多项奇葩。直到今天，这种算法仍是多项奇葩。直到今天，这种算法仍是多项奇葩。直到今天，这种算法仍是多项式求值比较先进的算法式求值比较先进的算法式求值比较先进的算法式求值比较先进的算法 。美国著名数学史家萨顿说过，秦美国著名数学史家萨顿说过，秦美国著名数学史家萨顿说过，秦美国著名数学史家萨顿说过，秦九韶是九韶是九韶是九韶是“他那个民族，他那个时代，他那个民族，他那个时代，他那个民族，他那个时代，他那个民族，他那个时代，并且确实也是所有时代最伟大的数学并且确实也是所有时代最伟大的数学并且确实也是所有时代最伟大的数学并且确实也是所有时代最伟大的数学家之一家之一家之一家之一”。把一个把一个n n次多项式次多项式 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)=(anx+an-1)x+an-2)x+a1)x+a0，由内向外逐层计算一次多项式的值，其计算过程如何？由内向外逐层计算一次多项式的值，其计算过程如何？v1=anx+an-1，v2=v1x+an-2，v3=v2x+an-3，vn=vn-1x+a0.例例1 1：已知一个已知一个5 5次多项式为次多项式为 f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8用秦九韶算法求用秦九韶算法求f(5)f(5)的值的值.f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=55+2=27；v2=275+3.5=138.5；v3=138.55-2.6=689.9；v4=689.95+1.7=3451.2；v5=3451.25-0.8=17255.2.所以所以f(5)=17255.2.练习：练习：已知一个已知一个5次多项式为次多项式为 f(x)=5x5+3.5x3+1.7x-0.8 用秦九韶算法求当用秦九韶算法求当x=5时，时，V1，V3的值及求的值及求f(5)的值的值.解：解：f(x)=(5x+0)x+3.5)x+0)x+1.7)x-0.8.v1=55+0=25；v2=255+3.5=128.5；v3=128.55+0=642.5；v4=642.55+1.7=3214.2；v5=3214.25-0.8=16070.2.所以所以v1=25，v3=642.5，f(5)=16070.2.思考：思考：上述求多项式上述求多项式 f(x)=anxn+an-1xn-1+a1x+a0的值的方法称为的值的方法称为秦九韶算法秦九韶算法，利用该算法求，利用该算法求f(x0)的值，一共需要多少的值，一共需要多少次乘法运算，多少次加法运算？次乘法运算，多少次加法运算？思考：思考：在秦九韶算法中，记在秦九韶算法中，记v0=an，那么第，那么第k步的算式步的算式是什么？是什么？vk=vk-1x+an-k(k=1，2，n)n n次乘法运算，次乘法运算，n n次加法运算次加法运算思考：思考：用秦九韶算法求多项式的值，可以用什么逻辑用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？结构来构造算法？其算法步骤如何设计？第一步，输入多项式的次数第一步，输入多项式的次数n n，最高次项的系数，最高次项的系数a an n和和x x的值的值.第二步，令第二步，令v=av=an n，i=n-1.i=n-1.第三步，输入第三步，输入i i次项的系数次项的系数a ai i.第四步，第四步，v=vx+av=vx+ai i，i=i-1.i=i-1.第五步，判断第五步，判断i0i0是否成立是否成立.若是，则返回第三步；若是，则返回第三步；否则，输出多项式的值否则，输出多项式的值v.v.思考：思考：该算法的程序该算法的程序框图如何表示？对应框图如何表示？对应的程序如何表述？的程序如何表述？开始开始输入输入n，an，x的值的值v=anv=vx+ai输入输入a ai ii0？i=n-1i=i-1结束结束是是输出输出v v否否开始开始输入输入n，an，x的值的值v=anv=vx+ai输入输入aii0？i=n-1i=i-1结束结束是是输出输出v否否INPUT “n=”；nINPUT “an=”；aINPUT “x=”；x v=ai=n-1WHILE i=0INPUT“ai=”；b v=v*x+bi=i-1 WENDPRINTPRINT v vENDENDPRINTPRINT“i=i=”；i i练习：练习：用秦九韶算法求用秦九韶算法求 f(x)=0.83x5+0.41x4+0.16x3+0.33x2+0.5x+1 当当x=5时的值时的值.v1=0.835+0.41=4.56；v2=4.565+0.16=22.96；v3=22.965+0.33=115.13；v4=115.135+0.5=576.15；v5=576.155+1=2881.75.f(5)=2881.75课时小结课时小结:评价一个算法好坏的一个重要评价一个算法好坏的一个重要标志是运算的次数，如果一个算法标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就内的运算次数，那么这样的算法就只能是一个理论算法只能是一个理论算法.在多项式求在多项式求值的各种算法中，秦九韶算法是一值的各种算法中，秦九韶算法是一个优秀算法个优秀算法.1：P45 练习练习22：P48 A组组 23：资料：资料作业布置作业布置