Euclid算法证明

也叫:辗转相除法 or 欧几里得算法。

题目来源

注意: 0 和任意整数的最大公约数都是这个整数(而不是0)。

编写递归函数求两个正整数a和b的最大公约数(GCD,Greatest Common Divisor),使用Euclid算法:

  1. 如果 a 除以 b 能整除,则最大公约数是 b;
  2. 否则,最大公约数等于 b 和 a%b 的最大公约数;
  3. 证明该算法。

代码部分

1
2
3
4
5
6
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a%b);
}

算法证明

------本文结束感谢您的阅读 ------
0%