中国古代数学中的算法案例.pptVIP

* 中国古代数学中的算法案例 定义 如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。 1. 求两个正整数最大公约数的算法 1. 求两个正整数最大公约数的算法 问题：求78和36的最大公约数。 78 36 2 39 18 3 13 6 所以：78和36的最大公约数是2×3=6 思考： 假设a和b的最大公约数p，那么a-b，或是b-a是否能被p整除？ 例如，求78和36的最大公约数： (78，36) → (42，36) → (6，36) → (6，30) → (6，24) → (6，18) → (6，12) → (6，6). 所以：78和36的最大公约数是6 理论依据：由a－b=r → a=b+r，得(a, b)与(b, r)有相同的公约数. 更相减损术 等值算法 简介 更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的。 但它适用于任何需要求最大公约数的场合。 例1 ：用等值算法（更相减损术）求下列两数的最大公约数。 （1）225，135； （2）98，280. 答案: (1) 45; (2) 14. 输出b Y N 输入a,b a ≠ b 结束 开始 a b b=b－a a=a－b Y N 程序： a=input(“a=”)； b=input(“b=”)； while ab if ab a=a－b; else b=b－a； end end print(%io(2), b, “两数的最大公约数为：” ) 辗转相除法 　辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年） 欧几里得 辗转相除法 （2）98，280. （98，280）→（98，84） →（14，84） 输出b b=r Y N 输入a,b a=b r=a mod b r ≠ 0 结束 开始 r = a Mod b 第一步：输入两个正整数a，b（a＞b）; 第二步：求出a÷b的余数r； 第三步：若r≠0,令a=b，b=r，，重复第二步；若r=0，执行第四步 第四步：输出最大公约数b. a=input(“a=”); b=input(“b=”); r=modulo(a,b); while r0 a=b; b=r; r=modulo(a,b); end b 更相减损术和辗转相除法的主要区别在于: 前者所使用的运算是“减”，后者是“除”。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，所以辗转相除法更好一些。 早在我国先秦时期，《墨经》上就已经给出了圆的定义。我国古代数学经典《九章算术》在第一章“方田”章中写到“半周半径相乘得积步”，也就是我们现在所熟悉的面积公式。 为了证明这个公式，我国魏晋时期数学家刘徽写了一篇1800余字的注记，这篇注记就是数学史上著名的“割圆术”。 2．割圆术 刘徽形容他的“割圆术”说：割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体，而无所失矣。 简单来说所谓“割圆术”，是用圆内接正多边形的周长去无限逼近圆周并以此求取圆周率的方法。 第一，从半径为1的圆内接正六边形开始，计算它的面积S6； 第二，逐步加倍圆内接正多边形的边数，分别计算圆内接正十二边形，正二十四边形，正四十八边形，…的面积，到一定的边数（设为2n）为止，得到一列递增的数， S6，S12，S24，S48，…，S2n. 第三，S2n近似等于圆面积。 下面的关键是找出正n边形的面积与正2n边形的面积之间的关系，以便递推。 设圆的半径为1，正n边形的边长AB为xn，弦心距OG为hn；面积为Sn，根据勾股定理，得： 容易知道x6=1, 正2n边形的面积等于正n边形的面积加上n个等腰三角形的面积，即 正2n边形的边长为 于是由 求得S12=3； S24≈3.105828；…… 按照这样的思路，刘徽把圆内接正多边形的面积一直算到了正3072边形，并由此而求得了圆周率 为3.14和 3.1416这两个近似数值。这个结果是当时世界上圆周率计算的最精确的数据。 祖冲之（429～500） 南北朝时期杰出的数学家和天文学家，在数学方面，祖冲之推算出圆周率π的不足近似值（朒数）3.1415926和过剩近似值（盈数）3.1415927，指出π的真值在盈、朒两限之间，即3.1415926＜π＜3.141592