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

中国古代数学中的算法案例中国古代数学中的算法案例 最大公约数定定   义义l如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数几个自然数公有的约数，叫做这几个自然数的公约数公约数中最大的一个公约数，称为这几个自然数的最大公约数•更相减损术   （出自《九章算术》）求得最大公约数的方法•辗转相除法     （欧几里得算法）更相减损术简介简介l更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为为约分而设计的约分而设计的 但但它适用于任何任何需要求最大公约数的场合如何使用如何使用l求求98与与63的最大公约数的最大公约数 　　　　l 98-63=35 ，63-35=28 　　35-28=7 　　，28-7=21 　　 21-7=14 　　 ，14-7=7 　　 （98,63）→ （63,35）→ （35,28）（28,7） →（14,7） →∴98和63的最大公约数等于7 1、、求求16与与12的最大公约数的最大公约数2、求、求78与与36的最大公约数的最大公约数更相减损术步骤：更相减损术步骤：1、大数减小数；、大数减小数；2、差数和较小的数再组成数对，大数减小数；、差数和较小的数再组成数对，大数减小数；3、产生的一对相等数就是最大公约数。

产生的一对相等数就是最大公约数 得 与 有相同的公约数理论依据算法表示算法表示 lS1：：输入两个正数输入两个正数a,b(a>b) ；；lS2：：如果如果a≠b，则执行，则执行S3，否则转到，否则转到S5；；lS3：：将将a-b的值赋予的值赋予r；；lS4：：若若b>r，则把，则把b赋予赋予a，把，把r赋予赋予b，否则，否则把把            r赋予赋予a，重新执行，重新执行S2；；lS5：：输出最大公约数输出最大公约数b.输出输出bYN输入输入a,ba ≠ b结束结束开始开始a > bb=b－－aa=a－－bYN程序：程序：a=input(“a=”)；；b=input(“b=”)；；while a<>b if a>=b a=a－－b; else b=b－－a；； endendprint(%io(2), b, “两数的最大公约数为：两数的最大公约数为：” )辗转相除法辗转相除法辗转相除法l　辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年），所以它是现在仍在使用的算法中最早出现的欧几里得如何使用如何使用l以求288和123的最大公约数为例，操作如下： 　　lS1：288÷123=2……42 　　lS2：123÷42=2……39 　　lS3：42÷39=1……3 　　lS4：39÷3=13 　l（288,123）→ （123,42）→ （42,39） → （39,3） l3就是288和123的最大公约数。

这是一个辗转相处这是一个辗转相处的过程的过程……辗转相除的步骤：辗转相除的步骤：1、大数除以小数，求余数；、大数除以小数，求余数；2、用余数和较小的数组成一对，再用大数、用余数和较小的数组成一对，再用大数除以小数，求余数；除以小数，求余数；3、直到余数为、直到余数为0；；4、最后一个除数为最大公约数最后一个除数为最大公约数1、、求求98与与63的最大公约数的最大公约数2、求、求78与与36的最大公约数的最大公约数理论依据得 与 有相同的公约数  第一步第一步：输入两个正：输入两个正整数整数a，，b（（a＞＞b））; 第二步第二步：求出：求出a÷b的的余数余数r；； 第三步第三步：令：令a=b，，b=r，若，若r≠0，重复第二，重复第二步；步； 第四步第四步：输出最大公：输出最大公约数约数a.l更相减损术更相减损术和辗转相除法辗转相除法的主要区别在于: 前者所使用的运算是“减减”，后者是“除除”从算法思想上看，两者并没有本质上的区别，但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，所以辗转相除法辗转相除法更好一些。

割圆术割圆术n早在我国先秦时期，《墨经》上就已经给出了圆的定义我国古代数学经典《九章算术》在第一章“方田”章中写到“半周半径相乘得积步”，也就是我们现在所熟悉的公式n为了证明这个公式，我国魏晋时期数学家刘徽写了一篇1800余字的注记，这篇注记就是数学史上著名的“割圆术” 刘徽形容他的刘徽形容他的““割圆术割圆术””说：说：割之弥细，所失弥少，割之割之弥细，所失弥少，割之又割，以至于不可割，则与又割，以至于不可割，则与圆合体，而无所失矣圆合体，而无所失矣 简单来说所谓简单来说所谓““割圆术割圆术””，是用圆内接正多边形的，是用圆内接正多边形的周长去无限逼近圆周并以此周长去无限逼近圆周并以此求取求取圆周率圆周率的方法 计算方法计算方法n第一，从半径为第一，从半径为1 1的圆内接正六边形开始，的圆内接正六边形开始，计算它的面积计算它的面积S6S6；；n第二，逐步加倍圆内接正多边形的边数，第二，逐步加倍圆内接正多边形的边数，分别计算圆内接正十二边形，正二十四分别计算圆内接正十二边形，正二十四边形，正四十八边形，边形，正四十八边形，……的面积，到一的面积，到一定的边数（设为定的边数（设为2 2m m）为止，得到一列递）为止，得到一列递增的数，增的数， S6S6，，S12S12，，S24S24，，S48S48，，……，，S2S2n n. .n第三，第三，S2nS2n近似等于圆面积。

近似等于圆面积下面的关键是找出正下面的关键是找出正n n边形的面积与正边形的面积与正2 2n n边形的面积之间的关系，以便递推边形的面积之间的关系，以便递推设圆的半径为设圆的半径为1 1，正，正n n边形边形的边长的边长ABAB为为x xn n，弦心距，弦心距OGOG为为h hn n；面积为；面积为S Sn n，根据勾股，根据勾股定理，得：定理，得：容易知道容易知道x x6 6=1,=1, 正正2 2n n边形的面积等于正边形的面积等于正n n边形的面积加上边形的面积加上n n个等腰三个等腰三角形的面积，即角形的面积，即于是由于是由求得求得S12=3；；S24≈3.105828；；…… 按照这样的思路，刘徽把圆内接正多边形的面积一直算到了正3072边形，并由此而求得了圆周率 为3.14和 3.1416这两个近似数值这个结果是当时世界上圆周率计算的最精确的数据 n=6;x=1;s=6*sqrt(3)/4;for i=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) 程序编写 秦九韶（秦九韶（1208年－年－1261年）年）南宋官员、数学家，与李冶、杨辉、南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。

字道朱世杰并称宋元数学四大家字道古，汉族，自称鲁郡（今山东曲阜）古，汉族，自称鲁郡（今山东曲阜）人，生于普州安岳（今属四川）人，生于普州安岳（今属四川）精研星象、音律、算术、诗词、弓精研星象、音律、算术、诗词、弓剑、营造之学，历任琼州知府、司剑、营造之学，历任琼州知府、司农丞，后遭贬，卒于梅州任所，著农丞，后遭贬，卒于梅州任所，著作作《《数书九章数书九章》》，其中的大衍求一，其中的大衍求一术、三斜求积术和秦九韶算法是具术、三斜求积术和秦九韶算法是具有世界意义的重要贡献有世界意义的重要贡献  《《数书九章数书九章》》在数学内容上颇多创新中国算筹式在数学内容上颇多创新中国算筹式记数法及其演算式在此得以完整保存；自然数、分数、小数、记数法及其演算式在此得以完整保存；自然数、分数、小数、负数都有专条论述，还第一次用小数表示无理根的近似值；负数都有专条论述，还第一次用小数表示无理根的近似值；卷卷1大衍类中灵活运用最大公约数和最小公倍数，并首创连大衍类中灵活运用最大公约数和最小公倍数，并首创连环求等，借以求几个数的最小公倍数；在环求等，借以求几个数的最小公倍数；在《《孙子算经孙子算经》》中中“物不知数物不知数”问题的基础上总结成问题的基础上总结成大衍求一术大衍求一术，使一次同余式，使一次同余式组的解法规格化、程序化，比西方高斯创用的同类方法早组的解法规格化、程序化，比西方高斯创用的同类方法早500多年，被公认为多年，被公认为“中国剩余定理此外，秦九韶还改进了中国剩余定理此外，秦九韶还改进了一次方程组的解法，用互乘对减法消元，与现今的加减消元一次方程组的解法，用互乘对减法消元，与现今的加减消元法完全一致。

法完全一致已知一个一元已知一个一元n次多项式函数次多项式函数:             P(x)=anxn+an-1xn-1+……+a1x+ao当知道当知道x值时，我们可以按顺序一项一项的计算，值时，我们可以按顺序一项一项的计算，然后相加，求出然后相加，求出P(x)设有设有n+1项的项的n次函数，即：次函数，即：再将括号内的前再将括号内的前n-1项提取公因数项提取公因数x,得得:将前将前n项提取公因数项提取公因数x ，得，得:如此如此反复提取公因数反复提取公因数x    ，最后将函数化为，最后将函数化为:令令......则：则： fn即为所求即为所求怎样用怎样用程序框图程序框图表示秦九韶算法表示秦九韶算法 ？？ 观察秦九韶算法的数学模型，计算观察秦九韶算法的数学模型，计算vk时时要用到要用到fk－－1的值，若令的值，若令f0=an，我们可以得，我们可以得到下面的递推公式：到下面的递推公式：f0=anfk=fk－－1·x+an－－k (k=1, 2, …, n) 这是一个在秦九韶算法中反复执行的这是一个在秦九韶算法中反复执行的步骤，可以用步骤，可以用循环结构循环结构来实现。

来实现用秦九韶方法求多项式用秦九韶方法求多项式开开始始输入输入 x,n;a0,a1,a2,…,ank=k－－1f=f*x +ak输出输出S结束结束k=n, f=an开始开始输入输入x,n;a0,a1,a2,…,ank>0是是否否Scilab语言：语言： x=input("x="); n=input("n="); result=input("The first xishu"); for i=1 : 1 : n a=input("xishu: "); result=result*x+a; end disp(result,"The result is:"); n=input("n="); //输入多项式次数输入多项式次数a=zeros(1,n+1); //定义带下标的变量定义带下标的变量for i=1:1:n+1a(i)=input("a(i)="); //顺次输入系数顺次输入系数a0,a1,...,anendx=input("x="); //输入自变量的值输入自变量的值y=a(n+1);for i=1:1:n y=y*x+a(n+1－－i);endy 这种计算方法，称之为秦九韶方法。

直到今这种计算方法，称之为秦九韶方法直到今天，这种算法仍是世界上多项式求值的最先进的天，这种算法仍是世界上多项式求值的最先进的算法其最大的意义在于将算法其最大的意义在于将求求n次次多项式的值转化多项式的值转化为求为求n个一次多项式的值个一次多项式的值在人工计算时，利用秦在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；对九韶算法和其中的系数表可以大幅简化运算；对于计算机程序算法而言，加法比乘法的计算效率于计算机程序算法而言，加法比乘法的计算效率要高很多，所以此算法极大地缩短了要高很多，所以此算法极大地缩短了CPU运算时运算时间 谢谢观赏Thanks for listening!。