《中国古代数学中的算法案例》教学课件2

1.3中国古代数学中的算法案例一、复习引入下面我们举一些我国古代代数学中“算法”的例子，让同学们体会“算法”的概念，看一看中国古代数学在算法上的伟大成就。我们在小学、中学学到的算术、代数，从计数到多元一次联立方程组以及方程的求根方法，都是我国古代数学家最先创造的，有的比其他国家早几百年甚至上千年。我国人民在长期的生活、生产和劳动中，创造了很多数学的计算和思想方法。二、提出问题本节主要介绍的内容一、更相减损之术（又称“等值算法”）

----研究如何求二个正整数的最大公约数。二、割圆术

----解决圆周率π的近似值问题。三、秦九韶算法

----解决求多项式函数值问题。三、概念形成概念1：求两个正整数的最大公约数你记得在小学里是如何求最大公约数吗？对了，用短除法。例如求18和30的最大公约数：所以，18与30的最大公约数是2×3=6。这个方法可以总结为：用两个数连续除以他们的公约数，一直除到所得的商是互质数为止，然后把所有的除数连乘起来。183091535三、概念形成概念1.求两个正整数的最大公约数当两个数比较大时（如8610与6300），使用上述方法求最大公约数就比较困难。下面我们介绍两种古老而有效的算法——辗转相除法与更相减损术。（1）辗转相除法(*)例子:辗转相除法求8610和6300的最大公约数。为了简洁，我们把8610和6300的最大公约数记作（8610，6300）。把8610变为下式8610=6300×1+2310三、概念形成（被除数，除数）=（除数，余数）概念1.求两个正整数的最大公约数据此，我们可以用如下办法求8610和6300的最大公约数：被除数除数余数（8610，6300）8610=6300×1+2310=（6300，2310）6300=2310×2+1680=（2310，1680）2310=1680×1+630=（1680，630）1680=630×2+420=（630，420）630=420×1+210=（420，210）420=210×2+0=210这就是辗转相除法。由除法的性质可知，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出最大公约数。三、概念形成辗转相除法算法分析概念1.求两个正整数的最大公约数从上面例子可以看出，辗转相除法中也包含重复的操作，因此可以用循环结构来构造算法。S1：给定两个正数m，n。S2：计算m除以n所得的余数r。S3：m=n，n=r。S4：若r=0，则m，n的最大公约数等于m；否则，返回S2。r=0?n=rm=nr=mMODn输入：m，n输出：m开始结束三、概念形成辗转相除法的Siclab程序概念1.求两个正整数的最大公约数r=0?n=rm=nr=mMODn输入：m，n输出：m开始结束m=input("m=");n=input("n=");ifm<nx=m;m=n;n=x;endr=n;whiler<>0r=modulo(m,n);m=n;n=r;endprint(%io(2),m)三、概念形成概念1.求两个正整数的最大公约数（2）更相减损术《九章算术》是中国古代的数学专著，其中有这样一段论述：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。”。这是一个求最简分式的算法，可以用它来求最大公约数，我们称为“更相减损术”。翻译为现代语言如下三、概念形成概念1.求两个正整数的最大公约数（2）更相减损术第一步：任意给两个正整数，如果它们都是偶数，用2约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到它们相等为止，则这个“相等的数”就是所求的最大公约数；如果操作过程中有约分，还要在“等数”上乘以约掉的因数。三、概念形成概念1.求两个正整数的最大公约数（2）更相减损术例如：求78和36的最大公约数。解：（78，36）（6，36）（42，36）（6，30）（6，18）（6，12）（6，24）（6，6）所以，78和36的最大公约数为6。此种算法称为“等值算法”。N三、概念形成概念1.求两个正整数的最大公约数开始输入m、n输出m、nm＝nm＞nm=m-nn=n-m结束yyNm=input("m=");n=input("n=");whilem<>nifm>nm=m-n;elsen=n-m;endendprint(%io(2),m,n);（2）更相减损术三、概念形成概念2.割圆术所谓“割圆术”，是用圆内接正多边形的周长去无限逼近圆周并以此求取圆周率的方法。这个方法，是我国魏晋时期刘徽在批判总结了数学史上各种旧的计算方法之后，经过深思熟虑才创造出来的一种崭新的方法。刘徽从圆内接正六边形把圆周等分为六条弧的基础上，再继续等分，把每段弧再分割为二，做出一个圆内接正十二边形，这个正十二边形的周长不就要比正六边形的周长更接近圆周了吗？如果把圆周再继续分割，做成一个圆内接正二十四边形，那么这个正二十四边形的周长必然又比正十二边形的周长更接近圆周。三、概念形成概念2.割圆术先分析割圆术的算法oAB1Chnxn设圆O的面积为S，其内接正n边形的面积为Sn.由于D所以正2n边形的面积等于：S2n=Sn+n·xn(1-hn)/2.从而有S2n＜S＜S2n+(S2n-Sn).计算圆周率的不足近似值计算圆周率的过剩近似值三、概念形成概念2.割圆术oAB1ChnxnD割圆术的Siclab程序n=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.秦九韶算法已知求当时的函数值，要用多少次乘法，多少次加法？乘法：4+3+2+1=

。加法：

。乘法和加法的次数能减少吗？这种思想记述在我国南宋时期数学家秦九韶（约1202—1261）的代表作《数书九章》中，并总结了一套完整的算法，我们称之为秦九韶算法。直到今天这种算法仍是多项式求值比较先进的算法。三、概念形成概念3.秦九韶算法开始结束i=i-1

i=n-1输出v输入n，an，x输入ain=input("n=");an=input("an=");x=input("x=");v=an;