算法案例（1）

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 算法初步,1.3 算法案例(1),3 5,9 15,1.,在小学，我们已经学过求最大公约数的知识，你能求出,18,与,30,的最大公约数吗？,18 30,2,3,18,和,30,的最大公约数是,2,3=6.,先用两个数公有的,质因数,连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来,.,2.,如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求,8251,与,6105,的最大公约数,?,新课引入,1.,辗转相除法,:,求两个正数,8251,和,6105,的最大公约数。,分析：,8251,与,6105,两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数,.,解：,8251,6105,1,2146,注：,8251,和,6105,的公约数就是,6105,和,2146,的公约数，求,8251,和,6105,的最大公约数，只要求出,6105,和,2146,的公约数就可以了。,案例,1,辗转相除法与更相减损术,例题剖析,求两个正数,8251,和,6105,的最大公约数。,解：,8251,6105,1,2146;,则,37,为,8251,与,6105,的最大公约数。,以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前,300,年左右首先提出的。,6105,21462,1813;,2146,18131,333;,1813,3335,148;,333,1482,37;,148,374,0.,第一步：输入两个正整数,m,n(mn).,第二步：计算,m,除以,n,所得的余数,r.,第三步：,m=n,n=r.,第四步：若,r,0,则,m,n,的最大公约数等于,m,；,否则转到第二步,.,第五步：输出最大公约数,m.,诱思探究,（,2,）算法步骤,（,1,）算法分析：,所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。,你能写出利用辗转相除法求最大公约数的程序吗？,开始,输入,m,n,r=m MOD n,m=n,r=0?,是,否,n=r,输出,m,结束,INPUT “m,n=“;m,n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,（,3,）程序框图,（,4,）程序,利用辗转相除法求两数,4081,与,20723,的最大公约数,.,课堂练习,解：,20723=40815+318;,4081=31812+265;,318=2651+53;,265=535+0.,所以,4081,与,20723,的最大公约数为,53.,2.,更相减损术,:,我国早期也有解决求最大公约数问题的算法，就是更相减损术。,更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母,子之数，以少减多，更相减损，求其等也，以等数约之。,翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用,2,约简；若不是，执行第二步。,第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。,用更相减损术求,98,与,63,的最大公约数,.,解：由于,63,不是偶数，把,98,和,63,以大数减小数，并辗转相减，,所以，,98,与,63,的最大公约数是,7,。,98,63,35;,63,35,28;,35,28,7;,28,7,21;,21,7,14;,14,7,7.,例题剖析,2,用更相减损术求两个正数,84,与,72,的最大公约数。,课堂练习,解：,把,84,与,72,分别除以,2,得：,42,，,36,21-18=3,18-3=15,15-3=12,12-3=9,9-3=6,6-3=3,所以,84,与,72,的最大公约数为,12.,再分别除以,2,得：,21,，,18,辗转相除法与更相减损术的比较有何区别？,（,1,）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主,;,计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。,（,2,）从结果体现形式来看，辗转相除法体现结果是以相除余数为,0,则得到，而更相减损术则以减数与差相等而得到,.,诱思探究,2,如何求,324,、,243,、,135,这三个数的最大公约数。,思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。,诱思探究,3,课堂小结,本节课学习的主要内容：,1.,了解辗转相除法与更相减损术求两个正整数的最大公约数的算理；,2.,能用辗转相除法与更相减损术求两个正整数的最大公约数。,课外作业,1.,课本第,48,页,A,组,1,2.,预习课本,3739,内容,再见！,