iLeichun

public static int math(int a, int b) {

...

}

分析： 关于这道题的算法有多种，我们今天只研究下面这种算法：

1    public static int math(int a, int b) {

2       int hold = 0;

3       while (b != 0) {

4           hold = a % b;

5           a = b;

6           b = hold;

7       }

8       return a;

9    }

初看这个解法，你可能会一头雾水。再看看，更是不知所云。甚至怀疑这样算是不是可 以得到正确结果，但经过测试你会发现的确可以得到正确结果，这究竟是为什么呢？让我们 来分析一下这个算法，为了便于叙述，把行号加上：

第 1 行，程序调用这个方法时会传入两个正整数 a 和 b

第 2 行，声明一个 int 类型的变量 hold 并赋初值 0；第 3-7 行是一个 while 循环，循环条件是 b!=0；

第 4 行，用 hold 来保存 a%b 的结果

第 5 行，把 b 的值赋给 a

第 6 行，把 hold 的值赋给 b

若 b 不为 0，则进行下一次循环，直到 b=0 时停止循环

最后第 8 行把 a 的值返回。

首先我们假设程序只进行一次循环，也就是说：方法传入 a 和 b 时

第 4 行，hold=a%b=0；

第 5 行，a=b；

第 6 行，b=hold=0；再进行第 3 行判断循环停止

第 8 行，返回 a 的值，也就是第 5 行中方法开始时传入的 b 的值，这说明： 如果 a%b=0 那么 a 和 b 的最大公约数就为 b，

这点好理解，a%b=0 也就是说 a 能被 b 整除，那当然 a 和 b 的最大公约数就是 b 了。 关键是如果不是进行一次，而是进行多次循环呢？

为了便与理解，我把上面的程序改为递归算法：

1    public static int math1(int a, int b) {

2       if (b == 0) {

3           return a;

4       }

5       int hold = a % b;

6       a = b;

7       b = hold;

8       return math1(a, b);

9    }

第 1 行，程序调用这个方法时传入两个正整数 a 和 b

第 2－4 行，如果 b 等于 0 返回 a 的值

第 5 行，声明一个 int 类型的变量 hold 保存 a%b 的结果

第 6 行，把 b 的值赋给 a

第 7 行，把 hold 的值赋给 b

第 8 行，递归调用，直到 b 的值为 0 时返回 a 的值

最后第 8 行把 a 的值返回。

在首次调用这个方法传入 a 和 b 的值时第 3 行肯定不会执行，而是执行 5－8 行的代码， 由第 8行，我们可以看出程序的意思是 a和 b的最大公约数与 b和 a%b 的最大公约数相同。

由此我们可以得到如下两个命题：

命题一：a 和 b 的最大公约数与 b 和 a%b 的最大公约数相同；

命题二：如果 b%(a%b)=0，那么 a 和 b 的最大公约数为 a%b，（其中 a，b 都为正整数，且 a%b!=0）。 

如果能证明这两个命题，则上面的算法也就不难理解了：因为程序实际上一直在运用命题一反复进行递归调用，只是在最后两次时运用命题二，得出最后结果。

 我们先看命题一：a 和 b 的最大公约数与 b 和 a%b 的最大公约数相同。 证明：由于 a%b!=0 则 a!=b，当 a<b 时 a%b=a，命题自然成立；

当 a>b  时可设 a 和 b 的最大公约数为 x；

a=mx，b=nx，其中 m 和 n 为正整数且 m 与 n 互质（除 1 之外再无其它公因数） 则可设：a%b=(m-kn)x，其中 k 为正整数

这说明：b 和 a%b 有公因数 x，下面证明 n 与 m-kn 互质 假设 n 与 m-kn 有公因数 y，y 为正整数且 y 不等于 1 则可设：n=py，m-kn=qy，其中 p 和 q 为正整数 那么：m-kn=m-kpy=qy

可得：m=kpy+qy=(kp+q)y