In diesem Beispiel lernen Sie, die GCD zweier Zahlen mit zwei verschiedenen Methoden zu ermitteln: Funktion und Schleifen und euklidischer Algorithmus
Um dieses Beispiel zu verstehen, sollten Sie die folgenden Python-Programmierthemen kennen:
- Python-Funktionen
- Python-Rekursion
- Python-Funktionsargumente
Der höchste gemeinsame Faktor (HCF) oder der größte gemeinsame Teiler (GCD) zweier Zahlen ist die größte positive ganze Zahl, die die beiden angegebenen Zahlen perfekt teilt. Zum Beispiel ist der HCF von 12 und 14 2.
Quellcode: Verwenden von Schleifen
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Ausgabe
Der HCF beträgt 6
Hier werden zwei in den Variablen num1 und num2 gespeicherte Ganzzahlen an die compute_hcf()Funktion übergeben. Die Funktion berechnet dem HCF diese beiden Zahlen und gibt sie zurück.
In der Funktion bestimmen wir zunächst die kleinere der beiden Zahlen, da der HCF nur kleiner oder gleich der kleinsten Zahl sein kann. Wir verwenden dann eine forSchleife, um von 1 zu dieser Zahl zu gelangen.
In jeder Iteration prüfen wir, ob unsere Zahl beide eingegebenen Zahlen perfekt teilt. In diesem Fall speichern wir die Zahl als HCF. Nach Abschluss der Schleife erhalten wir die größte Zahl, die beide Zahlen perfekt teilt.
Die obige Methode ist leicht zu verstehen und zu implementieren, aber nicht effizient. Eine viel effizientere Methode zum Auffinden des HCF ist der euklidische Algorithmus.
Euklidischer Algorithmus
Dieser Algorithmus basiert auf der Tatsache, dass HCF aus zwei Zahlen auch ihre Differenz teilt.
In diesem Algorithmus teilen wir das Größere durch das Kleinere und nehmen den Rest. Teilen Sie nun den kleineren durch diesen Rest. Wiederholen, bis der Rest 0 ist.
Wenn wir zum Beispiel den HCF von 54 und 24 finden wollen, teilen wir 54 durch 24. Der Rest ist 6. Nun teilen wir 24 durch 6 und der Rest ist 0. Daher ist 6 der erforderliche HCF
Quellcode: Verwendung des euklidischen Algorithmus
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Hier schleifen wir, bis y Null wird. Die Anweisung x, y = y, x % ytauscht Werte in Python aus. Klicken Sie hier, um mehr über das Austauschen von Variablen in Python zu erfahren.
In jeder Iteration platzieren wir gleichzeitig den Wert von y in x und den Rest (x % y)in y. Wenn y Null wird, haben wir HCF in x.
