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

中国古代数学中的算法案例 中国古代数学中的算法案例最大公约数中国古代数学中的算法案例定定   义义l如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数几个自然数公有的约数，叫做这几个自然数的公约数公约数中最大的一个公约数，称为这几个自然数的最大公约数中国古代数学中的算法案例•更相减损术   （出自《九章算术》）求得最大公约数的方法•辗转相除法     （欧几里得算法）中国古代数学中的算法案例更相减损术中国古代数学中的算法案例简介简介l更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为为约分而设计的约分而设计的 但但它适用于任何任何需要求最大公约数的场合中国古代数学中的算法案例如何使用如何使用l求求98与与63的最大公约数的最大公约数 　　　　l解：解：由于63不是偶数，把98和63以大数减小数，并辗转相减：l 98-63=35 　　63-35=28 　　35-28=7 　　28-7=21 　　21-7=14 　　14-7=7 　　∴98和63的最大公约数等于7 中国古代数学中的算法案例 得 与 有相同的公约数理论依据中国古代数学中的算法案例算法表示算法表示 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 　　 ∴ 3就是288和123的最大公约数这是一个辗转相处的过程……中国古代数学中的算法案例理论依据得 与 有相同的公约数 中国古代数学中的算法案例 第一步第一步：输入两个正：输入两个正整数整数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!中国古代数学中的算法案例。