1.3中国古代数学中的算法案例（一）1. 求两个正整数最大公约数的算法辗转相除法求两个数的最大公约数，其基本步骤是带余除法m=nq+r（0rn），反复执行，直到余数r=0为止.求任意两个数的最大公约数的算法是 第一步：输入两个 正整数a，b（ab）;第二步：求出ab的 余数r；第三步：令a=b， b=r，若r0，重复第二 步；第四步：输出最大 公约数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.输出bb=cY N输入a,ba=bc=a mod bc 0结束开始c = a Mod ba=input(“a=”); b=input(“b=”); c=modulo(a,b); while cb)；S2如果ab，则执行S3，否则转到S5；S3 将ab的值赋予r；S4 若br，则把b赋予a，把r赋予b，否则把r赋予a，重新执行S2；S5 输出最大公约数输出bYN输入a,ba b结束开始a bb=baa=abYN程序： a=input(“a=”)； b=input(“b=”)； while a=ba=ab;else b=ba；end end print(%io(2), b, “两数的最大公约数为：” )例1 ：用等值算法（更相减损术）求下列两数的最大公约数。（1）225，135； （2）98，280.例2：用辗转相除法验证上例中两数的最大公约数是否正确。 答案: (1) 45;(2) 14.2割圆术魏晋时期数学家刘徽，“割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体而无所失矣”.即从圆内接正六边形开始，让边数逐次加倍，逐个算出这些内接正多边形的面积，从而得到一系列逐次递增的数值。第一，从半径为1的圆内接正六边形开始， 计算它的面积S6； 第二，逐步加倍圆内接正多边形的边数，分 别计算圆内接正十二边形，正二十四边形， 正四十八边形，的面积，到一定的边数（ 设为2m）为止，得到一列递增的数， S6，S12，S24，S48，S2m.第三，S2m近似等于圆面积。下面的关键是找出正n边形的面积与正2n 边形的面积之间的关系，以便递推。设圆的半径为1，正n边形的边长AB为xn，弦心距OG为hn；面积为Sn，根据勾股定理，得：容易知道x6=1,正2n边形的面积等于正n 边形的面积加上n个等腰三 角形的面积，即正2n边形的边长为于是由求得S12=3；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=modulo(a, b); d=a*b; While c0a=b; b=c;c=modulo(a,b); End print(%io(2), d/b)数学运用 例2、用更相减损术求98与63的最大公约数。解：由于63不是偶数，把98和63以大数减小数， 并辗转相减 986335 633528 35287 28721 21714 1477所以，98和63的最大公约数等于7 课堂练习 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 bA.求a,b的最小公倍数 B.求a,b的最大公约约数 C.求a被b整除的商 D.求b除以a的余数分析：解题关键就是：aint(a/b)bmod(a,b)B2.写出图示流程图所表达算法的伪代码，并求出最后输 出的n的值。课堂练习10 m14720 n8430 rmod(m,n)40 If r=0 Then Goto 7050 mn,nr60 Goto 3070 Print n80 Endn的值为21课堂练习3.用更相减损术求两个正数84与72的最大公约数 分析：先约简，再求21与18的最大公约数,然后 乘以两次约简的质因数4。 21-18=3 18-3=15 15-3=12 12-3=9 9-3=6 6-3=3 所以，21和18的最大公约数等于3 所以，84和72的最大公约数等于12。 回顾反思 1、辗转相除法是当大数被小数除尽时，结束 除法运算，较小的数就是最大公约数2、更相减损术是当大数减去小数的差等于小 数时减法停止较小的数就是最大公约数3、求三个以上(含三个数)的数的最大公约数 时，可依次通过求两个数的最大公约数与第 三数的最大公约数来求得 4、辗转相除法中蕴含的数学原理及算法语 言的表示； 5、如何实现当型循环。