文档介绍：算法案例
(第一课时)
案例1 辗转相除法与更相减损术
2. 思考:
小学学过的求两个数最大公约数的方法?
先用两个公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.
1、求两个正整数的最大公约数
(1)求25和35的最大公约数
(2)求49和63的最大公约数
25
(1)
5
5
35
7
49
(2)
7
7
63
9
所以,25和35的最大公约数为5
所以,49和63的最大公约数为7
2、除了用这种方法外还有没有其它方法?
算出8256和6105的最大公约数.
辗转相除法(欧几里得算法)
观察用辗转相除法求8251和6105的最大公约数的过程
第一步用两数中较大的数除以较小的数,求得商和余数 8251=6105×1+2146
结论: 8251和6105的公约数就是6105和2146的公约数,求8251和6105的最大公约数,只要求出6105和2146的公约数就可以了。
第二步对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数。
思考:从上述的过程你体会到了什么?
完整的过程
8251=6105×1+2146
6105=2146×2+1813
2146=1813×1+333
1813=333×5+148
333=148×2+37
148=37×4+0
例2 用辗转相除法求225和135的最大公约数
225=135×1+90
135=90×1+45
90=45×2
显然37是148和37的最大公约数,也就是8251和6105的最大公约数
显然45是90和45的最大公约数,也就是225和135的最大公约数
思考1:从上面的两个例子可以看出计算的规律是什么?
S1:用大数除以小数
S2:除数变成被除数,余数变成除数
S3:重复S1,直到余数为0
辗转相除法是一个反复执行直到余数等于0停止的步骤,这实际上是一个循环结构。
8251=6105×1+2146
6105=2146×2+1813
2146=1813×1+333
1813=333×5+148
333=148×2+37
148=37×4+0
m = n × q + r
用程序框图表示出右边的过程
r=m MOD n
m = n
n = r
r=0?
是
否
思考2:辗转相除法中的关键步骤是哪种逻辑结构?
1、辗转相除法(欧几里得算法)
(1)算理:所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数。若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数。
(2)算法步骤
第一步:输入两个正整数m,n(m>n).
第二步:计算m除以n所得的余数r.
第三步:m=n,n=r.
第四步:若r=0,则m,n的最大公约数等于m;
否则转到第二步.
第五步:输出最大公约数m.
(3)程序框图
(4)程序
INPUT “m,n=“;m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
开始
输入m,n
r=m MOD n
m=n
r=0?
是
否
n=r
输出m
结束