1.3.1算法案例
一、辗转相除法与更相减损术
知识探究（一）:辗转相除法
思考1:18与30的最大公约数是多少？
你是怎样得到的？
先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数.
思考2:对于8251与6105这两个数，
由于其公有的质因数较大，
利用上述方法求最大公约数就比较困难.
注意到8251=6105×1+2146，
那么8251与6105这两个数的公约数
和6105与2146的公约数有什么关系？
2146=1813×1+333，
148=37×4+0.
333=148×2+37，
1813=333×5+148，
8251=6105×1+2146，
6105=2146×2+1813，
思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.
重复上述操作，你能得到8251与6105这两个数的最大公约数吗？
第一步，给定两个正整数m，n(m>n).
第二步，计算m除以n所得的余数r.
第三步，m=n，n=r.
第四步，若r=0，则m，n的最大公约数等 于m；否则，返回第二步.
思考4:上述求两个正整数的最大公约数的方法
称为辗转相除法或欧几里得算法.
一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？
思考5:该算法的程序框图如何表示？
思考6:该程序框图对应的程序如何表述？
INPUT m，n
DO
r=m MODn
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
思考7:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？
INPUT m，n
WHILE n>0
r=m MODn
m=n
n=r
WEND
PRINT m
END
知识探究（二）:更相减损术
98-63=35，
14-7=7.
21-7=14，
28-7=21，
35-28=7，
63-35=28，
思考1:设两个正整数m>n，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.
反复利用这个原理，可求得98与63的最大公约数为多少？
第一步，给定两个正整数m，n(m>n).
第二步，计算m-n所得的差k.
第三步，比较n与k的大小，
其中大者用m表示，小者用n表示.
思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？
其算法步骤如何设计？
第四步，若m=n，则m，n的最大公约数
等于m；否则，返回第二步.
思考3:该算法的程序框图如何表示？
思考4:该程序框图对应的程序如何表述？
INPUT m，n
WHILE m<>n
k=m-n
IF n>k THEN
m=n
n=k
ELSE
m=k
END IF
WEND
PRINT m
END
例1：分别用辗转相除法和更相减损术
求168与93的最大公约数.
辗转相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6.
所以168与93的最大公约数为3
更相减损术:168-93=75，
93-75=18，
75-18=57，
57-18=39，
39-18=21，
21-18=3，
18-3=15，
15-3=12，
12-3=9，
9-3=6，
6-3=3.
例2：求325，130，270三个数的最大公约数.
解：因为325=130×2+65，130=65×2，
所以325与130的最大公约数是65.
因为270=65×4+10，65=10×6+5，10=5×2，
所以65与270最大公约数是5.
故325，130，270三个数的最大公约数是5.