13中国古代数学中的算法案例

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,良乡中学数学组 任宝泉,书 山 有 路 勤 为 径，学 海 无 崖 苦 作 舟,少 小 不 学 习，老 来 徒 伤 悲,成功,=,艰苦的劳动,+,正确的方法,+,少谈空话,天才就是百分之一的灵感，百分之九十九的汗水！,天 才 在 于 勤 奋，努 力 才 能 成 功！,勤劳的孩子展望未来,但懒惰的孩子享受现在,!,什 么 也 不 问 的 人 什 么 也 学 不 到,!,1.3中国古代数学中的算法案例,一、复习引入,下面我们举一些我国古代代数学中,“,算法,”,的例子，让同学们体会,“,算法,”,的概念，看一看中国古代数学在算法上的伟大成就。,我们在小学、中学学到的算术、代数，从计数到多元一次联立方程组以及方程的求根方法，都是我国古代数学家最先创造的，有的比其他国家早几百年甚至上千年。我国人民在长期的生活、生产和劳动中，创造了很多数学的计算和思想方法。,二、提出问题,本节主要介绍的内容,一、更相减损之术（又称,“,等值算法,”,）,-,研究如何求二个正整数的最大公约数。,二、割圆术,-,解决圆周率,的近似值问题。,三、秦九韶算法,-,解决求多项式函数值问题。,三、概念形成,概念,1.,求两个正整数的最大公约数,你记得在小学里是如何求最大公约数吗？,对了，用短除法。例如求,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,）之间的关系,它们有相同的公约数，因此也有相同的最大公约数。难道这只是巧合吗,?,可以证明它们有相同的公约数（略）。,三、概念形成,我们可以总结为：,（被除数，除数）,=,（除数，余数）,概念,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.,求两个正整数的最大公约数,从上面例子可以看出，辗转相除法中也包含重复的操作，因此可以用循环结构来构造算法。,S,1,：给定两个正数,m,，,n,。,S,2,：计算,m,除以,n,所得的余数,r,。,S,3,：,m=n,，,n=r,。,S,4,：若,r=0,，则,m,，,n,的最大公约数等于,m,；否则，返回,S2,。,r=0?,n,=r,m,=n,r,=,m,MOD,n,输入：,m,，,n,输出：,m,开始,结束,三、概念形成,辗转相除法的,Siclab,程序,概念,1.,求两个正整数的最大公约数,r=0?,n,=r,m,=n,r,=,m,MOD,n,输入：,m,，,n,输出：,m,开始,结束,m=input(m=);,n=input(n=);,if mn,m=m-n;,else,n=n-m;,end,end,print(%io(2),m,n);,（,2,）更相减损术,三、概念形成,概念,2.,割圆术,所谓,“,割圆术,”,，是,用圆内接正多边形的周长去无限逼近圆周并以此求取圆周率的方法,。这个方法，是我国魏晋时期刘徽在批判总结了数学史上各种旧的计算方法之后，经过深思熟虑才创造出来的一种崭新的方法。,刘徽从圆内接正六边形把圆周等分为六条弧的基础上，再继续等分，把每段弧再分割为二，做出一个圆内接正十二边形，这个正十二边形的周长不就要比正六边形的周长更接近圆周了吗？如果把圆周再继续分割，做成一个圆内接正二十四边形，那么这个正二十四边形的周长必然又比正十二边形的周长更接近圆周。,按照这样的思路，刘徽把圆内接正多边形的面积一直算到了正,3072,边形，并由此而求得了圆周率 为,3.14,和,3.1416,这两个近似数值。这个结果是当时世界上圆周率计算的最精确的数据。刘徽对自己创造的这个,“,割圆术,”,新方法非常自信，把它推广到有关圆形计算的各个方面，从而使汉代以来的数学发展大大向前推进了一步。,可以想象，在当时需要付出多么艰辛的劳动。现在让我们用刘徽的思想，使用计算机求圆周率的近似值。计算机的最大特点是运算速度快，只要我们将运算方法告诉计算机，计算机会迅速得到所求的答案。,三、概念形成,概念,2.,割圆术,先分析割圆术的算法,o,A,B,1,C,h,n,x,n,设圆,o,的面积为,S,，其内接正,n,边形的面积为,S,n,.,由于,D,所以正,2n,边形的面积等于：,S,2n,=S,n,+n,x,n,(1-h,n,)/2.,从而有,S,2n,S,S,2n,+(S,2n,-S,n,).,计算圆周率的不足近似值,计算圆周率的过剩近似值,三、概念形成,概念,2.,割圆术,o,A,B,1,C,h,n,x,n,D,割圆术的,Siclab,程序,n=6;,x=1;,s=6*sqrt(3)/4;,for i=1:1:5,h=sqrt(1-(x/2)2);,s=s+n*x*(1-h)/2;,n=2*n;,x=sqrt(x/2)2+(1-h)2);,end,print(%io(2),n,s);,由于,三、概念形成,概念,3.,秦九韶算法,已知 求当 时的函数值，要用多少次乘法，多少次加法？,乘法：,4+3+2+1=,。,加法：,。,乘法和加法的次数能减少吗？,聪明的同学们一定想到了，如果我们计算出了,x,2,，当我们计算,x,3,时根本不用从头算起，利用,x,2,用一次乘法就可以算出,x,3,了。同理,x,4,可由,x,3,算出，,x,5,可由,x,4,算出，这样我们只用了,4,次乘法即可。计算过程大大简化。对于计算机来说，做一次乘法运算所用的时间比一次加法运算要长的多，所以减少乘法运算次数，计算机能更快的得到结果。,这种思想记述在我国南宋时期数学家,秦九韶,（约,1202,1261,）的代表作,数书九章,中，并总结了一套完整的算法，我们称之为,秦九韶算法,。直到今天这种算法仍是多项式求值比较先进的算法。,三、概念形成,概念,3.,秦九韶算法,比如一个,5,次多项式为 求当 时的函数值，要用多少次乘法，多少次加法？,分析：用刚才的方法，计算 共用,4,次乘法，乘上它们的系数需要,5,次乘法，共需要,9,次乘法和,5,次加法。,还有更快速的,算法,吗？,三、概念形成,概念,3.,秦九韶算法,比如一个,5,次多项式为 求当 时的函数值，要用多少次乘法，多少次加法？,解：原式可化为,先计算最内层括号里 的值，然后由内向外逐层计算。,多项式的系数分别为：,三、概念形成,概念,3.,秦九韶算法,比如一个,5,次多项式为 求当 时的函数值，要用多少次乘法，多少次加法？,多项式的系数分别为：,共用了,5,次乘法和,5,次加法，减少了,4,次乘法。,三、概念形成,概念,3.,秦九韶算法,用秦九韶算法求,n,次多项式,的值时，需要,n,次乘法运算，,n,次加法运算，共,2n,次运算。,三、概念形成,概念,3.,秦九韶算法,开始,结束,i=i-1,i=n-1,输出,v,输入,n,，,a,n,，,x,输入,a,i,n=,input(n,=);,an=,input(an,=);,x=,input(x,=);,v=an;,i=n-1;,while i=0,print(%io(2),i),a=,input(ai,=);,v=v*,x+a;i,=i-1;,end,print(%io(2),v),用秦九韶算法框图及程序,四、应用举例,例,1.,用更相减损术求,132,与,143,的最大公约数,（,132,，,143,）,（,132,，,11,）,（,121,，,11,）,（,110,，,11,）,（,99,，,11,）,（,88,，,11,）,（,77,，,11,）,（,66,，,11,）,（,55,，,11,）,（,44,，,11,）,（,33,，,11,）,（,22,，,11,）,（,11,，,11,）,故，,132,与,143,的最大公约数是,11,。,思考：用辗转相除法求下列两数的最大公约数。,（,1,）,8251,，,6105,（,2,）,1480,，,480,四、应用举例,例,2.,用秦九韶算法求多项式 在,x=2,时的函数值，并用循环语句写出算法。,算法程序可参照前面的秦九韶算法程序。,五、课堂练习,思考,?,1.,某班有,41,名学生，设计一个算法，输入每个学生的数学成绩后，分别统计在区间,0,60).60,80),80,100,内成绩的个数，用自然语言描述算法步骤，写出此算法的框图并用,Siclab,语言写出该算法的程序。,课本第,32,页，习题,1-3A,，,1,，,2,，,3,，,4,六、课堂总结,重点是理解中国古代的三个问题的算法，难点是为算法编写程序。,理解并掌握,更相减损术,求两个正整数的最大公约数的步骤及,秦九韶算法,的计算过程。,七、布置作业,课本第,32,页，习题,1-3A,，,1,，,2,，,3,，,4,弹性作业：课本,32,页，习题,1-3 B,良乡中学数学组,下课,