中国古代算法案例1.ppt

1、1.3 中国古代数学中的算法案例,我国人民在长期的生活，生产和劳动过程中，创造了整数、分数、小数、正负数的概念及其运算，在代数学、几何学等方面，我国在宋，元之前也都处于世界的前列。我们在小学、中学学到的算术，代数，从记数到多元一次联立方程的求根方法，都是我国古代数学家最先创造的。更为重要的是我国古代数学的发展有着自己鲜明的特色，也就是“寓理于算”，即把解决的问题“算法化,3 5,9 15,问题1：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗,18 30,2,3,18和30的最大公约数是23=6,先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有

2、的除数连乘起来,问题2:我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数,1、求两个正整数的最大公约数的算法,我国早期也有解决求最大公约数问题的算法，就是更相减损术,更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母子之数，以少减多，更相减损，求其等也，以等数约之,翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的

3、数相等为止，则这个数（等数）就是所求的最大公约数,更相减损术,例1 用更相减损术求91与49的最大公约数,解：由于49不是偶数，把91和49以大数减小数，并辗转相减， 即：914942 49427 42735 35728 28721 21714 1477 所以，91与49的最大公约数是7,更相减损术,练习1 用更相减损术求98与63的最大公约数,解：由于63不是偶数，把98和63以大数减小数，并辗转相减,即：986335; 633528; 35287; 28721; 21714; 1477,所以，98与63的最大公约数是7,练习2：用更相减损术求两个正数84与72的最大公约数,12,我国魏晋时

4、期的数学家刘徽，他在注九章算术中采用正多边形面积逐渐逼近圆面积的算法计算圆周率，用刘徽自己的原话就是：“割之弥细，所失弥少；割之又割，以至于不可割，则与圆合体而无所失矣” ，这段注文充分说明了刘徽对极限概念. 他的思想后来又得到祖冲之的推进和发展，计算出圆周率的近似值在世界上很长时间里处于领先地位,2.刘徽割圆术,2.刘徽割圆术,一、刘徽首先指出利用=3这一数值算得的结果不是圆面积，而是圆内接正十二边形的面积，这个结果比的真值少,二、他由圆内接正六边形算起，逐渐把边数加倍，逐个算出正12边形、正24边形、正48边形、正96边形的面积，这些面积会逐渐地接近圆面积.最后求出圆面积的近似值,三、已知

5、正6边形一边（恰与半径等长)即求得正12边形边长，.由正12边形求正24边形一边之长时，刘徽反复地应用到勾股定理（或称商高、勾股定理），如图,割圆术。不断地利用勾股定理，来计算正N边形的边长,刘徽先将直径为2的圆分割为6等分，再分割成12等分，24等分，.，这样继续下去，并利用勾股定理计算其面积，从而求出圆周率的近似值，他一直计算到圆内接正192边形的面积。因为圆的半径为1，所以随着边数的增大，面积不断趋近于圆周率，这样不断计算下去，就可以得到越来越精密的圆周率近似值,祖冲之,祖冲之: （公元429-500年）是我国南北朝时期，河北省涞源县人他从小就阅读了许多天文、数学方面的书籍，勤奋好学，刻

6、苦实践，终于使他成为我国古代杰出的数学家、天文学家,圆周率是指平面上圆的周长与直径之比。早在一千四百多年以前，我国古代著名的数学家祖冲之，就精密地计算出圆的周长是它直径的3.1415926-3.1415927倍之间。这是当时世界上算得最精确的数值-圆周率,圆周率”是说一个圆的周长同它的直径有一个固定的比例。我们的祖先很早就有“径一周三”的说法，就是说，假如一个圆的直径是1尺，那它的周长就是3尺。后来，人们发现这个说法并不准确。东汉的大科学家张衡认为应该是3.162。三国到西晋时期的数学家刘徽经过计算，求出了3. 14159的圆周率，这在当时是最先进的，但是刘徽只算到这里就没有继续算。祖冲之打算

7、采用刘徽“割圆术”（在圆内做正6边形，6边形的周长刚好是直径的3倍，然后再做12边形、24边形边数越多，它的周长就和圆的周长越接近）的方法算下去。 在当时的情况下，不但没有计算机，也没有笔算，只能用长4寸，方3寸的小竹棍来计算。工作是艰巨的，这时祖冲之的儿子也能帮助他了。 父子俩算了一天又一天，眼睛熬红了，人也渐渐瘦了下来，可大圆里的边形却越画越多，3072边、6144边边数越多，边长越短。父子俩蹲在地上，一个认真地画，一个细心地算，谁也不敢走神。最后，他们在那个大圆里画出了24576边形，并计算出它的周长是3.1415926。 俩人看看摆在地上密密麻麻的小木棍，再看看画在地上的大圆里的图形，

8、高兴地笑了。 后来，祖冲之推算出，49152边形的周长不会超过3.1415927。所以，他得出结论，圆周率是在3.1415926和3.1415927这两个数之间。 祖冲之是世界上第一个计算圆周率精确到小数点后7位的人，比欧洲人早了1000多年，这是我国古代一项非常了不起的贡献,祖冲之计算得出的密率分数近似值355/113 ，外国数学家获得同样结果，已是一千多年以后的事了为了纪念祖冲之的杰出贡献，有些外国数学史家建议把叫做祖率,祖冲之在天文历法方面的成就，大都包含在他所编制的大明历及为大明历所写的驳议中,秦九韶 （公元1202-1261年）南宋，数学家。他在1247年（淳佑七年）著成数书九章十八

9、卷全书共81道题，分为九大类：大衍类、天时类、田域类、测望类、赋役类、钱谷类、营建类、军旅类、市易类。这是一部划时代的巨著，它总结了前人在开方中所使用的列筹方法，将其整齐而有系统地应用到高次方程的有理或无理根的求解上去，其中对大衍求一术一次同余组解法）和正负开方术高次方程的数值解法）等有十分深入的研究。其中的“大衍求一术”一次同余组解法），在世界数学史上占有崇高的地位,3. 秦九韶算法,秦九韶算法,设计求多项式f(x)=2x55x44x3+3x26x+7当x=5时的值的算法，并写出程序,一般的解决方案,x=5; f=2 * x5 5 * x4 4 * x3 + 3 * x2 6 * x + 7

10、; f,上述算法一共做了解15次乘法运算，5次加法运算. 优点是简单，易懂; 缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高,有没有更高效的算法,用提取公因式的方法多项式变形为,f(x)= 2x55x44x3+3x26x+7 =x4(2x5)4x3+3x26x+7 =x3(2x5)4)+3x26x+7 =(2x5)x4)x+3)x6)x+7,这样共作了5次加法，5次乘法,第二种做法与第一种做法相比,乘法的运算次数减少了,因而能提高运算效率.而且对于计算机来说,做一次乘法所需的运算时间比做一次加法要长得多,因此第二种做法能更快地得到结果,求多项式 f(x)=2x5-5x4-4x3+

11、3x2-6x+7当x=5时的值,解法一:首先将原多项式改写成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7,v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677,所以,当x=5时,多项式的值是2677,然后由内向外逐层计算一次多项式的值,即,这种求多项式值的方法就叫秦九韶算法,f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0,我们可以改写成如下形式,f(x)=(anx+an-1)x+an-2)x+a1)x+a0,求多项式的值时,首先计算最内层括号内一次多项式的值,即,v1=v0 x+an-1,然后由内向外逐层计算一次多项式的值,即,一般地,对于一个n次多项式,v2=v1x+an-2,v3=v2x+an-3,vn=vn-1x+a0,这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法,v1=v0 x+an-1,v2=v1x+an-2,v3=v2x+an-3,vn=vn-1x+a0,观察上述秦九韶算法中的n个一次式,可见vk的计算要用到vk-1的值,若令v0=an,得,