《中国古代数学中的算法案例ppt课件》由会员分享，可在线阅读，更多相关《中国古代数学中的算法案例ppt课件（37页珍藏版）》请在金锄头文库上搜索。
1、中国古代数学中的算法案例 最大公约数定定义义l假设有一个自然数a能被自然数b整除，那么称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。更相减损术 出自求得最大公约数的方法辗转相除法 欧几里得算法更相减损术简介简介l更相减损术是出自的一种求最大公约数的算法，它本来是为约分而设计的。l 但它适用于任何需求求最大公约数的场所。如何运用如何运用l求求98与与63的最大公的最大公约数。数。l解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小以大数减小数，并数，并辗转相减：相减：l98-63=35l63-
2、35=28l35-28=7l28-7=21l21-7=14l14-7=7l98和和63的最大公的最大公约数等于数等于7。 得 与 有一样的公约数实际根据算法表示算法表示lS1：输入两个正数a,b(ab) ；lS2：假设ab，那么执行S3，否那么转到S5；lS3：将a-b的值赋予r；lS4：假设br，那么把b赋予a，把r赋予b，否那么把l r赋予a，重新执行S2；lS5：输出最大公约数b.输出输出b bYN输入输入a,ba,ba b终了了开开场a bb=baa=abYN程序：程序：a=input(“a=)；b=input(“b=)；while ab if a=b a=ab; else b=ba；
3、 endendprint(%io(2), b, “两数的最大公两数的最大公约约数数为为： )辗转相除法辗转相除法辗转相除法l辗转相除法最早出如今欧几里得的几何本来中大约公元前300年，所以它是如今仍在运用的算法中最早出现的。欧几里得如何运用如何运用l以求288和123的最大公约数为例，操作如下： lS1：288123=242 lS2：12342=239 lS3：4239=13 lS4：393=13 l 3就是288和123的最大公约数。这是一个辗转相处的过程实际根据得 与 有一样的公约数 第一步：第一步：输入两个正入两个正整数整数a，bab; 第二步：求出第二步：求出ab的的余数余数r； 第三
4、步：令第三步：令a=b，b=r，假，假设r0，反复，反复第二步；第二步； 第四步：第四步：输出最大公出最大公约数数a.l更相减更相减损术和和辗转相除法的主要区相除法的主要区别在在于于:l前者所运用的运算是前者所运用的运算是“减，后者是减，后者是“除。从算法思想上看，两者并没有本除。从算法思想上看，两者并没有本质上的区上的区别，但是在，但是在计算算过程中，假程中，假设遇到一个数很大，另一个数比遇到一个数很大，另一个数比较小的情小的情况，能况，能够要要进展很多次减法才干到达一展很多次减法才干到达一次除法的效果，所以次除法的效果，所以辗转相除法更好一相除法更好一些。些。割割圆术圆术n早在我国先秦时期
5、，上就曾经给出了圆的定义。我国古代数学经典在第一章“方田章中写到“半周半径相乘得积步，也就是我们如今所熟习的公式。n为了证明这个公式，我国魏晋时期数学家刘徽写了一篇1800余字的注记，这篇注记就是数学史上著名的“割圆术。 刘徽描画他的刘徽描画他的“割割圆术说：割之弥：割之弥细，所失，所失弥少，割之又割，以致弥少，割之又割，以致于不可割，那么与于不可割，那么与圆合合体，而无所失矣。体，而无所失矣。 简单来来说所所谓“割割圆术，是用，是用圆内接正多内接正多边形的周形的周长去无限逼近去无限逼近圆周并以此求取周并以此求取圆周率周率的方法。的方法。 计算方法计算方法n第一，从半径第一，从半径为1 1的的
6、圆内接正六内接正六边形开形开场，计算它的面算它的面积S6S6；n第二，逐第二，逐渐加倍加倍圆内接正多内接正多边形的形的边数，数，分分别计算算圆内接正十二内接正十二边形，正二十四形，正二十四边形，正四十八形，正四十八边形，形，的面的面积，到一，到一定的定的边数数设为2m2m为止，得到一列止，得到一列递增的数，增的数， n S6 S6，S12S12，S24S24，S48S48，S2n.S2n.n第三，第三，S2nS2n近似等于近似等于圆面面积。下面的关键是找出正下面的关键是找出正n n边形的面积与正边形的面积与正2n2n边形的面积之间的关系，以便递推。边形的面积之间的关系，以便递推。设圆的半径的半
7、径为1 1，正，正n n边形形的的边长ABAB为xnxn，弦心距，弦心距OGOG为hnhn；面；面积为SnSn，根据勾，根据勾股定理，得：股定理，得：容易知道容易知道x6=1,x6=1, 正正2n2n边形的面形的面积等于正等于正n n边形的面形的面积加上加上n n个等腰三个等腰三角形的面角形的面积，即，即于是由于是由求得求得S12=3；S243.105828； 按照这样的思绪，刘徽把圆内接正多边形的面积不断算到了正3072边形，并由此而求得了圆周率 为3.14和 3.1416这两个近似数值。这个结果是当时世界上圆周率计算的最准确的数据。 n=6;x=1;s=6*sqrt(3)/4;for i=
8、1 : 1 : 5h=sqrt(1(x/2)2);s=s+n*x*(1h)/2;n=2*n;x=sqrt(x/2)2+(1h)2);endprint(%io(2), n, s) 程序编写 秦九韶秦九韶1208年年1261年年南宋官员、数学家，与李冶、杨辉、南宋官员、数学家，与李冶、杨辉、朱世杰并称宋元数学四大家。字道朱世杰并称宋元数学四大家。字道古，汉族，自称鲁郡今山东曲阜古，汉族，自称鲁郡今山东曲阜人，生于普州安岳今属四川。人，生于普州安岳今属四川。精研星象、音律、算术、诗词、弓精研星象、音律、算术、诗词、弓剑、营造之学，历任琼州知府、司剑、营造之学，历任琼州知府、司农丞，后遭贬，卒于梅州任
9、所，著农丞，后遭贬，卒于梅州任所，著作作，其中的大衍求一，其中的大衍求一术、三斜求积术和秦九韶算法是具术、三斜求积术和秦九韶算法是具有世界意义的重要奉献。有世界意义的重要奉献。 在数学内容上在数学内容上颇多多创新。中国算筹式新。中国算筹式记数法数法及其演算式在此得以完好保管；自然数、分数、小数、及其演算式在此得以完好保管；自然数、分数、小数、负数数都有都有专条条论述，述，还第一次用小数表示无理根的近似第一次用小数表示无理根的近似值；卷；卷1大衍大衍类中灵敏运用最大公中灵敏运用最大公约数和最小公倍数，并首数和最小公倍数，并首创连环求求等，借以求几个数的最小公倍数；在等，借以求几个数的最小公倍数；
10、在中中“物不知物不知数数问题的根底上的根底上总结成大衍求一成大衍求一术，使一次同余式，使一次同余式组的解的解法法规格化、程序化，比西方高斯格化、程序化，比西方高斯创用的同用的同类方法早方法早500多年，多年，被公以被公以为“中国剩余定理此外，秦九韶中国剩余定理此外，秦九韶还改良了一次方程改良了一次方程组的的解法，用互乘解法，用互乘对减法消元，与减法消元，与现今的加减消元法完全一致。今的加减消元法完全一致。知一个一元知一个一元n次多次多项式函数式函数:P(x)=anxn+an-1xn-1+a1x+ao当知道当知道x值时，我们可以按顺序一项一项的计算，值时，我们可以按顺序一项一项的计算，然后相加，
11、求出然后相加，求出P(x)设有设有n+1项的项的n次函数，即：次函数，即：再将括号内的前再将括号内的前n-1项提取公因数项提取公因数x,得得:将前将前n项提取公因数提取公因数x，得，得:如此反复提取公因数如此反复提取公因数x，最后将函数化，最后将函数化为:令令.那么：那么：fn即为所求即为所求怎怎样用程序框用程序框图表示秦九韶算法表示秦九韶算法 ？ 察看秦九韶算法的数学模型，察看秦九韶算法的数学模型，计算算vk时要用到要用到fk1的的值，假，假设令令f0=an，我，我们可可以得到下面的以得到下面的递推公式：推公式：f0=anfk=fk1x+ank (k=1, 2, , n) 这是一个在秦九韶算
12、法中反复是一个在秦九韶算法中反复执行的行的步步骤，可以用循，可以用循环构造来构造来实现。开开场场输入输入 x,n;a0,a1,a2,ank=k1f=f*x +ak输出输出S终了了k=n, f=an开开场输入输入x,n;a0,a1,a2,ank0是是否否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=); /输输入多
13、入多项项式次数式次数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+1i);endy 这种计算方法，称之为秦九韶方法。直到今这种计算方法，称之为秦九韶方法。直到今天，这种算法仍是世界上多项式求值的最先进的天，这种算法仍是世界上多项式求值的最先进的算法。其最大的意义在于将求算法。其最大的意义在于将求n次多项式的值转化次多项式的值转化为求为求n个一次多项式的值。在人工计算时，利用秦个一次多项式的值。在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；对九韶算法和其中的系数表可以大幅简化运算；对于计算机程序算法而言，加法比乘法的计算效率于计算机程序算法而言，加法比乘法的计算效率要高很多，所以此算法极大地缩短了要高很多，所以此算法极大地缩短了CPU运算时运算时间。间。 谢谢欣赏Thanks for listening!
