1

ユーザーが入力した 3 つの数値の 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

私が気づいた間違いの 1 つ、あなたの if 条件が間違っています:

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

これら 3 つの数値の GCD はそれぞれ以下であるため、次のように変更します。

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

このように数値を繰り返しテストする場合は、特定の数値とカウントダウンから開始して、条件を満たす数値が実際の G​​CD であることを保証できるようにする必要があります。そして、その特定の開始番号は、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 を 2 つの数値で実装し、そのメソッドを 3 つの数値で呼び出すことができます。

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

次に、3 つの数値の場合:

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確かに true であり、largeVar を 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);
}

maximumVar を正しく処理するように変更されました。その点に注意を払っていませんでした。ローカル スコープであるため、largeVar の値は再帰呼び出しでは保持されないため、recursiveMethod 呼び出しにも渡す必要があります (それか、クラス スコープ変数として宣言するなど)。適切な開始値は 0 です。

于 2013-01-08T21:07:30.357 に答える
0

毎回 1 ずつ 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 に答える