0

5つの数値を要求してGCDを出力する簡単なプログラムを作成しようとしています。簡単な方法で2つの数値を使ってこれを行う方法をすでに発見しました。

private static int gcd(int number1, int number2) //Finds GCD of 2 numbers.
{
    if(number2 == 0)
    {
        return number1;
    }
    return gcd(number2, number1%number2);
}

returnステートメントの実際の計算は私を混乱させるものであり、5つ以上の数値でそれをどのように書き出すかはわかりません。「gcd（a、b、c）= gcd（gcd（a、b）、c）」のように再帰的にこの方法を実行するのが最善の方法だと聞きましたが、実際には問題があると思います。問題の数学の論理。本当に、3つの数値、次に4つ、次に5つなどを返す方法について、良い出発点が必要です。ロジック部分を理解したら、これをはるかに簡単に行う方法を理解できると思います。

4

2 に答える 2

3

gcd(int, int)既存の方法を「ブラックボックス」として扱う必要があります。新しいgcd(int, int, int, int, int)メソッドは、それがどのように機能するかを知らなくてもそれを呼び出すことができます。あなたは書くでしょう：

private static int gcd(int a, int b, int c, int d, int e)
{
    return gcd(gcd(a, b), gcd(gcd(c, d), e));
}

または、もう少し一般的な解決策として、 Java 5のvar-argsサポートを使用して、任意の正の数の引数gcd(int, int...)を取るメソッドを作成できます。

private static int gcd(int number1, int... otherNumbers)
{
    int result = number1;
    for(int number: otherNumbers)
        result = gcd(result, number);
    return result;
}

（どちらの場合も、この関数はプログラミングの意味で「再帰的」ではないことに注意してください。前者のアプローチは、の呼び出しを再帰的にネストしますがgcd(int, int)、これはプログラマーが「再帰」によって意味するものではありません。gcd(int, int)ただし、元の関数は再帰的です。 、実際には自分自身を呼び出すためです。）

于 2013-03-12T00:39:43.477 に答える
3

これが最大公約数の重要な視点です。寸法がmとnの長方形の床を考えてみてください。mとnのGCDは、その床に完全にフィットする最大の正方形のタイルの寸法です。

したがって、使用しているアルゴリズムでは、8と10などの2つの数値から始めます。次に、プログラムは1つの数値（たとえば8）と2つの数値のモジュラス（2）を使用してプロセスを繰り返します。これはチョッピングに相当します。残りのビットに入るタイルもその領域に収まることがわかっているので、8x8セクションから離れます。2x8のセクションが残っています。このプロセスを繰り返すと、GCDとして2が得られます。これにより、使用しているアルゴリズムの実際の意味が明らかになることを願っています。

したがって、この概念を3つの数値のGCDに拡張すると、m、n、およびpのGCDは、寸法がmxnxpの直角プリズムに収まる最大の立方体ブロックであると言えます。このGCDを見つけるには、まず、プリズムの面の1つに収まる正方形のタイルを見つけます。次に、この寸法を使用して、いわばプリズムの断面を切り取り、その断面のGCDを取得できます。もちろん、これは私たちが正確に視覚化できないより高い次元に拡張することができます！

于 2013-03-12T00:45:00.687 に答える