欧几里得算法如何工作？

发布于 2024-11-07 18:45:17 字数 698 浏览 0 评论 0原文

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

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，但这却让我困惑。请帮忙？

原文

I just found this algorithm to compute the greatest common divisor in my lecture notes:

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

So r is the remainder when dividing b into a (get the mod). Then b is assigned to a, and the remainder is assigned to b, and a is returned. I can't for the life of my see how this works!

And then, apparently this algorithm doesn't work for all cases, and this one must then be used:

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;
}

I don't understand the reasoning behind this. I generally get recursion and am good at Java but this is eluding me. Help please?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

神也荒唐 2024-11-14 18:45:17

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，我们有两种情况：

如果 r = 0，则 a = bq，因此 b 可以整除 b 和 a。因此gcd(a,b)=b。
否则（r > 0），我们可以将求 gcd(a,b) 的问题简化为求 gcd(b,r) 的问题，它是完全相同的数（因为 a、b 和 r 都可以被 d 整除））。

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

现在， r = a % b 这有望解释您所拥有的代码。

回复收藏 0 原文

☆獨立☆ 2024-11-14 18:45:17

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

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

回复收藏 0 原文

无可置疑 2024-11-14 18:45:17

鉴于从未使用过“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 了解更多详细信息）

given that 'q' is never used, I don't see a difference between your plain iterative function, and the recursive iterative function... both do

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

Barring trying to apply this to non-integers, under which circumstances does this algorithm fail?

(also see http://en.wikipedia.org/wiki/Euclidean_algorithm for lots of detailed info)

回复收藏 0 原文