12

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

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分配给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，但这让我望而却步。请帮忙？

4

5 回答 5

27

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

基本上归结为这样一个事实：对于两个整数 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 希望能解释您拥有的代码。

于 2011-05-15T00:55:23.547 回答
1

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

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

于 2011-05-15T00:07:13.930 回答
0

鉴于从未使用过'q'，我看不出你的普通迭代函数和递归迭代函数之间有什么区别......两者都做

gdc(first number, second number)
  as long as (second number > 0) {
      int remainder = first % second;
      gcd = try(second as first, remainder as second);
  }
}

除非尝试将其应用于非整数，否则该算法在哪些情况下会失败？

（有关大量详细信息，另请参阅http://en.wikipedia.org/wiki/Euclidean_algorithm ）

于 2011-05-15T00:12:38.310 回答
0

这是一篇有趣的博客文章：Tominology。

在讨论欧几里得算法背后的许多直觉的地方，它是用 JavaScript 实现的，但我相信如果想要的话，将代码转换为 Java 并不困难。

于 2014-11-21T00:34:46.080 回答
-1

这是我发现的一个非常有用的解释。

对于那些懒得打开它的人来说，这就是它所说的：

考虑必须找到 (3084,1424) 的 GCD 的示例。让我们假设 d 是 GCD。这意味着 d | 3084 和 d | 1424（使用符号“|”表示“除”）。

由此得出 d | (3084 - 1424)。现在我们将尝试尽可能地减少这些可被 d 整除的数字（在本例中为 3084 和 1024），以便我们达到 0 作为数字之一。请记住，GCD (a, 0) 是 a。

自 d | (3084 - 1424)，因此 d | ( 3084 - 2(1424) ) 这意味着 d | 236.
提示：（3084 - 2*1424 = 236）

现在忘记初始数字，我们只需要求解 d，我们知道 d 是除以 236、1424 和 3084 的最大数字。所以我们使用较小的两个数字继续，因为它会使问题收敛到 0 .

d | 1424 和 d | 236 意味着 d | （1424 - 236）。
所以，d | ( 1424 - 6(236) ) => d | 8.

现在我们知道 d 是除以 8、236、1424 和 3084 的最大数。再次取较小的两个，我们有

d | 236 和 d | 8，这意味着 d | (236 - 8)。
所以，d | ( 236 - 29(8) ) => d | 4.

可被 d 整除的数字列表再次增加并收敛（数字越来越小，接近于 0）。就目前而言，d 是除以 4、8、236、1424、3084 的最大数。

采取同样的步骤，

d | 8 和 d | 4 暗示 d | (8-4)。
所以，d | ( 8 - 2(4) ) => d | 0。

可被 d 整除的数字列表现在是 0、4、8、236、1484、3084。 (a, 0) 的 GCD 始终为 a。因此，一旦您将 0 作为两个数字之一，另一个数字就是原始两个的 gcd 以及介于两者之间的所有数字。

这正是您的代码正在做的事情。您可以将终止条件识别为 GCD (a, 0) = a。

另一个步骤是找到两个数字的余数，并选择它和前两个数字中较小的一个作为新数字。

于 2015-02-22T09:32:56.267 回答