中国古代数学中 的算法案例（一）ppt课件

1、1.3中国古代数学中中国古代数学中 的算法案例一的算法案例一 1. 求两个正整数最大公约数的算法求两个正整数最大公约数的算法 辗转相除法辗转相除法 求两个数的最大公约数，其根本步骤求两个数的最大公约数，其根本步骤 是带余除法是带余除法m=nq+r0rn， 反复执行，直到余数反复执行，直到余数r=0为止为止. 求恣意两个数的最大公约数的算法是求恣意两个数的最大公约数的算法是 第一步：输入两个第一步：输入两个 正整数正整数a，bab; 第二步：求出第二步：求出ab的的 余数余数r； 第三步：令第三步：令a=b， b=r，假设，假设r0，反复，反复 第二步；第二步； 第四步：输出最大第四步：输出最大

2、 公约数公约数a. 举例阐明举例阐明. m=90，n=36， m=2n+18，r=18. 令令m=36， n=18. 又有又有36=182， 即即m=2n， 此时此时r=0. 令令m=18，n=0. 故最大公约数为故最大公约数为18. 算理：算理： 先找到先找到a,b中较大的，中较大的， 记为记为a； a=btc； 假设假设c0,记记a=b, b=c, 前往第前往第2步进展循环；步进展循环； 假设假设c=0，输出，输出b. 输出输出b b b=c Y N 输入输入a,ba,b a=b c=a mod b c 0 终了终了 开开 场场 c = a Mod b a=input(“a=); b=in

3、put(“b=); c=modulo(a,b); while c0 a=b; b=c; c=modulo(a,b); end b 更相减损术更相减损术 以两数中较大的数减去较小的数，即以两数中较大的数减去较小的数，即78 3642；以差数；以差数42和较小的数和较小的数36构成新构成新 的一对数；的一对数； 对这一对数再用大数减去小数，即对这一对数再用大数减去小数，即42 366，再以差数，再以差数6和较小的数和较小的数36构成新的构成新的 一对数；一对数； 对这一对数再用大数减去小数，即对这一对数再用大数减去小数，即36 630，再构成新的一对数；，再构成新的一对数； 例如，求例如，求78和

4、和36的最大公约数：的最大公约数： 继续这一过程继续这一过程,直到产生一对相等的数，直到产生一对相等的数， 这个数就是最大公约数这个数就是最大公约数. 操作如下：操作如下： (78，36) (42，36) (6，36) (6，30) (6，24) (6，18) (6，12) (6，6). 实际根据：实际根据： 由由ab=r a=b+r，得，得(a, b)与与(b, r)有一有一 样的公约数样的公约数. 算法如下：算法如下： S1输入两个正数输入两个正数a, b (ab)； S2假设假设ab，那么执行，那么执行S3，否那么转到，否那么转到 S5； S3 将将ab的值赋予的值赋予r； S4 假设假

5、设br，那么把，那么把b赋予赋予a，把，把r赋予赋予b， 否那么把否那么把r赋予赋予a，重新执行，重新执行S2； S5 输出最大公约数输出最大公约数 输出输出b b Y N 输入输入a,ba,b a b 终了终了 开场开场 a b b=baa=ab YN 程序：程序： a=input(“a=)； b=input(“b=)； while ab if a=b a=ab; else b=ba； end end print(%io(2), b, “两数的最大公约数为：两数的最大公约数为： ) 例例1 ：用等值算法更相减损术求以下：用等值算法更相减损术求以下 两数的最大公约数。两数的最大公约数。 122

6、5，；，； 298，280. 例例2：用辗转相除法验证上例中两数的最：用辗转相除法验证上例中两数的最 大公约数能否正确。大公约数能否正确。 答案答案: (1) 45;(2) 14. 2割圆术割圆术 魏晋时期数学家刘徽，魏晋时期数学家刘徽，“割之弥细，所割之弥细，所 失弥少，割之又割，以致于不可割，那么失弥少，割之又割，以致于不可割，那么 与圆合体而无所失矣与圆合体而无所失矣. 即从圆内接正六边形开场，让边数逐次即从圆内接正六边形开场，让边数逐次 加倍，逐个算出这些内接正多边形的面积，加倍，逐个算出这些内接正多边形的面积， 从而得到一系列逐次递增的数值。从而得到一系列逐次递增的数值。 第一，从半

7、径为第一，从半径为1的圆内接正六边形开场，的圆内接正六边形开场， 计算它的面积计算它的面积S6； 第二，逐渐加倍圆内接正多边形的边数，分第二，逐渐加倍圆内接正多边形的边数，分 别计算圆内接正十二边形，正二十四边形，别计算圆内接正十二边形，正二十四边形， 正四十八边形，正四十八边形，的面积，到一定的边数的面积，到一定的边数 设为设为2m为止，得到一列递增的数，为止，得到一列递增的数， S6，S12，S24，S48，S2m. 第三，第三，S2m近似等于圆面积。近似等于圆面积。 下面的关键是找出正下面的关键是找出正n边形的面积与正边形的面积与正2n 边形的面积之间的关系，以便递推。边形的面积之间的关

8、系，以便递推。 设圆的半径为设圆的半径为1，正，正n边形边形 的边长的边长AB为为xn，弦心距，弦心距 OG为为hn；面积为；面积为Sn，根，根 据勾股定理，得：据勾股定理，得： 2 2 2 2 1, 2 1(6) 2 n n n nn x h x xhn 容易知道容易知道x6=1, 正正2n边形的面积等于正边形的面积等于正n 边形的面积加上边形的面积加上n个等腰三个等腰三 角形的面积，即角形的面积，即 2 1 (1)(6) 2 nnnn SSnxhn 正正2n边形的边长为边形的边长为 22 2 )1 () 2 ( n n n h x x 于是由于是由 6 3 6 4 S 求得求得S12=3；

9、 S243.105828； n=6; x=1; s=6*sqrt(3)/4; for i=1 : 1 : 5 h=sqrt(1(x/2)2); s=s+n*x*(1h)/2; n=2*n; x=sqrt(x/2)2+(1 h)2); end print(%io(2), n, s) 程序：程序： 数学运用数学运用 例例1、两个正整数的最小公倍数，实践上就是这两数、两个正整数的最小公倍数，实践上就是这两数 乘积除以它们的最大公约数，试写出求正整数乘积除以它们的最大公约数，试写出求正整数a,b最小最小 公倍数的程序。公倍数的程序。 a=input(“a=); b=input(“b=); c=modu

10、lo(a, b); d=a*b; While c0 a=b; b=c; c=modulo(a,b); End print(%io(2), d/b) 数学运用数学运用 例例2 2、用更相减损术求、用更相减损术求9898与与6363的最大公约数。的最大公约数。 解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，以大数减小数， 并辗转相减并辗转相减 989863633535 636335352828 353528287 7 28287 72121 21217 71414 14147 77 7 所以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7 课堂

11、练习课堂练习 1.1.下面一段伪代码的目的是下面一段伪代码的目的是( )( ) 10 Read a,b 20 If a/bInt (a/b) Then goto 70 30 caInt(a/b)b 40 ab 50 bc 60 Goto 20 70 Print b A.求求a,b的最小公倍数的最小公倍数 B.求求a,b的最大公约数的最大公约数 C.求求a被被b整除的商整除的商 D.求求b除以除以a的余数的余数 分析：解题关键就是：分析：解题关键就是：aint(a/b)bmod(a,b) B 2.2.写出图示流程图所表达算法的伪代码，并求出最后写出图示流程图所表达算法的伪代码，并求出最后 输出的

12、输出的n n的值。的值。 课堂练习课堂练习 10 m147 20 n84 30 rmod(m,n) 40 If r=0 Then Goto 70 50 mn,nr 60 Goto 30 70 Print n 80 End n的值为的值为21 课堂练习课堂练习 3.3.用更相减损术求两个正数用更相减损术求两个正数8484与与7272的最大公约数的最大公约数 分析：先约简，再求分析：先约简，再求21与与18的最大公约数的最大公约数,然后然后 乘以两次约简的质因数乘以两次约简的质因数4。 21-18=321-18=3 18-3=1518-3=15 15-3=1215-3=12 12-3=912-3=9 9-3=69-3=6 6-3=36-3=3 所以，所以，2121和和1818的最大公约数等于的最大公约数等于3 3 所以，所以，8484和和7272的最大公约数等于的最大公约数等于1212。 回想反思回想反思 1、辗转相除法是当大数被小数除尽时，终了、辗转相除法是当大数被小数除尽时，终了 除法运算，较小的数就是最大公约数除法运算，较小的数就是最大公约数 2、更相减损术是当大数减去小数的差等于小、更相减损术是当大数减去小数的差等于小 数时减法停顿