Euclid’s Algorithm （最大公约数）
2018-11-01 本文已影响0人
小猪与城
1.问题描述
两个正数 m 和 n 的最大公约数
2. 伪代码
gcd(m,n) //求最大公约数
while n ≠ 0
r ← m mod n //计算m除n的余数
m ← n //把n赋给m
n ← r //把r赋给n
return m
实例展示
表格中 每一行的结果是运行一次while循环的结果
| r | m | n |
|---|---|---|
| 24 | 60 | |
| 24 | 60 | 24 |
| 12 | 24 | 12 |
| 0 | 12 | 12 |
执行结果：24 和 60 的最大公约数为12
创建于 2018/11/1
