C言語で最大公約数を求める方法

#C 言語で最大公約数を求める実装方法には、具体的なコード例が必要です。

最大公約数と呼ばれる最大公約数は、次の 2 つを指します。以上の整数 公約数のうちの最大値。アルゴリズム設計では、最大公約数を見つけることがよくある問題です。以下では、C 言語で最大公約数を実装するいくつかの方法を詳細に紹介し、具体的なコード例を示します。

方法 1: ブルート フォース メソッド

ブルート フォース メソッドは、考えられるすべての約数を調べて、最大公約数として最大の約数を見つけるという、単純かつ直接的な方法です。

#include <stdio.h>

int gcd(int a, int b) {
    int i, result = 1;

    for(i = 1; i <= a && i <= b; i++) {
        if(a % i == 0 && b % i == 0) {
            result = i;
        }
    }

    return result;
}

int main() {
    int a, b;

    printf("请输入两个整数：
");
    scanf("%d%d", &a, &b);

    printf("最大公约数为：%d
", gcd(a, b));

    return 0;
}

方法 2: ユークリッド除算法

ユークリッド除算法 (ユークリッド アルゴリズムとも呼ばれる) は、2 つの整数の最大公約数が小さい方の数に等しいという単純な数学的原理に基づいています。数値: 差異の最大公約数。

#include <stdio.h>

int gcd(int a, int b) {
    int remainder;

    while(b != 0) {
        remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

int main() {
    int a, b;

    printf("请输入两个整数：
");
    scanf("%d%d", &a, &b);

    printf("最大公约数为：%d
", gcd(a, b));

    return 0;
}

方法 3: 多相減算法

多相減算法も、最大公約数を見つけるためによく使用される方法です。2 つの数値を継続的に減算して差を取得し、その後、 2 つの数値が等しくなるまでの最大公約数。

#include <stdio.h>

int gcd(int a, int b) {
    while(a != b) {
        if(a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }

    return a;
}

int main() {
    int a, b;

    printf("请输入两个整数：
");
    scanf("%d%d", &a, &b);

    printf("最大公约数为：%d
", gcd(a, b));

    return 0;
}

上記は、C 言語で最大公約数を実現するための 3 つの一般的な方法です。さまざまなアルゴリズムのアイデアを通じて、さまざまなシナリオで解決するための適切な方法を選択し、特定のニーズに応じて対応するコードを選択できます。成し遂げる。

以上がC言語で最大公約数を求める方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。