C++-Programm zur Berechnung des größten gemeinsamen Faktors

Der höchste gemeinsame Faktor oder größte gemeinsame Teiler ist ein Faktor, der zwei oder mehr Werte gleichzeitig dividieren kann, ohne dass ein Rest entsteht. In diesem Artikel besprechen wir verschiedene Möglichkeiten, HCF/GCD von zwei Zahlen in C++ durchzuführen.

Dies ist nur eine mathematische Lösung. Es gibt mehrere Algorithmen, um den größten gemeinsamen Teiler zu finden. Die euklidische Methode ist eine übliche Methode, um den größten gemeinsamen Teiler zu ermitteln. Wir werden denselben Algorithmus im iterativen und rekursiven Modus verwenden.

Verwenden Sie iterative Methoden

Die euklidische iterative Lösung zum Finden des größten gemeinsamen Teilers wird im Abschnitt „Algorithmus“ angezeigt.

Algorithmus

• Nehmen Sie zwei Zahlen a und b als Eingabe.
• Wenn a gleich 0 ist, gib b zurück.
• Wenn b 0 ist, gib a zurück.
• Wenn a und b nicht identisch sind, führen Sie den Vorgang aus.
  • Wenn a > b, dann a := a – b.
  • Sonst b := b - a.
• Beende die Schleife.
• Gib den größten gemeinsamen Faktor als Variable a zurück.

Beispiel

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

Ausgabe

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

Verwenden Sie iterative Methoden

Die gleiche euklidische Methode kann mit rekursiven Methoden implementiert werden. Im Folgenden beschreiben wir die Definition einer rekursiven Methode, den unten gezeigten Algorithmus.

Algorithmus

• Definieren Sie eine Funktion namens HCF, die zwei Zahlen a und b akzeptiert.
• Wenn a 0 ist, gib b zurück
• Andernfalls gib HCF( b mod a, a) zurück

Beispiel

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

Ausgabe

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

Fazit

Das Finden des größten gemeinsamen Faktors oder des größten gemeinsamen Teilers ist bei der Lösung verschiedener mathematischer Probleme sehr nützlich. Sie kann mit der euklidischen Methode berechnet werden. Diese Methode kann iterativ oder rekursiv angewendet werden. Hier zeigen wir zwei Methoden. Andererseits können wir GCD/HCF über das kleinste gemeinsame Vielfache (LCM) berechnen. Der GCD und der LCM zweier Zahlen sind dasselbe wie das Produkt der beiden Zahlen. Wenn wir also nach diesem Prinzip den LCM und das Produkt dieser beiden Zahlen kennen, können wir den GCD leicht berechnen.

Das obige ist der detaillierte Inhalt vonC++-Programm zur Berechnung des größten gemeinsamen Faktors. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!