求两个正整数最大公约数的算法

1、求两个正整数求两个正整数最大公约数的算法最大公约数的算法学习目标：学习目标：（）了解中国古代数学中求两个正整数最大公约数的算法（）了解中国古代数学中求两个正整数最大公约数的算法以及割圆术的算法；以及割圆术的算法；（）通过对（）通过对“更相减损之术更相减损之术”及及“割圆术割圆术”的学习，更好的学习，更好的理解将要解决的问题的理解将要解决的问题“算法化算法化”的思维方法，并注意理解推的思维方法，并注意理解推导导“割圆术割圆术”的操作步骤。的操作步骤。（3）学会借助实例分析，探究数学问题。）学会借助实例分析，探究数学问题。 人们在长期的生活，生产和劳动过程中，创人们在长期的生活，生产和劳动过程中，

2、创造了整数，分数，小数，正负数及其计算，以及造了整数，分数，小数，正负数及其计算，以及无限逼近任一实数的方法，在代数学，几何学方无限逼近任一实数的方法，在代数学，几何学方面，我国在宋，元之前也都处于世界的前列。我面，我国在宋，元之前也都处于世界的前列。我们在小学，中学学到的算术，代数，从记数到多们在小学，中学学到的算术，代数，从记数到多元一次联立方程的求根方法，都是我国古代数学元一次联立方程的求根方法，都是我国古代数学家最先创造的。更为重要的是我国古代数学的发家最先创造的。更为重要的是我国古代数学的发展有着自己鲜明的特色，也就是展有着自己鲜明的特色，也就是“寓理于算寓理于算”，即把解决的问题即

3、把解决的问题“算法化算法化”。本章的内容是算法，。本章的内容是算法，特别是在中国古代也有着很多算法案例，我们来特别是在中国古代也有着很多算法案例，我们来看一下并且进一步体会看一下并且进一步体会“算法算法”的概念。的概念。求最大公约数你能求出你能求出18与与30的公约数吗的公约数吗? 你能看出你能看出78与与36的公约数吗的公约数吗? 更相减损之术（指导阅读课本更相减损之术（指导阅读课本P27-P28）步骤：步骤： 以两数中较大的数减去较小的数，即以两数中较大的数减去较小的数，即；以差数和较小的数；以差数和较小的数3构成新的一对数，对这一构成新的一对数，对这一对数再用大数减去小数，即对数再用大数

4、减去小数，即,再以差数再以差数和较小的数构成新的一对数，对这一对数再用大数减和较小的数构成新的一对数，对这一对数再用大数减去小数，即去小数，即,继续这一过程继续这一过程,直到产生一对直到产生一对相等的数，这个数就是最大公约数相等的数，这个数就是最大公约数 )36, 6()36,42()36,78()6 ,30()6 ,24()6 , 6()6 ,12()6 ,18(即，rbarbaba,rb,由由，得与有相同的公约数有相同的公约数 理论依据：理论依据：算法：算法：1S)(,baba输入两个正数输入两个正数2Sba 3S5S如果如果，则执行则执行，否则转到否则转到3Sba r将将的值赋予的值赋予

5、 4Srb barbra2S若若，则把则把赋予赋予，把把赋予赋予，否则把否则把赋予赋予，重新执行重新执行 5Sb输出最大公约数输出最大公约数 程序程序:a=input(“a=”)b=input(“b=”)while ab if a=b a=a-b; else b=b-a； endendprint(%io(2),a,b) 我国早期也有解决求最大公约数问题的算法，就是我国早期也有解决求最大公约数问题的算法，就是更相减损术。更相减损术。更相减损术求最大公约数更相减损术求最大公约数 可半者半之，不可半者，副置分母分子之数，可半者半之，不可半者，副置分母分子之数，以少减多，更相减损，求其等也，以等数约以

6、少减多，更相减损，求其等也，以等数约之。之。 翻译出来为：翻译出来为： 第一步：任意给出两个正数；判断它们是否都是偶数。第一步：任意给出两个正数；判断它们是否都是偶数。若是，用若是，用2约简；若不是，执行第二步。约简；若不是，执行第二步。 第二步：以较大的数减去较小的数，接着把较小的数与第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大所得的数相等为止，则这个数（等数）就是所求的最大公约数。公约数。 例例1 用更相减损术求用更相减损术求91与与49的最大

7、公约数的最大公约数.更相减损术的应用更相减损术的应用 解：由于解：由于49不是偶数，把不是偶数，把91和和49以大数减小以大数减小数，并辗转相减，数，并辗转相减， 即：即：914842 49427 42735 35728 28721 21714 1477 所以，所以，91与与49的最大公约数是的最大公约数是7。 例例2 求两个正数求两个正数a=204和和b=85的最大的最大公约数。公约数。辗转相除法求最大公约数辗转相除法求最大公约数 分析：分析：204与与85两数都比较大，而且两数都比较大，而且没有明显的公约数，如能把它们都没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求变小一点，

8、根据已有的知识即可求出最大公约数出最大公约数 20485234 显然显然204的最大公约数也必是的最大公约数也必是85的约数，的约数，同样同样204与与85的公约数也必是的公约数也必是34的约数，的约数，所以所以204与与85的最大公约数也是的最大公约数也是85与与34的最大公约数。的最大公约数。 8534217 34172+0 则则17为为204与与85的最大公约数。的最大公约数。辗转相除法的基本步骤：第一步：用较大的数第一步：用较大的数m除以较小的数除以较小的数n得到得到一个商一个商q0和一个余数和一个余数r0；第二步：若第二步：若r00，则，则n为为m，n的最大公约的最大公约数；若数；若

9、r00，则用除数，则用除数n除以余数除以余数r0得到一得到一个商个商q1和一个余数和一个余数r1；第三步：若第三步：若r10，则，则r1为为m，n的最大公约的最大公约数；若数；若r10，则用除数，则用除数r0除以余数除以余数r1得到一得到一个商个商q2和一个余数和一个余数r2； 依次计算直至依次计算直至rn0，此时所得到的，此时所得到的rn1即即为所求的最大公约数。为所求的最大公约数。程序框图：a=input(“a=”);b=input(“b=”);While modulo(a,b)0, r=modulo(a,b); a=b;b=r;endd=b开始开始输入a,b求a除以b的余数ra=bb=r

10、r=0 ?结束结束输出b是否程序：比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗转相）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较当两个数字大小区别较大时计算次数的区别较明显。明显。 （2）从结果体现形式来看，辗转相除法体现结）从结果体现形式来看，辗转相除法体现结果是以相除余数为果是以相除余数为0则得到，而更相减损术则以则得到，而更相减损术则以减数与差相等而得到。减数与差相等而得到。巩固运用巩固运用 求求196和和147的最大公约数的最大公约数 回顾反思回顾反思 辗转相除法是当大数被小数除尽时，结束除辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数法运算，较小的数就是最大公约数 更相减损术是当大数减去小数的差等于小数更相减损术是当大数减去小数的差等