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

中国古代数学中的算法案例 1.用两数中较大的数减去较小的数,再用差数和较小的数构成新的一对数,再用大数减小数,以同样的操作一直做下去,直到产生一对相等的数,这个数就是最大公约数. 2.古希腊求两个正整数的最大公约数的方法是:辗转相除法（欧几里得算法）用较大的数除以较小的数所得的余数和较小的数构成新的一对数,继续做上面的除法,直到大数被小数除尽,这个较小的数就是最大公约数. 导入 3.割圆术是我国魏晋时期的数学家刘徽在注《九章算术》中采用正多边形面积逐渐逼近圆面积的算法计算圆周率π的一种方法. (1)更相减损之术 所谓更相减损之术,就是对于给定的两个数,以两数中较大的数减去较小的数,然后将所得的差和较小的数构成一对新数,再用这对新数中的较大的数减去较小的数,反复执行此步骤直到差数和较小的数相等为止,此时相等的数便为原来两个数的最大公约数. 难点 所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,这时较小的数就是原来两个数的最大公约数. (2)割圆术 π是数学上最重要的常数之一,我国古代数学家在割圆术上取得了巨大的成就.通过学习割圆术,同学们可以尝试着计算π的近似值.特别将不足近似值和过剩近似值相结合,通过近似值的上下限S2nSS2n+(S2n-Sn)(n=6,12,…). 第一，从半径为1的圆内接正六边形开始，计算它的面积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不是偶数,把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 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=7×3+6=27, v2=27×3+5=86, v3=86×3+4=262, v4=262×3+3=789, v5=789×3+2=2 369, v6=2 369×3+1=7 108, v7=7 108×3=21 324, ∴f(3)=21 324. 【评析】利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写,然后由内向外逐次计算,由于后项计算需用到前项的结果,故应认真、细心,确保中间结果的准确性. 练习、设计求多项式f(x)=2x5－5x4－4x3+3x2－6x+7当x=5时的值的算法，并写出程序. 用提取公因式的方法多项式变形为 f(x)= 2x5－5x4－4x3+3x2－6x+7 =x4(2x－5)－4x3+3x2－6x+7 =x3((2x－5)－4)+3x2－6x+7