算法案例之求最大公约数课件.pptx

算法案例之求最大公约数
求以下几组正整数的最大公约数。
(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示
m和n的最大公约数。)
（1）（18，30） （2）（24，16）
1）（225，135） （2）（98，196）
（3）（72，168） （4）（153，119）
45
98
24
17
4
感谢你的欣赏
2019-10-6
次数
1
2
3
4
5
6
m
n
r
8251和6105的最大公约数
解：
8251=6105×1+2146
6105=2146 ×2+1813
2146=1813 ×1+333
1813=333 ×5+148
333=148 ×2+37
148=37 ×4
（8251，6105）
=（6105，2146）
=（2146，1813）
=（1813，333）
=（333，148）
=（148，37）
=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-10-6
辗转相除法求两个数的最大公约数，其算法可以描述如下：
辗转相除法是一个反复执行直到余数等于0停止的步骤，
这实际上是一个循环结构
思考：辗转相除直到何时结束？主要运用的是哪种算法结构？
如此循环，直到得到结果。
① 输入两个正整数m和n；
② 求余数r：计算m除以n，将所得余数存放到变量r中；
③更新被除数和余数：m=n，n=r。
④判断余数r是否为0：若余数为0则输出结果，否则转
向第②步继续循环执行。
6
感谢你的欣赏
2019-10-6
开始
输入：m,n
输出：m
结束
r=0?
m=n
N
Y
r=m MOD n
n=r
程序：　　INPUT “m，n=”;m,n　　DO
r=m MOD n　　m=n　　n=r　　LOOP UNTIL r=0　　PRINT m　　END
7
感谢你的欣赏
2019-10-6
更相减损术
同理：a,b,c为正整数，若a-b=c，则（a,b）=(b,c)。
“更相减损术”（也是求两个正整数的最大公约数的算法）
步骤：
第一步：任意给定两个正整数；判断他们是否都是偶数。
若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较
小的数比较，并以大数减小数。继续这个操作，直到所
得的减数和差相等为止，则这个等数就是所求的最大公
约数。
8
感谢你的欣赏
2019-10-6
例、用更相减损术求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-10-6
练习：用更相减损术求下列两数的最大公约数：
（1）（225，135） （2）（98，196）
（3）（72，168） （4）（153，119）
45
98
24
17
10
感谢你的欣赏
2019-10-6
例 用更相减损术求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
次数
1
2
3
4
5
6
a
98
63
35
28
21
14
b
63
35