icancode.de

Größter gemeinsamer Teiler (rekursiv)

Einleitung

Rico Magnucki

Rico Magnucki

21st Century Digital Boy und Blog-Gründer. Studiert naturwissenschaftliche Informatik in Bielefeld. Auf dem Blog ist er der Ansprechpartner für LaTeX, schreibt Tutorials, dreht die Videos für YouTube und durchforstet das Internetz nach spannenden Dingen.


Neuste Artikel

HP Deskjet 3636 – Multitalent zum schmalen Preis 09th April, 2017

NETGEAR AC1750 Smart WLAN-Router im Test 10th January, 2016

Kotlin

Größter gemeinsamer Teiler (rekursiv)

Veröffentlicht am .

Neue Programmiersprachen lernen sich am besten mit Beispielen. Da mir nicht immer passende Beispiele einfallen, bediene ich mich gerne bei den Basics aus dem Bachelor Studium. So z.B. auch am größten gemeinsamen Teiler (ggT).

Berechnet wird der größte gemeinsame Teiler in der Regel über den euklidischen Algorithmus.

Did you mean: recursion?

Meinten Sie Rekursion? - icancode.deDieser Algorithmus wird allgemein gern verwendet, um Rekursion zu erklären. Ich setze jetzt mal voraus, ihr wisst wie Rekursion funktioniert. Sonst googlet das doch einfach mal ;)

Zurück zum größten gemeinsamen Teiler. Die beiden Spezialfälle a = 0 und b = 0 sind klar – sie geben einfach die andere Zahl zurück.

if (a == 0) return b
if (b == 0) return a

Für die restliche Berechnung reicht eine Fallunterscheidung:

if (a > b) return ggt(a - b, b)
else return ggt (a, b - a)

Ist a größer als b, dann wird ggt erneut aufgerufen. Diesmal aber mit den Werten a - b und b. Ist a kleiner als b rufen wir ggt mit a und b - a auf.

Das wird jetzt so lange wiederholt, bis a oder b 0 ist. Komplett haben wir dann folgende Methode:

fun ggt(a: Int, b: Int): Int {
    if (a == 0) return b
    if (b == 0) return a
    if (a > b) return ggt(a - b, b)
    else return ggt (a, b - a)
}

Das muss doch schöner gehen…

Geht es auch. Der moderne euklidische Algorithmus ist noch kürzer.

fun ggt(a: Int, b: Int): Int {
    if (b == 0) return a
    return ggt(b, a.mod(b))
}

Hier wird sich des modulo Operators bedient – der Division mit Rest also. Es gibt die gleiche Abbruchbedingung wie in der ersten Variante: b == 0

Sollte das nicht der Fall sein, wird die Methode erneut aufgerufen. Diesmal aber mit den Werten b und a modulo b.

Warum funktioniert das?

Wir haben nur eine Abbruchbedingung definiert, warum funktioniert das Programm dann trotzdem? Weil 0 mod x 0 als Ergebnis liefert. Demnach sind die Werte im nächsten Schritt x , 0 und die Abbruchbedingung ist erfüllt.

Weiter zu: größter gemeinsamer Teiler (iterativ)

Rico Magnucki

Rico Magnucki

http://magnucki.de

21st Century Digital Boy und Blog-Gründer. Studiert naturwissenschaftliche Informatik in Bielefeld. Auf dem Blog ist er der Ansprechpartner für LaTeX, schreibt Tutorials, dreht die Videos für YouTube und durchforstet das Internetz nach spannenden Dingen.

Navigation