java - 欧几里得算法是如何工作的？

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的余数(取模)。然后将b赋给a，余数赋给b，返回a。我这辈子都看不懂这是怎么回事!

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

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

Wikipedia article 包含一个解释，但不容易立即找到它(而且，过程 + 证明并不总是回答“为什么它有效”的问题)。

基本上可以归结为这样一个事实，即对于两个整数 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 整除。

总结一下:我们有 a = 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 这有望解释您的代码。