Python-Programm zur Ermittlung des größten gemeinsamen Teilers (HCF) oder der größten gemeinsamen Teilung (GCD)

Python-Beispiel大全

In diesem Beispiel werden Sie zwei verschiedene Methoden lernen, um den GCD von zwei Zahlen zu finden: Funktion und Schleifen sowie das Euklidische Algorithmus

Um diesen Beispiel zu verstehen, sollten Sie die folgenden Kenntnisse habenPython-ProgrammierungThema:

• Python-Funktion

• Python rekursiv

• Python-Funktion parameter

Der größte gemeinsame Teiler (H.C.F.) oder die größte gemeinsame Teilung (G.C.D.) ist der größte positive Ganzzahl, der beide gegebenen Zahlen perfekt teilen kann. Zum Beispiel, H.C.F.(12, 14) ist gleich2。

Quellcode: Verwenden Sie einen Schleifen

# Python-Programm zur Ermittlung des H.C.F. von zwei Zahlen
# Definieren Sie eine Funktion
def compute_hcf(x, y):
# Wählen Sie die kleinere Zahl
　　　　if x > y:
　　　　　　　　kleiner = y
　　　　else:
　　　　　　　　kleiner = x
　　　　for i in range(1, kleiner+1)
　　　　　　　　Wenn (x % i == 0) und (y % i == 0):
　　　　　　　　　　　　hcf = i　
　　　　return hcf
num1　=　54　
num2　=　24
print("Der HCF ist", compute_hcf(num1, num2))

Ausgaberesultat

Der HCF ist　6

Hier wird in der Variable num1und num2Zwei Ganzzahlen werden an die Funktion compute hcf() übergeben. Diese Funktion berechnet den H.C.F. dieser beiden Zahlen und gibt ihn zurück.

In dieser Funktion bestimmen wir zunächst das kleinere der beiden Zahlen F, das nur kleiner oder gleich dem kleinsten Wert sein kann. Dann verwenden wir einen for-Zyklus von1bis zu dieser Zahl.

In jeder Iteration überprüfen wir, ob unsere Zahl perfekt die beiden Eingabezahlen teilt. Wenn ja, speichern wir diese Zahl als H.C.F. und erhalten am Ende des Zyklus die größte Zahl, die perfekt die beiden Zahlen teilt.

Der obige Ansatz ist einfach zu verstehen und zu implementieren, aber nicht effizient. Eine effizientere Methode zum Finden des HCF ist der Euklidische Algorithmus.

Euklidischer Algorithmus

Dieser Algorithmus basiert auf der Tatsache: Der HCF zweier Zahlen teilt auch ihre Differenz.

In diesem Algorithmus teilen wir den größeren Wert durch den kleineren, nehmen den Rest und teilen den kleineren durch diesen Rest. Wiederholen Sie dies, bis der Rest 0 ist.

Beispielsweise, wenn wir den HCF berechnen möchten54und24der HCF, wir verwenden54geteilt durch24。 Der Rest ist6。24geteilt durch6，der Rest ist 0. Daher,6ist der notwendige HCF

Quellcode: Euklidischer Algorithmus verwenden

# Die Funktion zum Finden des HCF verwendet das Euklidische Algorithmus
def compute_hcf(x, y):
　　　while(y):
　　　　　　　x, y = y, x % y
　　　return x
hcf = compute_hcf(300,　400)
print("Der HCF ist", hcf)

Hier wiederholen wir den Kreislauf, bis y 0 wird. Der Ausdruck x, y = y, x % y tauscht die Werte in Python aus. Klicken Sie hier, um mehr zu erfahrenAustausch von Variablen in PythonMehr Informationen.

In jeder Iteration platzieren wir den Wert von y in x und den Rest (x % y) in y. Wenn y 0 wird, erhalten wir den HCF von x.

Python-Beispiel大全