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

1、中国古代数学中的算法案例,1.用两数中较大的数减去较小的数,再用差数和较小的数构成新的一对数,再用大数减小数,以同样的操作一直做下去,直到产生一对相等的数,这个数就是最大公约数. 2.古希腊求两个正整数的最大公约数的方法是:辗转相除法（欧几里得算法）用较大的数除以较小的数所得的余数和较小的数构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是最大公约数.,导入,3.割圆术是我国魏晋时期的数学家刘徽在注九章算术中采用正多边形面积逐渐逼近圆面积的算法计算圆周率的一种方法.,(1)更相减损之术 所谓更相减损之术,就是对于给定的两个数,以两数中较大的数减去较小的数,然后将所得的差和较

2、小的数构成一对新数,再用这对新数中的较大的数减去较小的数,反复执行此步骤直到差数和较小的数相等为止,此时相等的数便为原来两个数的最大公约数.,难点,所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,这时较小的数就是原来两个数的最大公约数.,(2)割圆术 是数学上最重要的常数之一,我国古代数学家在割圆术上取得了巨大的成就.通过学习割圆术,同学们可以尝试着计算的近似值.特别将不足近似值和过剩近似值相结合,通过近似值的上下限S2nSS2n+(S2n-Sn)(n=6,12,).,第一，从半径为1的圆内接正六

3、边形开始，计算它的面积S6；,第二，逐步加倍圆内接正多边形的边数，分别计算圆内接正十二边形，正二十四边形，正四十八边形，的面积，到一定的边数（设为2m）为止，得到一列递增的数， S6，S12，S24，S48，S2m.,第三，S2m近似等于圆面积.,下面的关键是找出正n边形的面积与正2n边形的面积之间的关系，以便递推.,设圆的半径为1，正n边形的边长AB为xn，弦心距OG为hn；面积为Sn，根据勾股定理，得：,容易知道x6=1,正2n边形的面积等于正n边形的面积加上n个等腰三角形的面积，即,正2n边形的边长为,求最大公约数,例1、用更相减损之术求98和63的最大公约数. 【分析】由于63不是偶数

4、,把98和63以大数减小数,并辗转相减. 【解析】98-63=35,63-35=28,35-28=7, 28-7=14,14-7=7，所以98和63的最大公约数为7. 【评析】等值算法是当大数减去小数的差等于小数时停止减法,较小的数就是所求的最大公约数.,例2、设计程序,求两正整数m,n的最小公倍数.,解：由于m,n的最小公倍数,即为m与n的乘积除以m与n的最大公约数.因此,可先求出m与n的最大公约数,再用m.n去除以这个最大公约数即可. 程序如下:,m=input(“m=”) n=input(“n=”) S=m*n; while mn if mn m=m-n; else n=n-m; end

5、 end T= print(%io(2),T),（3）秦九韶算法 秦九韶算法是求一元n次多项式的一种算法,通过一次多项式的反复计算,逐步得出高次多项式的值,对于一个n次多项式,只需做n次乘法和n次加法即可.,例3、用秦九韶算法求多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x在x=3时的值.,【分析】明确项数与次数正确改写所给多项式从内向外逐次求值.,【解析】f(x)=(7x+6)x+5)x+4)x+3)x+2)x+1)x, v0=7，v1=73+6=27, v2=273+5=86, v3=863+4=262, v4=2623+3=789, v5=7893+2=2 369,

6、v6=2 3693+1=7 108, v7=7 1083=21 324, f(3)=21 324.,【评析】利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写,然后由内向外逐次计算,由于后项计算需用到前项的结果,故应认真、细心,确保中间结果的准确性.,练习、设计求多项式f(x)=2x55x44x3+3x26x+7当x=5时的值的算法，并写出程序.,用提取公因式的方法多项式变形为,f(x)= 2x55x44x3+3x26x+7 =x4(2x5)4x3+3x26x+7 =x3(2x5)4)+3x26x+7 =(2x5)x4)x+3)x6)x+7,解：,计算的过程可以列表表示为：,f(x)

7、=(2x5)x4)x+3)x6)x+7, x=5,中国古代数学中的算法案例学习的意义是什么? 我国古代数学中算法的内容十分丰富,成就辉煌.课本中的更相减损之术、割圆术、秦九韶算法，就是很好的代表.我国古代数学主要特征是算法化,现代信息技术的发展也使算法焕发了生机.通过本部分的学习,体会中国古代数学对世界数学发展的贡献,增强民族自豪感,努力学习,为国家的发展贡献力量.,1.学习更相减损之术与辗转相除法时,要注意两种方法的相通之处. 2.要深切体会刘徽的“割之弥细，所失弥少”的思想方法,利用正多边形面积随边数增多,逐渐逼近圆面积来计算圆周率.,课程总结,3.学习秦九韶算法时,注意通过分析秦九韶算法的运算次数,感悟算法思想的优越性和先进性,算法的关键是采用逐步提出