java-greatest-common-divisor

投稿日: 2019-10-18 2019-10-18
タグ: Algorithms, Java

Javaで最大公約数を見つける

1. 概要

数学では、非ゼロの2つの整数のhttps://en.wikipedia.org/wiki/Greatest_common_divisor[GCD]は*各整数を均等に分割する最大の正の整数*です。

このチュートリアルでは、2つの整数の最大公約数（GCD）を見つけるための3つのアプローチを見ていきます。 さらに、Javaでの実装を見ていきます。

[[brute force method]]
=== 2. 強引な

最初のアプローチでは、1から指定された最小数まで繰り返し、指定された整数がインデックスで割り切れるかどうかを確認します。 *指定された数値を分割する最大のインデックス*は、指定された数値のGCDです：

int gcdByBruteForce(int n1, int n2) {
    int gcd = 1;
    for (int i = 1; i <= n1 && i <= n2; i++) {
        if (n1 % i == 0 && n2 % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

ご覧のとおり、上記の実装の複雑さは_O（min（n1、n2））_です。これは、GCDを見つけるために_n_回（小さい数に相当する）ループを繰り返す必要があるためです。

[[euclid’s algorithm]]
=== 3. ユークリッドのアルゴリズム

第二に、ユークリッドのアルゴリズムを使用してGCDを見つけることができます。 Euclidのアルゴリズムは効率的であるだけでなく、Javaの再帰を使用して理解しやすく、実装も簡単です。

ユークリッドの方法は、2つの重要な定理に依存しています。

まず、大きい数字から小さい数字を引くと、
GCDは変更されません-そのため、数値を引き続き減算すると、最終的にGCD *になります

第二に、小さい数字が大きい数字を正確に除算すると、
小さい数字は、指定された2つの数字のGCDです。

実装では、基本的に一度に多くの減算が行われるため、減算ではなくモジュロを使用することに注意してください。

int gcdByEuclidsAlgorithm(int n1, int n2) {
    if (n2 == 0) {
        return n1;
    }
    return gcdByEuclidsAlgorithm(n2, n1 % n2);
}

また、_n1_の位置で_n2_を使用し、アルゴリズムの再帰ステップでn2の位置で残りを使用する方法に注意してください__.__

さらに、*ユークリッドのアルゴリズムの複雑さは_O（Log min（n1、n2））_であり、これは前に見たブルートフォース法と比較して優れています*。

[[stein’s algorithm or binary gcd algorithm]]
=== 4. スタインのアルゴリズムまたはバイナリGCDアルゴリズム

最後に、*バイナリGCDアルゴリズムとも呼ばれる* Steinのアルゴリズムを使用して、2つの非負整数のGCDを見つけることができます。 このアルゴリズムは、算術シフト、比較、減算などの単純な算術演算を使用します。

Steinのアルゴリズムは、GCDに関連する次の基本的なIDを繰り返し適用して、2つの非負整数のGCDを見つけます。

gcd（0、0）= 0、gcd（n1、0）= n1、gcd（0、n2）= n2
n1_と_n2_が両方とも偶数の場合、_gcd（n1、n2）= 2 *
gcd（n1 / 2、n2 / 2）、2が公約数であるため
n1_が偶数の整数で、_n2_が奇数の整数の場合、_gcd（n1、n2）=
gcd（n1 / 2、n2）、2は公約数ではなく、その逆も同じであるため

_n1_と_n2_が両方とも奇数の整数で、_n1> = n2_の場合、_gcd（n1、
n2）= gcd（（n1-n2）/ 2、n2）_およびその逆

_n1_が_n2_に等しくなるまで、または_n1 = 0_になるまで手順2〜4を繰り返します。 GCDは_（2 ^ n ^）* n2_です。 ここで、_n_は、ステップ2の実行中に_n1_と_n2_に共通して2が見つかった回数です。

int gcdBySteinsAlgorithm(int n1, int n2) {
    if (n1 == 0) {
        return n2;
    }

    if (n2 == 0) {
        return n1;
    }

    int n;
    for (n = 0; ((n1 | n2) & 1) == 0; n++) {
        n1 >>= 1;
        n2 >>= 1;
    }

    while ((n1 & 1) == 0) {
        n1 >>= 1;
    }

    do {
        while ((n2 & 1) == 0) {
            n2 >>= 1;
        }

        if (n1 > n2) {
            int temp = n1;
            n1 = n2;
            n2 = temp;
        }
        n2 = (n2 - n1);
    } while (n2 != 0);
    return n1 << n;
}

2で除算または乗算するために算術シフト演算を使用していることがわかります。 さらに、指定された数値を減らすために減算を使用します。

n1> n2_の場合のSteinのアルゴリズムの複雑さは_O（（log〜2〜n1）^ 2 ^）_です。 _n1 <n2、_の場合、_O（（log〜2〜n2）^ 2 ^）. *

5. 結論

このチュートリアルでは、2つの数値のGCDを計算するためのさまざまな方法を見ました。 また、これらをJavaで実装し、その複雑さを簡単に確認しました。

いつものように、ここでの例の完全なソースコードは、いつものようにhttps://github.com/eugenp/tutorials/tree/master/java-math[over on GitHub]です。

getdocs

9427