欧几里德算法如何工作？

Question

我刚刚发现这个算法来计算我的讲义中最大的公约数:

public static int gcd( int a, int b ) {
    while (b != 0) {
        final int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

所以r是将b分成a(得到mod)时的余数.然后b被分配给一个,其余被分配给b,和一个被返回.我不能为我的生活看到它如何运作!

然后,显然这个算法不适用于所有情况,然后必须使用这个:

public static int gcd( int a, int b ) {
    final int gcd;
    if (b != 0) {
        final int q = a / b;
        final int r = a % b; // a == r + q * b AND r == a - q * b.
        gcd = gcd( b, r );
    } else {
        gcd = a;
    }
    return gcd;
}

我不明白这背后的原因.我通常得到递归并且擅长Java,但这是在逃避我.请帮忙？

Answer 1

在维基百科的文章包含的解释,但它不容易立刻找到它(也,程序+证明并不总是回答"为什么它的工作原理").

基本上,它归结为这样的事实:对于两个整数a,b(假设a> = b),总是可以写a = bq + r,其中r <b.

如果d = gcd(a,b),那么我们可以写a = ds和b = dt.所以我们有ds = qdt + r.由于左侧可被d整除,因此右侧也必须可被d整除.由于qdt可被d整除,因此结论是r也必须能被d整除.

总结一下:我们有一个= bq + r,其中r <b和a,b和r都可被gcd(a,b)整除.

由于a> = b> r,我们有两种情况:

1. 如果r = 0则a = bq,因此b除以b和a.因此gcd(a,b)= b.
2. 否则(R> 0),就可以减少寻找GCD的问题(A,B),以找到满足gcd(B,R),它是完全相同的数目(为a,b和r都是由d整除)的问题.

为什么减少？因为r <b.所以我们正在处理的数字肯定更小.这意味着我们只需要在达到r = 0之前将这种减少应用有限次数.

现在,r = a%b,希望能解释你的代码.

Answer 2

它们是等价的。首先要注意的是，q在第二个程序中根本没有使用它。另一个区别只是迭代与递归。

至于为什么它有效，上面链接的维基百科页面很好。第一个插图特别有效地直观地传达了“为什么”，下面的动画则说明了“如何”。