中国古代数学中的算法案列.ppt

中国古代数学中的算法案例 最大公约数 定 义 如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。 求得最大公约数的方法 辗转相除法 （欧几里得算法） 更相减损术 （出自《九章算术》） 更相减损术 简介 更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的。 但它适用于任何需要求最大公约数的场合。 如何使用 求98与63的最大公约数。 　　 解：由于63不是偶数，把98和63以大数减小数，并辗转相减： 98-63=35 　　 63-35=28 　　 35-28=7 　　 28-7=21 　　 21-7=14 　　 14-7=7 　　 ∴98和63的最大公约数等于7。 理论依据 得 与 有相同的公约数 算法表示 S1：输入两个正数a,b(ab) ； S2：如果a≠b，则执行S3，否则转到S5； S3：将a-b的值赋予r； S4：若br，则把b赋予a，把r赋予b，否则把 r赋予a，重新执行S2； S5：输出最大公约数b. 辗转相除法 辗转相除法 　辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年），所以它是现在仍在使用的算法中最早出现的。 如何使用 以求288和123的最大公约数为例，操作如下： 　　 S1：288÷123=2……42 　　 S2：123÷42=2……39 　　 S3：42÷39=1……3 　　 S4：39÷3=13 　　 ∴ 3就是288和123的最大公约数。 理论依据 割圆术 早在我国先秦时期，《墨经》上就已经给出了圆的定义。我国古代数学经典《九章算术》在第一章“方田”章中写到“半周半径相乘得积步”，也就是我们现在所熟悉的公式。 为了证明这个公式，我国魏晋时期数学家刘徽写了一篇1800余字的注记，这篇注记就是数学史上著名的“割圆术”。 刘徽形容他的“割圆术”说：割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体，而无所失矣。 简单来说所谓“割圆术”，是用圆内接正多边形的周长去无限逼近圆周并以此求取圆周率的方法。 计算方法 第一，从半径为1的圆内接正六边形开始，计算它的面积S6； 第二，逐步加倍圆内接正多边形的边数，分别计算圆内接正十二边形，正二十四边形，正四十八边形，…的面积，到一定的边数（设为2m）为止，得到一列递增的数， S6，S12，S24，S48，…，S2n. 第三，S2n近似等于圆面积。 按照这样的思路，刘徽把圆内接正多边形的面积一直算到了正3072边形，并由此而求得了圆周率 为3.14和 3.1416这两个近似数值。这个结果是当时世界上圆周率计算的最精确的数据。 程序编写 下面的关键是找出正n边形的面积与正2n边形的面积之间的关系，以便递推。 设圆的半径为1，正n边形的边长AB为xn，弦心距OG为hn；面积为Sn，根据勾股定理，得： 容易知道x6=1, 正2n边形的面积等于正n边形的面积加上n个等腰三角形的面积，即 于是由 求得S12=3； S24≈3.105828；…… n=6; x=1; s=6*sqrt(3)/4; for i=1 : 1 : 5 h=sqrt(1－(x/2)^2); s=s+n*x*(1－h)/2; n=2*n; x=sqrt((x/2)^2+(1－h)^2); end print(%io(2), n, s) 秦九韶（1208年－1261年）南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。字道古，汉族，自称鲁郡（今山东曲阜）人，生于普州安岳（今属四川）。精研星象、音律、算术、诗词、弓剑、营造之学，历任琼州知府、司农丞，后遭贬，卒于梅州任所，著作《数书九章》，其中的大衍求一术、三斜求积术和秦九韶算法是具有世界意义的重要贡献。 《数书九章》在数学内容上颇多创新。中国算筹式记数法及其演算式在此得以完整保存；自然数、分数、小数、负数都有专条论述，还第一次用小数表示无理根的近似值；卷1大衍类中灵活运用最大公约数和最小公倍数，并首创连环求等，借以求几个数的最小公倍数；在《孙子算经》中“物不知数”问题的基础上总结成大衍求一术，使一次同余式组的解法规格化、程序化，比西方高斯创用的同类方法早500多年，被公认为“中国剩余定理此外，秦九韶还改进了一次方程组的解法，用互乘对减法消元，与现今的加减消元法完全一致。 * * * * * * * * * * * * * * * 输出b Y N 输入a,b a ≠ b 结束 开始