1.3中国古代数学中的算法案例第一章算法初步一、复习引入下面我们举一些我国古代代数学中“算法”的例子，让同学们体会“算法”的概念，看一看中国古代数学在算法上的伟大成就。我们在小学、中学学到的算术、代数，从计数到多元一次联立方程组以及方程的求根方法，都是我国古代数学家最先创造的，有的比其他国家早几百年甚至上千年。我国人民在长期的生活、生产和劳动中，创造了很多数学的计算和思想方法。二、提出问题本节主要介绍的内容一、更相减损之术（又称“等值算法”）----研究如何求二个正整数的最大公约数。二、割圆术----解决圆周率π的近似值问题。三、秦九韶算法----解决求多项式函数值问题。三、概念形成概念1.求两个正整数的最大公约数你记得在小学里是如何求最大公约数吗？21830391535对了，用短除法。例如求18和30的最大公约数：所以，18与30的最大公约数是2×3=6。这个方法可以总结为：用两个数连续除以他们的公约数，一直除到所得的商是互质数为止，然后把所有的除数连乘起来。三、概念形成概念1.求两个正整数的最大公约数当两个数比较大时（如8610与6300），使用上述方法求最大公约数就比较困难。下面我们介绍两种古老而有效的算法——辗转相除法与更相减损术。（1）辗转相除法(*)例子:辗转相除法求8610和6300的最大公约数。为了简洁，我们把8610和6300的最大公约数记作（8610，6300）。把8610变为下式8610=6300×1+2310三、概念形成概念1.求两个正整数的最大公约数我们来看一下（8610，6300）和（6300，2310）之间的关系28610630034305310551435105072872104130263002310331051155510503857210773011它们有相同的公约数，因此也有相同的最大公约数。难道这只是巧合吗?可以证明它们有相同的公约数（略）。三、概念形成我们可以总结为：（被除数，除数）=（除数，余数）概念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?YesNon=rm=nr=mMODn输入：m，n输出：m开始结束三、概念形成辗转相除法的Siclab程序概念1.求两个正整数的最大公约数r=0?YesNon=rm=nr=mMODn输入：m，n输出：m开始结束m=input("m=");n=input("n=");ifm0r=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("...
