Programme C++ pour calculer le plus grand facteur commun

Le facteur commun le plus élevé ou le plus grand diviseur commun est un facteur qui peut diviser deux ou plusieurs valeurs simultanément sans produire de reste. Dans cet article, nous aborderons plusieurs façons d’effectuer HCF/PGCD de deux nombres en C++.

Ceci n'est qu'une solution mathématique, il existe plusieurs algorithmes pour trouver le plus grand diviseur commun. La méthode euclidienne est une méthode courante pour trouver le plus grand diviseur commun. Nous utiliserons le même algorithme en mode itératif et récursif.

Utilisez des méthodes itératives

La solution itérative euclidienne pour trouver le plus grand diviseur commun est présentée dans la section algorithme.

Algorithme

• Prenez deux nombres a et b en entrée.
• Si a est égal à 0, renvoie b.
• Si b est 0, renvoie a.
• Lorsque a et b ne sont pas identiques, effectuez l'opération.
  • Si a > alors a := a – b.
  • Sinon b := b - a.
• Terminez la boucle.
• Renvoyer le plus grand commun diviseur sous forme de variable a.

Exemple

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   else if (y == 0)
      return x;
   while (x != y) {
      if (x > y)
         x = x - y;
      else
         y = y - x;
   }
   return x;
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) <<   endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

Sortie

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

Utilisez des méthodes itératives

La même méthode euclidienne peut être implémentée en utilisant des méthodes récursives. Nous décrivons ci-dessous la définition d'une méthode récursive, l'algorithme présenté ci-dessous.

Algorithme

• Définissez une fonction appelée HCF qui accepte deux nombres a et b.
• Si a vaut 0, renvoie b
• Sinon, retournez HCF (b mod a, a)

Exemple

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   return solve( y % x, x );
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) << endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

Sortie

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

Conclusion

Trouver le plus grand facteur commun ou le plus grand diviseur commun est très utile pour résoudre différents problèmes mathématiques. Il peut être calculé à l'aide de la méthode euclidienne. Cette méthode peut être appliquée de manière itérative ou récursive. Nous montrons ici deux méthodes. D'un autre côté, nous pouvons calculer GCD/HCF via le plus petit commun multiple (LCM). Le PGCD et le LCM de deux nombres sont identiques au produit des deux nombres. Ainsi, selon ce principe, si l’on connaît le LCM et le produit de ces deux nombres, on peut facilement calculer le PGCD.

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!