java - 欧几里得算法不正确的结果

Question

我正在尝试编写 Euclid 算法的 Java 实现：我的方法的主体如下所示：

    while(a%b != 0) {
        int newA = b * ((int) Math.floor(a/b));
        int newB = a - newA;

        a = newA;
        b = newB;
    }
    return a;

但是，我不断得到不正确的结果......我认为我有一个逻辑错误，但真的不明白它在哪里：\

有任何想法吗？

Answer 1

欧几里得算法如下：

1. 如果 a < b，则交换（a，b）；
2. [a, b] = [b, a % b]，直到 a % b == 0；
3. 返回 b.

您的代码有多个问题，但更突出的是您正在返回a，而不是b.

另一件事：不要试图重新发明%（余数）运算符。

Answer 2

在欧几里得算法中，每一步都必须为a分配旧的b，并且b必须分配a%b。您正在正确计算 b 的新值，但对于 a 您正在计算类似a = a - a%b.

为了一个简单的修复，您可以将设置 a 值的行替换为简单的：

a = b;

（即在设置新b之前）

Answer 3

我想这会对你有很大帮助。Java中的欧几里得算法

代码

// non-recursive implementation
public static int gcd2(int p, int q) {
    while (q != 0) {
        int temp = q;
        q = p % q;
        p = temp;
    }
    return p;
}