Euklidischer Algorithmus mit Python

Der Euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Mit ihm lässt sich der größte gemeinsame Teiler zweier natürlicher Zahlen berechnen. Das Verfahren ist nach dem griechischen Mathematiker Euklid benannt, der es in seinem Werk „Die Elemente“ beschrieben hat. http://de.wikipedia.org/wiki/Euklidischer_Algorithmus

rekursive Variante

Diese Variante ist durch den rekursiven Aufruf der Funktion euklid_rek(wert_1,wert_2) mit den Parametern (wert_2,(wert_1 % wert_2)) (% steht in Python für Modulo; Modulo = Rest der ganzzahligen Division) gekennzeichnet. Zur Veranschaulichung der Aufrufe wurde die Zeile print("rekursiver Aufruf mit:",str(wert_1),str(wert_2)) eingefügt.

Die erste Zeile #! /usr/bin/env python3 ermöglicht unter Linux das direkte Ausführen des ausführbar gemachten Python-Skriptes ohne Aufruf des Interpreters.

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

# Euklidischer Algorithmus (ggT) rekursiv
print("Berechnung des größten gemeinsamen Teilers")
print("mit einem rekursiven euklidischen Algorithmus")
print("=============================================")
print(" ")

# Eingabe
print("Eingabe der Startwerte:")
print("-----------------------")
zahl_1 = int(input("erste ganze Zahl:  "))
zahl_2 = int(input("zweite ganze Zahl: "))

# Rekursion als Funktion
def euklid_rek(wert_1,wert_2):
    if wert_2 == 0:
        return wert_1
    else:
        print("rekursiver Aufruf mit:",str(wert_1),str(wert_2))
        return euklid_rek(wert_2,(wert_1 % wert_2))

# Funktionsaufruf und Ausgabe
print(" ")
print("Ergebnis:")
print("---------")
print("Der größte gemeinsame Teiler ist " + str(euklid_rek(zahl_1,zahl_2)))

iterative Variante

Bei der iterativen Variante wird an Stelle des rekursiven Aufrufes der Funktion eine while-Schleife verwendet. Eingabe, Funktionsaufruf und Ausgabe sind analog zur rekursiven Variante. Die Zeile print("Schleifendurchlauf mit:",str(wert_1),str(wert_2)) dient hier ebenfalls zur Veranschaulichung.

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

# Euklidischer Algorithmus (ggT) iterativ
print("Berechnung des größten gemeinsamen Teilers")
print("mit einem iterativen euklidischen Algorithmus")
print("=============================================")
print(" ")

# Eingabe
print("Eingabe der Startwerte:")
print("-----------------------")
zahl_1 = int(input("erste ganze Zahl:  "))
zahl_2 = int(input("zweite ganze Zahl: "))

# Iteration als Funktion
def euklid_it(wert_1,wert_2):
    while wert_2 != 0:
        print("Schleifendurchlauf mit:",str(wert_1),str(wert_2))
        hilfswert = wert_1 % wert_2
        wert_1 = wert_2
        wert_2 = hilfswert
    return wert_1

# Funktionsaufruf und Ausgabe
print(" ")
print("Ergebnis:")
print("---------")
print("Der größte gemeinsame Teiler ist " + str(euklid_it(zahl_1,zahl_2)))