辗转相除法可以用来计算两个数之间的最大公约数, 也成为欧几里得算法
算法大致: 在 B 等于 0 之前, 交换 AB 位置让 V 等于上一轮 A 求余 B 的结果, 当 B 为 0 时, A 就是最大公约数
代码实现
- int gcd(int a, int b){
- if (b == 0) {
- return a;
- }
- gcd(b, a % b);
- }
- int main() {
- printf("%d", gcd(12, 18));
- return 0;
- }
打印输出
6
每轮数字变化
- 12 18
- 18 12
- 12 6
- 6 0
此时, B == 0, 于是结果为 A 的值 6
来源: http://www.bubuko.com/infodetail-3319258.html