中国古代数学中的算法案例(上课)

《中国古代数学中的算法案例(上课)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中国古代数学中的算法案例定义如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。1.求两个正整数最大公约数的算法1.求两个正整数最大公约数的算法问题：求78和36的最大公约数。7836239183136所以：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

2、，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.输出bYN输入a,ba≠b结束开始a>bb=b－aa=a－bYN程序：a=input(“a=”)；b=input(“b=”)；whilea<>bifa>ba=a－

3、b;elseb=b－a；endendprint(%io(2),b,“两数的最大公约数为：”)辗转相除法辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年）欧几里得辗转相除法（2）98，280.（98，280）→（98，84）→（14，84）输出bb=rYN输入a,ba=br=amodbr≠0结束开始r=aModb第一步：输入两个正整数a，b（a＞b）;第二步：求出a÷b的余数r；第三步：若r≠0,令a=b，b=r，，重复第二步；若r=0，执行第四步第四步：输出最大公约数b.a=input(“a=”);b=input(“b=”);r=modu

4、lo(a,b);whiler<>0a=b;b=r;r=modulo(a,b);endb更相减损术和辗转相除法的主要区别在于:前者所使用的运算是“减”，后者是“除”。从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，所以辗转相除法更好一些。早在我国先秦时期，《墨经》上就已经给出了圆的定义。我国古代数学经典《九章算术》在第一章“方田”章中写到“半周半径相乘得积步”，也就是我们现在所熟悉的面积公式。为了证明这个公式，我国魏晋时期数学家刘徽写了一篇1800余字的注记

5、，这篇注记就是数学史上著名的“割圆术”。2．割圆术刘徽形容他的“割圆术”说：割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体，而无所失矣。简单来说所谓“割圆术”，是用圆内接正多边形的周长去无限逼近圆周并以此求取圆周率的方法。第一，从半径为1的圆内接正六边形开始，计算它的面积S6；第二，逐步加倍圆内接正多边形的边数，分别计算圆内接正十二边形，正二十四边形，正四十八边形，…的面积，到一定的边数（设为2n）为止，得到一列递增的数，S6，S12，S24，S48，…，S2n.第三，S2n近似等于圆面积。下面的关键是找出正n边形的面积与正2n边形的面积之间

6、的关系，以便递推。设圆的半径为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.14159

7、26和过剩近似值（盈数）3.1415927，指出π的真值在盈、朒两限之间，即3.1415926＜π＜3.1415927n=6;x=1;s=6*sqrt(3)/4;fori=1:1:5h=sqrt(1－(x/2)^2);s=s+n*x*(1－h)/2;n=2*n;x=sqrt((x/2)^2+(1－h)^2);endprint(%io(2),n,s)程序：3、秦九韶算法秦九韶（1208年－1261年）南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。字道古，汉族，自称鲁郡（今山东曲阜）人，生于普州安岳（今属四川）。精研星象、音律、算术、诗词、弓

8、剑、营造之学，历任琼州知府、司农丞，后遭贬，卒于梅州任所，著作《数书九章》，其中的大衍求一术、三斜求积术和秦