1、秦九韶和秦九韶和数书九章数书九章n 秦九韶(约公元秦九韶(约公元12021202年年12611261年),字年),字道古,南宋末年人,出生于鲁郡(今道古,南宋末年人,出生于鲁郡(今山东山东阜一带人)阜一带人)n 据史书记载,他据史书记载,他“性及机巧,星象、性及机巧,星象、音律、算术以至营造无不精究音律、算术以至营造无不精究”,还尝从,还尝从李李梅亭梅亭学诗词。他在政务之余,以数学为主线学诗词。他在政务之余,以数学为主线进行潜心钻研,且应用范围至为广泛:天文进行潜心钻研,且应用范围至为广泛:天文历法、水利水文、建筑、测绘、农耕、军事、历法、水利水文、建筑、测绘、农耕、军事、商业金融等方面。商业
2、金融等方面。n 秦九韶与李冶、秦九韶与李冶、杨辉杨辉、朱世杰并称、朱世杰并称宋宋元数学四大家元数学四大家。秦九韶秦九韶秦九韶和秦九韶和数书九章数书九章n 宋淳祜四至七年(公元宋淳祜四至七年(公元1244至至1247),),秦九韶在秦九韶在湖州湖州为母亲守孝三年期间,把长期为母亲守孝三年期间,把长期积累的数学知识和研究所得加以编辑,写成积累的数学知识和研究所得加以编辑,写成了举世闻名的数学巨著了举世闻名的数学巨著数书九章数书九章。n数书九章数书九章全书共九章九类,十八全书共九章九类,十八卷,每类卷,每类9题共计题共计81个算题。该书著述方个算题。该书著述方式,大多由式,大多由“问曰问曰”、“答曰
3、答曰”、“术曰术曰”、“草草曰曰”四部分组成:四部分组成:“问曰问曰”,是从实际生活中,是从实际生活中提出问题;提出问题;“答曰答曰”,是给出答案;,是给出答案;“术曰术曰”,是阐述解题原理与步骤;是阐述解题原理与步骤;“草曰草曰”,是给出详,是给出详细的解题过程。另外,每类下还有颂词,词细的解题过程。另外,每类下还有颂词,词简意赅,用来记述本类算题主要内容、与国简意赅,用来记述本类算题主要内容、与国计民生的关系及其解题思路等计民生的关系及其解题思路等。秦九韶秦九韶秦九韶和秦九韶和数书九章数书九章n 他在他在数书九章数书九章序言中说,数学序言中说,数学“大大则可以通神明,顺性命;小则可以经世务
4、,则可以通神明,顺性命;小则可以经世务,类万物类万物”。所谓。所谓“通神明通神明”,即往来于变化莫,即往来于变化莫测的事物之间,明察其中的奥秘;测的事物之间,明察其中的奥秘;“顺性顺性命命”,即顺应事物本性及其发展规律。在秦,即顺应事物本性及其发展规律。在秦九韶看来,数学不仅是解决实际问题的工九韶看来,数学不仅是解决实际问题的工具,而且应该达到具,而且应该达到“通神明,顺性命通神明,顺性命”的崇高的崇高境界。境界。n 从历史上来看,秦九韶的从历史上来看,秦九韶的数数书九章书九章可与可与九章算术九章算术相媲美;从世界范围来相媲美;从世界范围来看,秦九韶的看,秦九韶的数书九章数书九章也不愧为世界也
5、不愧为世界数数学名著学名著。秦九韶秦九韶 问题问题1 1:怎样求多项式怎样求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值?时的值?x=5f=2x5-5x4-4x3+3x2-6x+7PRINT fEND方法一方法一 此算的优点是简单此算的优点是简单,易懂;缺点是不通用易懂;缺点是不通用,不能解决任意多项多求值问题不能解决任意多项多求值问题,而且计而且计算效率不高算效率不高.15次乘法运算次乘法运算,5次加法运算次加法运算 方法二方法二:先计算先计算x x2 2的值,然后依次计算的值,然后依次计算x x2 2xx,(x(x2 2x)x)x x,(x(x2 2x)x)x)
6、x)x x的值,的值,这样每次都可以利用上一次计算的结果这样每次都可以利用上一次计算的结果.与第一种做法相比与第一种做法相比,这种做法中,乘法的运算次数减少了这种做法中,乘法的运算次数减少了,因而能提高运算效率因而能提高运算效率.而且对于计算机来说而且对于计算机来说,做一次乘法所需的运算时间比做一次加法要长得多做一次乘法所需的运算时间比做一次加法要长得多,因此第二因此第二种做法能更快地得到结果种做法能更快地得到结果.问题问题1 1:怎样求多项式怎样求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值?时的值?9次乘法运算次乘法运算,5次加法运算次加法运算 方法三:方法三:
7、能否有更好的算法能否有更好的算法,解决任意多项式的求值问题解决任意多项式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7 问题问题1 1:怎样求多项式怎样求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值?时的值?方法三:方法三:能否有更好的算法能否有更好的算法,解决任意多项式的求值问题解决任意多项式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4
8、x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5 问题问题1 1:怎样求多项式怎样求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值?时的值?方法三:方法三:能否有更好的算法能否有更好的算法,解决任意多项式的求值问题解决任意多项式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2
9、x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5 问题问题1 1:怎样求多项式怎样求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值?时的值?v2=v1x-4=55-4=21 方法三:方法三:能否有更好的算法能否有更好的算法,解决任意多项式的求值问题解决任意多项式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5 问
10、题问题1 1:怎样求多项式怎样求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值?时的值?v2=v1x-4=55-4=21v3=v2x+3=215+3=108 方法三:方法三:能否有更好的算法能否有更好的算法,解决任意多项式的求值问题解决任意多项式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5 问题问题1 1:怎样求多项式怎样求多项式f(x)
11、=2x5-5x4-4x3+3x2-6x+7当当x=5时的值?时的值?v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534 方法三:方法三:能否有更好的算法能否有更好的算法,解决任意多项式的求值问题解决任意多项式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5 问题问题1 1:怎样求多项式怎样求多项式f(x)=2x5
12、-5x4-4x3+3x2-6x+7当当x=5时的值?时的值?v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677 方法三:方法三:能否有更好的算法能否有更好的算法,解决任意多项式的求值问题解决任意多项式的求值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5 问题问题1 1:怎样求多
13、项式怎样求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值?时的值?v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=26775次乘法运算次乘法运算,5次加法运算次加法运算秦九韶算法秦九韶算法 问题问题2 2:如何求多项式如何求多项式 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-
14、1)x+an-2)x+a1)x+a0.析:析:问题问题2 2:如何求多项式如何求多项式 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.析:析:v0v1 问题问题2 2:如何求多项式如何求多项式 f(x)=anxn+an-1xn-1+a1x+a0的值的值?f(x)=anxn+an-1xn-1+a1x+a0 =(anxn-1+an-1xn-2+a2x+a1)
15、x+a0 =(anxn-2+an-1xn-3+a2)x+a1)x+a0 =(anx+an-1)x+an-2)x+a1)x+a0.析:析:v0v1v0=anv1=v0 x+an-1 问题问题2 2:如何求多项式如何求多项式 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.析:析:v0v1v0=anv1=v0 x+an-1v2v2=v1x+an-2 问题问题2
16、 2:如何求多项式如何求多项式 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.析:析:v0v1v0=anv1=v0 x+an-1v2v2=v1x+an-2vi=vi-1+an-i 问题问题2 2:如何求多项式如何求多项式 f(x)=anxn+an-1xn-1+a1x+a0的值的值?f(x)=anxn+an-1xn-1+a1x+a0 =(anxn-1+an
17、-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.析:析:v0v1v0=anv1=v0 x+an-1v2v2=v1x+an-2vi=vi-1+an-ivn=vn-1x+a0第一步,计算第一步,计算v1=anx+an-1.第二步,计算第二步,计算v2=v1x+an-2.第第n n步,计算步,计算vn=vn-1x+a0.即:即:第第i步,计算步,计算vi=vi-1+an-i循环体循环体秦九韶法求秦九韶法求n次多项式次多项式的值需要多少次乘法,的值需要多少次乘法,多少次加法运算?多少次加法运算?
18、用秦九韶算法求多项式的值,其算法步骤如何设计?用秦九韶算法求多项式的值,其算法步骤如何设计?第一步,输入多项式的次数第一步,输入多项式的次数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
19、,x的值的值输出输出v输入输入aiv=ani0?i=n-1i=i-1v=vx+ai开始开始结束结束输入输入n,an,x的值的值输出输出v输入输入aiv=ani0?i=n-1i=i-1v=vx+aiINPUT “n=”;nINPUT “an=”;aINPUT “x=”;xv=ai=n-1WHILE i=0 PRINT “i=”;i INPUT “ai=”;a v=vx+a i=i-1WEND PRINT vEND 程序:程序:解:解:f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.v v1 1=4=45+2=225+2=22;v v2 2=22=225+3.5=113.55
20、+3.5=113.5;v v3 3=113.5=113.55-2.6=564.95-2.6=564.9;v v4 4=564.9=564.95+1.7=2826.25+1.7=2826.2;v v5 5=2826.2=2826.25-0.8=14130.2.5-0.8=14130.2.所以所以f(5)=14130.2.f(5)=14130.2.例例2 2 已知一个已知一个5 5次多项式次多项式f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8用秦九韶算法求这用秦九韶算法求这个多项式当个多项式当x=5的值的值.小结小结 评价一个算法好坏的一个重要标志是运算的次数评价一个算法好坏的一个重要标志是运算的次数.如果一个如果一个算法从理论上需要超出计算机允许范围内的运算次数,那么这样算法从理论上需要超出计算机允许范围内的运算次数,那么这样的算法就只能是一个理论算法的算法就只能是一个理论算法.在多项式求值的各种算法中,秦九韶算法是一个优秀算法在多项式求值的各种算法中,秦九韶算法是一个优秀算法.