Euklidischer Algorithmus in Python
Der euklidische Algorithmus ersetzt ein Zahlenpaar wiederholt durch Divisor und Rest.
Was ist Euklidischer Algorithmus?
Der euklidische Algorithmus ersetzt ein Zahlenpaar wiederholt durch Divisor und Rest.
Bestimme den größten gemeinsamen Teiler zweier Zahlen.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Beispielcode
main.py
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))Erwartete Ausgabe
6So funktioniert es
Sobald der Rest null ist, enthält die andere Variable den ggT. Das Verfahren arbeitet in O(log min(a,b)).
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.