Comment utiliser l'algorithme multiple le moins courant en C++

Comment utiliser l'algorithme multiple le moins commun en C++

Le multiple le plus petit commun (Least Common Multiple, appelé LCM) fait référence au plus petit multiple commun de deux entiers ou plus. En mathématiques et en informatique, trouver le plus petit commun multiple est un problème courant, et C++ fournit un moyen simple et efficace de calculer le plus petit commun multiple. Cet article explique comment utiliser l'algorithme multiple le moins courant en C++ et fournit des exemples de code spécifiques.

Tout d’abord, comprenons la définition du plus petit commun multiple. Pour deux entiers a et b, leur plus petit commun multiple peut être calculé par la formule suivante :

LCM(a, b) = (a * b) / GCD(a, b)

où, GCD représente le plus grand commun maximum Diviseur. En C++, vous pouvez utiliser l'algorithme euclidien pour calculer le plus grand commun diviseur de deux entiers, puis remplacer le plus grand commun diviseur dans la formule ci-dessus pour trouver le plus petit commun multiple.

Ce qui suit est un exemple de code pour l'algorithme multiple le moins courant écrit en C++ :

// 求两个整数的最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// 求两个整数的最小公倍数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int a = 6;
    int b = 8;
    int result = lcm(a, b);
    std::cout << "最小公倍数是：" << result << std::endl;
    return 0;
}

Dans le code ci-dessus, nous définissons d'abord une fonction pgcd qui calcule le plus grand diviseur commun, qui est implémenté de manière récursive. Ensuite, nous avons défini une fonction lcm qui calcule le plus petit commun multiple. Elle appelle la fonction pgcd pour trouver le plus grand commun diviseur de deux entiers avant de calculer le plus petit commun multiple, et substitue le plus grand commun diviseur dans la formule ci-dessus pour calculer la valeur de le multiple le plus commun. Enfin, dans la fonction principale, nous définissons deux entiers a et b et appelons la fonction lcm pour calculer leur plus petit commun multiple et afficher le résultat.

En utilisant le code C++ ci-dessus, nous pouvons facilement trouver le plus petit commun multiple de deux entiers. Bien entendu, si nécessaire, nous pouvons également encapsuler le code en conséquence pour le rendre plus adapté aux scénarios d'application réels.

Pour résumer, cet article explique comment utiliser l'algorithme multiple le moins commun en C++, y compris le calcul du plus grand diviseur commun et la détermination du plus petit commun multiple, et fournit des exemples de code correspondants. En comprenant et en appliquant ces algorithmes, nous pouvons utiliser le C++ de manière flexible pour résoudre le problème de calcul multiple le moins courant dans des problèmes pratiques.

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!