算法案例---秦九韶算法.doc

《算法案例---秦九韶算法.doc》由会员分享，可在线阅读，更多相关《算法案例---秦九韶算法.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.3算法案例-秦九韶算法高二数学组 梅 杰一.教学目标1.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质；2.能利用秦九韶算法进行一些多项式的计算，能用循环结构表示算法步骤。二教学重难点1.理解秦九韶算法体现的思想；2.用循环结构表示算法步骤。三.教学过程（一）创设情景，揭示课题问题1 ：请同学们设计一个算法，计算当时的值。学生可能会提出两种做法：做法一：把5代入多项式的每一项，计算每一项的值，然后相加；做法二：先计算x的幂，可以利用前面的计算结果，以减少计算量，即先计算x2,然后依次计算x2.x,( x2.x).x,( ( x2.x).x).x的值，再各项

2、相加。结合学生的做法，进行比较点评：有哪些优点？哪些不足？计算次数各是多少？有哪些计算种类？做法一有15次乘法运算，5次加法运算；做法二有9次乘法运算，5次加法运算对于计算机来说，做一次乘法运算所用时间要比做一次加法要长的多，所以算法好坏的一个重要标志仍然是运算的次数问题2 ：上述问题1还有没有更有效的算法呢？老师引导学生从因式分解的角度，将多项式变形为：思考：从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？x的系数依次是什么？师生一起列表表示出计算过程：原多项式x的系数423.5-2.61.7-0.8运算20110567.52824.514131+变形后x的系数

3、422113.5564.92826.214130.2*5思考：让学生回顾整个计算过程，用此种方法一共进行了多少次乘法、加法运算？点评：一共进行了5次乘法，5次加法运算，相比较前两种做法，此做法更快、更方便，而且在计算过程中，只与多项式的系数有关。这种算法就是“秦九韶算法”，在此可以介绍下秦九韶生平。【见附页】（二）研探新知问题1：怎样用秦九韶算法求一般的多项式当x=x0时的值？类似上述方法，将多项式变形为：由内向外逐层计算一次多项式的值，把n次多项式的求值问题转化为求n个一次多项式值的问题，即求：,.思考：秦九韶算法使用一般的多项式中运算的次数？运算种类？点评: 秦九韶算法使用一般的多项式的求

4、值问题.直接法乘法运算的次数最多可到达,加法最多次.秦九韶算法通过转化把乘法运算的次数减少到最多次,加法最多次.问题2：怎样用程序语言来表示秦九韶算法呢？通过观察上述秦九韶算法中的n个一次式，可见计算要用到的值，若令，我们可以得到下面的递推公式：,（k=1,2,n）这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。师生一起分三步进行： 自然语言写算法：第一步,输入多项式次数,最高次项的系数和的值.第二步,；第三步,输入次项的系数；第四步,；第五步,判断是否大于等于,若是,则返回第三步;否则,输出多项式的值.画程序框图（略）翻译成程序语言INPUT “n=”;n INPUT “an=”

5、;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（三）例题讲解例1.利用秦九韶算法计算当时的值，并统计需要多少次乘法计算和多少次加法计算？例2利用秦九韶算法计算多项式当时的值点评: 如果多项式函数中有缺项的画,要以系数为的项补齐后再计算.例3 .某城市2001年末汽车保有量为万辆,预计此后每年报废上一年末汽车保有量的,并且每年新增汽车万辆.设计算法,计算经过多少年可使汽车保有量达到万辆.将此算法用程序语言给出.解：设,经过几年的汽车保有量为,则 上述各式充分

6、说明了秦九韶算法的优点:可以通过递推关系进行迭代处理.程序为: C=0.94A=30n=0WHILE A40 A=A*C+3 n=n+1WENDPRINT nEND（四）课堂小结（五）布置作业秦九韶生平简介 南宋大数学家秦九韶 秦九韶（公元12021261），字道古，安岳人。秦九韶与李冶、杨辉、朱世杰并称宋元数学四大家。其父秦季栖，进士出身，官至上部郎中、秘书少监。秦九韶聪敏勤学。宋绍定四年（1231），秦九韶考中进士，先后担任县尉、通判、参议官、州守、同农、寺丞等职。先后在湖北、安徽、江苏、浙江等地做官，1261年左右被贬至梅州（今广东梅县），不久死于任所。他在政务之余，对数学进行虔心钻研，

7、并广泛搜集历学、数学、星象、音律、营造等资料，进行分析、研究。 宋淳祜四至七年（1244至1247），他在为母亲守孝时，把长期积累的数学知识和研究所得加以编辑，写成了闻名的巨著数学九章，并创造了“大衍求一术”。这 不仅在当时处于世界领先地位，在近代数学和现代电子计算设计中，也起到了重要作用，被称为“中国剩余定理”。他所论的“正负开方术”，被称为“秦九韶程序”。现在，世界各国从小学、中学到大学的数学课程，几乎都接触到他的定理、定律和解题原则。秦九韶在数学方面的研究成果，比英国数学家取得的成果要早800多年。安岳修建的秦九韶纪念馆，恢宏壮观，雄伟气派。秦九韶的数学成就及对世界数学的贡献主要表现在以

8、下方面：1、秦九韶的数书九章是一部划时代的巨著 秦九韶潜心研究数学多年，在湖州守孝三年，所写成的世界数学名著数学九章，癸辛杂识续集称作数学大略，永乐大典称作数学九章。全书九章十八卷，九章九类：“大衍类”、“天时类”、“田域类”、“测望类”、“赋役类”、“钱谷类”、“营建类”、“军旅类”、“市物类”，每类9题（9问）共计81题（81问），该书内容丰富至极，上至天文、星象、历律、测候，下至河道、水利、建筑、运输，各种几何图形和体积，钱谷、赋役、市场、牙厘的计算和互易。许多计算方法和经验常数直到现在仍有很高的参考价值和实践意义，被誉为“算中宝典”。该书著述方式，大多由“问曰”、“答曰”、“术曰”、“

9、草曰”四部分组成：“问曰”，是从实际生活中提出问题；“答曰”，给出答案；“术曰”，阐述解题原理与步骤；“草曰”，给出详细的解题过程。此书已为国内外科学史界公认的一部世界数学名著。此书不仅代表着当时中国数学的先进水平，也标志着中世纪世界数学的最高水平。我国数学史家梁宗巨评价道：“秦九韶的数书九章（1247年）是一部划时代的巨著，内容丰富，精湛绝伦。特别是大衍求一术（不定方程的中国独特解法）及高次代数方程的数值解法，在世界数学史上占有崇高的地位。那时欧洲漫长的黑夜犹未结束，中国人的创造却像旭日一般在东方发出万丈光芒。”2、秦九韶的“大衍求一术”，领先高斯554年，被康托尔称为“最幸运的天才” 秦九

10、韶所发明的“大衍求一术”，即现代数论中一次同余式组解法，是中世纪世界数学的最高成就，比西方1801年著名数学家高斯（Gauss，17771855年）建立的同余理论早554年，被西方称为“中国剩余定理”。秦九韶不仅为中国赢得无尚荣誉，也为世界数学作出了杰出贡献。3、秦九韶的任意次方程的数值解领先霍纳572年 秦九韶在数书九章中除“大衍求一术”外，还创拟了正负开方术，即任意高次方程的数值解法，也是中世纪世界数学的最高成就，秦九韶所发明的此项成果比1819年英国人霍纳（WGHorner，17861837年）的同样解法早572年。秦九韶的正负方术，列算式时，提出“商常为正，实常为负，从常为正，益常为负

11、”的原则，纯用代数加法，给出统一的运算规律，并且扩充到任何高次方程中去。此外，秦九韶还改进了一次方程组的解法，用互乘对减法消元，与现今的加减消元法完全一致；同时秦九韶又给出了筹算的草式，可使它扩充到一般线性方程中的解法。在欧洲最早是1559年布丢（Buteo，约14901570年，法国）给出的，他开始用不很完整的加减消元法解一次方程组，比秦九韶晚了312年，且理论上的不完整也逊于秦九韶。秦九韶还创用了“三斜求积术”等，给出了已知三角形三边求三角形面积公式，与海伦（Heron，公元50年前后）公式完全一致。秦九韶还给出一些经验常数，如筑土问题中的“坚三穿四壤五，粟率五十，墙法半之”等，即使对现在仍有现实意义。秦九韶还在十八卷77问“推计互易”中给出了配分比例和连锁比例的混合命题的巧妙且一般的运算方法，至今仍有意义。