《算法案例之求最大公约数课件.pptx》由会员分享，可在线阅读，更多相关《算法案例之求最大公约数课件.pptx（17页珍藏版）》请在三一办公上搜索。
1、算法案例之求最大公约数,求以下几组正整数的最大公约数。(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示m和n的最大公约数。)（1）（18，30） （2）（24，16）（3）（63，63） （4）（72，8） （5）（301，133 ）,解：2 1 8 2 4 用公有质因数2除， 3 9 1 2 用公有质因数3除， 3 4 3和4互质不除了。 得：18和24最大公约数是：236,想一想，如何求8251与6105的最大公约数？,例、求18与24的最大公约数：,6；,8；,63；,8；,7；,短除法,1,谢谢观赏,2019-6-27,穷举法（也叫枚举法）步骤： 从两个数中较小数开
2、始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。,穷举法,2,谢谢观赏,2019-6-27,定理： 已知m,n,r为正整数，若m=nq+r（0rn）（即r=m MOD n）,则（m,n）=(n,r)。,辗转相除法,分析：m=nq+r r=m-nq ,例1、求8251和6105的最大公约数。,148=37 4,=37,8251=61051+2146,（8251，6105）=（6105，2146）,6105=2146 2+1813,=（2146，1813）,2146=1813 1+333,=（1813，333）,1813=333 5+148,=（333，148）,333=
3、148 2+37,=（148，37）,解：,3,谢谢观赏,2019-6-27,练习：用辗转相除法求下列两数的最大公约数：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119）,45,98,24,17,4,谢谢观赏,2019-6-27,8251和6105的最大公约数,解：8251=61051+21466105=2146 2+18132146=1813 1+3331813=333 5+148333=148 2+37148=37 4,（8251，6105）=（6105，2146）=（2146，1813）=（1813，333）=（333，148）=（148，3
4、7）=37,关系式m=np+r中m,n,r得取值变化情况,8251,6105,2146,6105,2146,2146,1813,1813,333,1813,333,148,148,333,37,148,37,0,5,谢谢观赏,2019-6-27,辗转相除法求两个数的最大公约数，其算法可以描述如下：,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构,思考：辗转相除直到何时结束？主要运用的是哪种算法结构？,如此循环，直到得到结果。, 输入两个正整数m和n；, 求余数r：计算m除以n，将所得余数存放到变量r中；,更新被除数和余数：m=n，n=r。,判断余数r是否为0：若余数为
5、0则输出结果，否则转向第步继续循环执行。,6,谢谢观赏,2019-6-27,程序：INPUT “m，n=”;m,nDO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND,7,谢谢观赏,2019-6-27,更相减损术,同理：a,b,c为正整数，若a-b=c，则（a,b）=(b,c)。,“更相减损术”（也是求两个正整数的最大公约数的算法）步骤：,第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。,第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求
6、的最大公约数。,8,谢谢观赏,2019-6-27,例、用更相减损术求98与63的最大公约数（自己按照步骤求解）,解：由于63不是偶数，把98和63以大数减小数，并辗转相减。,= 7,所以，98和63的最大公约数等于7。,（98，63）=（63，35）,98-63=35,63-35=28,=（35，28）,35-28=7,=（28，7）,28-7=21,=（21，7）,21-7=14,=（14，7）,14-7=7,=（7，7）,9,谢谢观赏,2019-6-27,练习：用更相减损术求下列两数的最大公约数：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119
7、）,45,98,24,17,10,谢谢观赏,2019-6-27,例 用更相减损术求98与63的最大公约数,解：由于63不是偶数，把98和63以大数减小数，并辗转相减 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7所以，98和63的最大公约数等于7。,（98，63）=（63，35）=（35，28）=（28，7）=（21，7）=（14，7）=（7，7）=7,关系式a-b=c中a,b,c得取值变化情况,11,谢谢观赏,2019-6-27,更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构,思考：更相减损直到何时结束？运用的是哪种
8、算法结构？,12,谢谢观赏,2019-6-27,程序：INPUT “a,b”;a,bi=0WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DOIF ba THENt=aa=bb=tEND IFa=a-bLOOP UNTIL a=bPRINT a*2iEND,13,谢谢观赏,2019-6-27,辗转相除法与更相减损术的区别：,小 结,（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。,（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0而得到，而更相减损术则以减数与差相等而得到的。,14,谢谢观赏,2019-6-27,作业：P38 习题：1.3 第一题,15,谢谢观赏,2019-6-27,16,谢谢观赏,2019-6-27,再见,17,谢谢观赏,2019-6-27,
