高中数学 第一章 算法初步 13 中国古代数学中的算法案例课件 新人教B版必修3 课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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.,割圆术,所谓,“,割圆术,”,，是,用圆内接正多边形的周长去无限逼近圆周并以此求取圆周率的方法。,这个方法，是我国魏晋时期刘徽在批判总结了数学史上各种旧的计算方法之后，经过深思熟虑才创造出来的一种崭新的方法。,刘徽从圆内接正六边形把圆周等分为六条弧的基础上，再继续等分，把每段弧再分割为二，做出一个圆内接正十二边形，这个正十二边形的周长不就要比正六边形的周长更接近圆周了吗？如果把圆周再继续分割，做成一个圆内接正二十四边形，那么这个正二十四边形的周长必然又比正十二边形的周长更接近圆周。,三、概念形成,概念,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,次乘法即可。计算过程大大简化。对于计算机来说，做一次乘法运算所用的时间比一次加法运算要长的多，所以减少乘法运算次数，计算机能更快的得到结果。,三、概念形成,概念,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,、用秦九韶算法求多项式,f,（,x,）,=2+0.35,x,+1.8,x,2,3.66,x,3,+6,x,4,5.2,x,5,+,x,6,在,x,=,1.3,的值时，令,v,0,=,a,6,；,v,1,=,v,0,x,+,a,5,；,；,v,6,=,v,5,x,+,a,0,时，,v,3,的值为（）,A.,9.8205 B.14.25C.,22.445 D.30.9785,C,2.,数,4557,、,1953,、,5115,的最大公约数是（）,A.31B.93C.217D.651,B,3.,用等值算法求下列各数的最大公约数,.,（,1,）,63,，,84,；（,2,）,351,，,513.,答案：,(1),21 (2)27,4.,用辗转相除法求下列各数的最大公约数,.,（,1,）,5207,，,8323,；（,2,）,5671,，,10759.,答案：,（,1,）,41,（,2,）,53,6.,用秦九韶算法求多项式 在 时的值,.,5.,求三个数,779,，,209,，,589,的最大公约数,.,144468,19,六、课堂总结,重点是理解中国古代的三个问题的算法，难点是为算法编写程序。,理解并掌握,更相减损术,求两个正整数的最大公约数的步骤及,秦九韶算法,的计算过程。,