1.3中国古代数学中的算法案例(一)

1.3中国古代数学中的算法案例（一）1.求两个正整数最大公约数的算法辗转相除法求两个数的最大公约数，其基本步骤是带余除法m=nq+r（0≤r＜n），反复执行，直到余数r=0为止.求任意两个数的最大公约数的算法是第一步：输入两个正整数a，b（a＞b）;第二步：求出a÷b的余数r；第三步：令a=b，b=r，若r≠0，重复第二步；第四步：输出最大公约数a.举例说明.m=90，n=36，m=2n+18，r=18.令m=36，n=18.又有36=18×2，即m=2n，此时r=0.令m=18，n=0.故最大公约数为18.算理：先找到a,b中较大的，记为a；a=b×t＋c；若c≠0,记a=b,b=c,返回第2步进行循环；若c=0，输出b.输出bb=cYN输入a,ba=bc=amodbc≠0结束开始c=aModba=input(“a=”);b=input(“b=”);c=mod(a,b);whilec0a=b;b=c;c=mod(a,b);endb更相减损术以两数中较大的数减去较小的数，即78－36＝42；以差数42和较小的数36构成新的一对数；对这一对数再用大数减去小数，即42－36＝6，再以差数6和较小的数36构成新的一对数；对这一对数再用大数减去小数，即36－6＝30，再构成新的一对数；例如，求78和36的最大公约数：继续这一过程,直到产生一对相等的数，这个数就是最大公约数.操作如下：(78，36)→(42，36)→(6，36)→(6，30)→(6，24)→(6，18)→(6，12)→(6，6).理论依据：由a－b=r→a=b+r，得(a,b)与(b,r)有相同的公约数.算法如下：S1输入两个正数a,b(ab)；S2如果a≠b，则执行S3，否则转到S5；S3将a－b的值赋予r；S4若br，则把b赋予a，把r赋予b，否则把r赋予a，重新执行S2；S5输出最大公约数输出bYN输入a,ba≠b结束开始abb=b－aa=a－bYN程序：a=input(“a=”)；b=input(“b=”)；whileabifa=ba=a－b;elseb=b－a；endendprint(%io(2),b,“两数的最大公约数为：”)例1：用等值算法（更相减损术）求下列两数的最大公约数。（1）225，135；（2）98，280.例2：用辗转相除法验证上例中两数的最大公约数是否正确。答案:(1)45;(2)14.数学运用例1、两个正整数的最小公倍数，实际上就是这两数乘积除以它们的最大公约数，试写出求正整数a,b最小公倍数的程序。a=input(“a=”);b=input(“b=”);c=mod(a,b);d=a*b;Whilec0a=b;b=c;c=mod(a,b);Endprint(%io(2),d/b)数学运用例2、用更相减损术求98与63的最大公约数。解：由于63不是偶数，把98和63以大数减小数，并辗转相减98－63＝3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7所以，98和63的最大公约数等于7回顾反思1、辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数．2、更相减损术是当大数减去小数的差等于小数时减法停止．较小的数就是最大公约数．3、求三个以上(含三个数)的数的最大公约数时，可依次通过求两个数的最大公约数与第三数的最大公约数来求得．4、辗转相除法中蕴含的数学原理及算法语言的表示；5、如何实现当型循环。