1

我正在尝试创建代码来查找三个用户输入数字的 GCD。我的目标是用输入的数字调用该方法，除以初始化为 1 的 q，仅当余数为零时记录 q，然后确定它是否大于或等于最小数字，如果不是，则增加 q 和召回方法，但如果我想打印出最后记录的最大 q，我做错了什么？我不断收到堆栈溢出错误。

public static int recursiveMethod (int x, int y, int z, int q)
{
    int largestVar; 
    int xRes = x % q;
    int yRes = y % q;
    int zRes = z % q;
    if (xRes==0 && yRes ==0 && zRes==0) {
                largestVar = q;
                if (q >= x && q >= y && q >= z)
                {
                    return largestVar;
                }
    }
    else { 
           q++;
    }
   return recursiveMethod(x, y, z, q);
4

4 回答 4

4

我注意到的错误之一是您的 if 条件错误：

if (q >= x && q >= y && q >= z)

这3个数的GCD都小于等于每一个，所以改成：

if (x >= q && y >= q && z >= q)

如果你像这样迭代地测试数字，你应该从某个数字开始倒计时，这样你就可以保证满足条件的数字就是实际的 GCD。并且那个特定的起始数字必须是最少的 3 个数字。 您的方法的完整工作版本在这里：

public static int recursiveMethod(int x, int y, int z, int q) 
{
    int largestVar;
    int xRes = x % q;
    int yRes = y % q;
    int zRes = z % q;
    if (xRes == 0 && yRes == 0 && zRes == 0) {
        largestVar = q;
        if (x >= q && y >= q && z >= q) {
            return largestVar;
        }
    } else {
        q--;
    }
    return recursiveMethod(x, y, z, q);
}

示例调用：

int x = recursiveMethod(30, 60, 45, 30); // x = 15 after this execution.
于 2013-01-08T20:58:21.140 回答
2

不要忘记gcd(x, y, z) = gcd(gcd(x, y), z).所以，如果你想要一个更简单的算法，你可以用两个数字实现 gcd，然后为 3 个数字调用该方法。

public static int GCD(int x, int y) {
   if (y == 0) return x;
   return GCD(x, x % y);
}

然后是三个数字：

public static int GCDfor3 (int x, int y, int z) {
    return GCD(GCD(x, y), z)
}
于 2013-01-08T21:02:55.667 回答
1

您的第一种情况将是 1，此时xRes==0 && yRes ==0 && zRes==0肯定是正确的，并且您将最大变量设置为 1。然后，由于 1 可能小于传入的变量，它继续，不会在 else 块中增加 q，并recursiveMethod调用q=1 再次！这个过程会不断重复。

public static int recursiveMethod (int x, int y, int z, int q, int largestVar)
{
    int xRes = x % q;
    int yRes = y % q;
    int zRes = z % q;
    if (xRes==0 && yRes ==0 && zRes==0) {
    //A common denominator found!
                largestVar = q;
    }
    //regardless whether a denominator was found, check for the termination condition
    //Or works here, by the way, since we only need to know when q is greater than one of them.
    if (q >= x || q >= y || q >= z) {
        return largestVar;
    }
    //if we don't terminate, increment q and recurse. 
    q++;
    return recursiveMethod(x, y, z, q, largestVar);
}

修改为正确处理最大变量。没注意那一点。作为局部作用域，最大变量的值不会通过递归调用来维护，因此它也必须传递到 recursiveMethod 调用中（或者被声明为类作用域变量，等等）。一个合适的起始值是 0。

于 2013-01-08T21:07:30.357 回答
0

如果您每次将 Q 加一，使用合适的数字，您总是会用完堆栈。我会对每对数字使用欧几里得算法，然后从那里开始。我的意思是，如果它在 a、b、c 之间是共同的，那么它必须是 a 和 b 或 a 和 c 或 c 和 b 之间的公因数，对吧？

https://math.stackexchange.com/questions/85830/how-to-use-the-extended-euclidean-algorithm-manually

于 2013-01-08T21:00:48.787 回答