秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。在西方被称作霍纳算法。
秦九韶_秦九韶算法 -简介
秦九韶
秦九韶(约公元1202年-1261年),字道古,南宋末年人,出生于鲁郡(今山东曲阜一带人)。早年曾从隐君子学数术,后因其父往四川做官,即随父迁徙,后也认为是普州安岳(今四川安岳县)人。秦九韶与李冶、杨辉、朱世杰并称宋元数学四大家。(安岳县于1998年9月正式开工建设秦九韶纪念馆,2000年12月峻工落成。)
秦九韶聪敏勤学,宋绍定四年(公元1231),秦九韶考中进士,先后担任县尉、通判、参议官、州守等职。先后在湖北、安徽、江苏、浙江等地做官。南宋理宗景定元年(公元1260年)出任梅州守,翌年卒于梅州。据史书记载,他“性及机巧,星象、音律、算术以至营造无不精究”,还尝从李梅亭学诗词。他在政务之余,以数学为主线进行潜心钻研,且应用范围至为广泛:天文历法、水利水文、建筑、测绘、农耕、军事、商业金融等方面。
秦九韶_秦九韶算法 -数书九章
《数书九章》
宋淳祜四至七年(公元1244至1247),秦九韶在湖州为母亲守孝三年期间,把长期积累的数学知识和研究所得加以编辑,写成了举世闻名的数学巨著《数书九章》。书成后,并未出版。原稿几乎流失,书名也不确切。后历经宋、元,到明建国,此书无人问津,直到明永乐年间,在解缙主编《永乐大典》时,记书名为《数学九章》。又经过一百多年,经王应麟抄录后,由王修改为《数书九章》。
全书不但在数量上取胜,重要的是在质量上也是拔尖的。从历史上来看,秦九韶的《数书九章》可与《九章算术》相媲美;从世界范围来看,秦九韶的《数书九章》也不愧为世界数学名著。
他在《数书九章》序言中说,数学“大则可以通神明,顺性命;小则可以经世务,类万物”。所谓“通神明”,即往来于变化莫测的事物之间,明察其中的奥秘;“顺性命”,即顺应事物本性及其发展规律。在秦九韶看来,数学不仅是解决实际问题的工具,而且应该达到“通神明,顺性命”的崇高境界。
《数书九章》全书共九章九类,十八卷,每类9题共计81个算题。该书著述方式,大多由“问曰”、“答曰”、“术曰”、“草曰”四部分组成:“问曰”,是从实际生活中提出问题;“答曰”,是给出答案;“术曰”,是阐述解题原理与步骤;“草曰”,是给出详细的解题过程。另外,每类下还有颂词,词简意赅,用来记述本类算题主要内容、与国计民生的关系及其解题思路等。
秦九韶_秦九韶算法 -算法
秦九韶算法一般地,一元n次多项式的求值需要经过[n(n+1)]/2次乘法和n次加法,而秦九韶算法只需要n次乘法和n次加法。在人工计算时,一次大大简化了运算过程。特别是在现代,在使用计算机解决数学问题时,对于计算机程序算法而言秦九韶算法可以以更快的速度得到结果,减少了CPU运算时间。
在新高中课本中,秦九韶算法是必修的算法案例之一,也是高考的考点之一。这不但可以使学生体会中国古代的数学理论、数学家的高超成就,更可以使提高自身的数学素质。
秦九韶_秦九韶算法 -历史意义
该算法看似简单,其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值。在人工计算时,利用秦九韶算法和其中的系数表可以大幅简化运算;对于计算机程序算法而言,加法比乘法的计算效率要高很多,因此该算法仍有极大的意义,对于计算机来说,做一次乘法运算所用的时间比作一次加法运算要长得多,所以此算法极大地缩短了CPU运算时间。
(附:计算机程序)
INPUT“n=”;n
INPUT“an=”;a
INPUT“x=”;x
v=a
i=n-1
WHILEi>=0
PRINT“i=”;i
INPUT“ai=”;a
v=v*x+a
i=i-1
WEND
PRINTv
END
秦九韶_秦九韶算法 -算法实现
v[1]:=a[n]*k+a[n-1];
fori:=2tondo
v[i]:=v[i-1]*k+a[n-i];
writeln(v[n]);