Comment trouver le plus grand diviseur commun en langage C

La méthode d'implémentation pour trouver le plus grand diviseur commun en langage C nécessite des exemples de code spécifiques

Le plus grand diviseur commun, appelé le plus grand commun diviseur, fait référence à la valeur maximale parmi les diviseurs partagés par deux entiers ou plus. Dans la conception d’algorithmes, trouver le plus grand diviseur commun est un problème courant. Ce qui suit présentera en détail plusieurs méthodes d'implémentation du plus grand diviseur commun en langage C et fournira des exemples de code spécifiques.

Méthode 1 : Méthode par force brute
La méthode par force brute est une méthode simple et directe, en parcourant tous les diviseurs possibles puis en trouvant le plus grand diviseur comme plus grand diviseur commun.

#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;
}

Méthode 2 : Division euclidienne
La division euclidienne (également connue sous le nom d'algorithme euclidien) est basée sur un principe mathématique simple : le plus grand commun diviseur de deux entiers est égal au plus grand commun diviseur du plus petit nombre et à la différence entre les deux nombres.

#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;
}

Méthode 3 : Méthode de soustraction de phase supplémentaire
La méthode de soustraction de phase supplémentaire est également une méthode plus couramment utilisée pour trouver le plus grand diviseur commun. Elle obtient la différence entre deux nombres en les soustrayant continuellement, puis trouve le plus grand diviseur commun. de la différence jusqu'à ce que les deux nombres Les nombres soient égaux.

#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;
}

Ces trois façons courantes d'implémenter le plus grand dénominateur commun en langage C. Grâce à différentes idées algorithmiques, nous pouvons choisir la méthode appropriée à résoudre dans différents scénarios et sélectionner l'implémentation du code correspondante en fonction de besoins spécifiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!