《中国古代数学中的算法案例》教学教案1

5/51.3中国古代数学中的算法案例学习目标1.了解中国古代数学中求两个正整数最大公约数的算法以及割圆术的算法；2.通过对“更相减损之术”及“割圆术”的学习，更好的理解将要解决的问题“算法化”的思维方法，并注意理解推导“割圆术”的操作步骤。学习重点1.改变解决问题的思路，要将抽象的数学思维转变为具体的步骤化的思维方法，提高逻辑思维能力；2.学会借助实例分析，探究数学问题。学习过程一、学习引入同学们是否知道，我们在小学、初中学到的算术、代数，从记数到多元一次联立方程组以及方程的求根方法，都是我国古代数学家最先创造的，有的比其他国家早几百年甚至上千年，我们人民在长期的生活、生产和劳动过程中，创造了整数、分数、小数、正负数及其计算，以及无限逼近任意实数的方法，在代数学、几何学方面，我国在宋、元之前也都处于世界前列，更为重要的是我国古代数学的发展有着自己鲜明的特色，走着与西方完全不同的道路，在今天看来这条道路仍然有很大的优越性。这条道路的一个重要特色就是“寓理于算”，也就是本节中所讲的要把解决问题“算法化”。下面我们举一些我国古代数学中算法的例子，让同学们更进一步体会“算法”的概念，看一看中国古代数学家的伟大成就和显著特色。下面就中国古代的数学成就，结合算法的知识，主要了解一下下面三个方面的内容：求两个正整数最大公约数的算法、割圆术和秦九韶算法。二、新知讲授（一）求两个正整数最大公约数的算法：更相减损之术我们知道，如果整数a能被整数b整除，则b称为a的一个约数，一个整数可能有好几个约数。例如，12能被1,2,3,4,6,12整除，这6个数都是12的约数。16的有1,2,4,8,16这5个约数。我们看到2和4，既是12的约数，又是16的约数，2和4叫做12和16的公约数，公约数2和4中，4最大，4称作12和16的最大公约数。如何找到一种算法，对任意两个正整数都能求出它们的最大公约数呢？下面给出我国古代数学家的一个算法，这个算法被称做“更相减损之术”。我们以求16,12这两个数的最大公约数为例加以说明。用两个数中较大的数减去较小的数，即16-12=4，用差数4和最小的数12构成新的一对数，对这一对数再用大数减小数，以同样的操作一直做下去，知道产生一对相等的数，这个数就是最大公约数。整个操作如下：4是12和16的最大公约数。这种算法的道理何在？不难看出，对任意两个数，每次操作后所得的两个数与前两数具有相同的最大公约数，而两数的值逐渐减少，经过有限步地操作后，总能得到相等的两个数，即求得两数的最大公约数。例1求78和36的最大公约数。解：这种算法，只做简单的减法，操作方便、易懂，也完全符合算法的要求，它完全是机械的运算，据此很容易编出程序，在计算机上运算，把这个算法与我们下面探索与研究中介绍的欧几里德算法比较，看看这个算法的优越性。下面是我们用Scilab编出的程序，供大家参考。实际上，你可用你在信息技术课上学到的任一种程序设计语言编出程序，从中体会一下这个算法的优越性。为了方便叙述，我们称这种算法为“等值算法”用等值算法求最大公约数的程序：a=input("pleasegivethefirstnumber");a=input("pleasegivethefirstnumber");b=input("pleasegivethesecondnumber");whilea<>bifa>ba=a-belseb=b-aendendprint(%io2(2),a,b)（二）割圆术我国魏晋时期的数学家刘徽，他在注《九章算术》中采用正多边形面积逐渐逼近圆面积的算法计算圆周率，用刘徽自己的原话就是“割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体而无所失矣。”他的思想后来又得到祖冲之的推进和发展，计算出圆周率的近似值在世界上很长时间里处于领先地位。刘徽从圆内接正六边形开始，让边数逐次加倍，逐个算出这些圆内接正多边形的面积，从而得到一系列逐渐递增的数值，来一步一步地逼近圆面积，最后求出圆周率的近似值。可以想象在当时需要付出多么艰辛的劳动，现在让我们用刘徽的思想，使用计算机求圆周率的近似值，计算机最大的特点是运算速度快，只要我们将运算规律告诉计算机，计算机会迅速得到所求的答案。我们先对单位圆内接正六边形、正十二边形、正二十四边形……的面积之间的关系进行分析，找出它们之间的递增规律。例2假设圆的半径为1，面积为S，圆内接正n边形面积为，边长为，边心距为，根据勾股定理，。正2n边形的面积为正n边形的面积再加上n个等腰三角形的面积和，即①正2n边形的边长为。刘徽割圆术还注意到，如果在内接n边形的每一边上，做一高为CD的矩形，就可得到这样我们就不仅可计算出圆周率的不足近似值，还可计算出圆周率的过剩近似值。正六边形的面积开始计算，即n=6，则正六边形的面积。用上面的公式①重复计算，就可得到正十二边形、正二十四边形……的面积。因为圆的半径为1，所以随着n的增大，的值不断趋近于圆周率，这样不断计算下去，就可以得到越来越精密的圆周率近似值。下面我们根据刘徽割圆术的算法思想，用Scilsb语言写出求的不足近似值程序：（三）秦九韶算法例3已知一个一元n次多项式函数，当，我们可按顺序一项一项地计算，然后相加，求得。下面看看我们宋代（约13世纪）大数学家秦九韶是如何计算多项式函数值的。让我们以5次多项式函数为例加以说明。设首先，我们把这个多项式一步一步的进行改写：上面的分层计算，只用了小括号，计算时，首先计算最内层的括号，然后由内向外逐层计算，知道最外层的一个括号，然后加上常数项。这种算法与直接算法比较，有什么有什么优越性呢？首先，这种算法一共做了5次乘法，5次加法，与直接计算相比较大大节省了乘法的次数，是计算量减少，并且逻辑结构简单。对任意一元n次多项式，类似的叙述如下：上面的方法，现在大家称它为秦九韶方法。直到今天，这种算法仍是世界上多项式求值的最先进的算法。这种方法的计算量仅为：乘法n次，加法n次。我们看看其他算法的计算量。用直接求和法，直接计算多项式各项的值，然后把他们相加。可知乘法的次数为，加法次数为n。逐项求和在直接求和法的基础上做了改进，先把多项式写成的形式，这样多项式的每一含x的幂的项都是与的乘积（k=1,2,3，……，n），在计算项时把的值保存在变量c中，求项时只须计算，同时把的值存入c中，继续下一项的运算，然后把这n+1项的值相加。容易看出逐项求和法所用乘法的次数为2n-