icancode.de

Größter gemeinsamer Teiler (iterativ)

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 (iterativ)

Veröffentlicht am .

Die Grundlagen und die rekursive Lösung habe ich ja bereits beschrieben. Der Vollständigkeit halber, hier noch die iterativen Lösungen:

Die alte Variante funktioniert wie folgt:

fun ggt(a: Int, b: Int): Int {
    var x = a
    var y = b
    if (a == 0) return b
    while (y != 0) {
        if (x > y) x -= y
        else y -= x
    }
    return x
} 

a und b müssen in separate, mutable Variablen überführt werden – also Felder, die veränderbar sind. Anschließend wird so lange eine Zahl von der anderen abgezogen, bis y = 0 ist.

Der moderne Algorithmus verwendet auch in der iterativen Implementierung den modulo Operator.

fun ggt(a: Int, b: Int): Int {
    var x = a
    var y = b
    while (y != 0) {
        val z = x.mod(y)
        x = y
        y = z
    }
    return x
}

Auch hier müssen die Parameter erst mutabel gemacht werden. Anschließend wird gerechnet. Das Ergebnis der Division mit Rest wird im Beispiel in dem Feld z zwischen gespeichert. Dieses kann immutable (unveränderbar) sein, da in jedem Schritt neu angelegt und nicht verändert wird. Natürlich ist auch eine Lösung möglich, die nur mutable Felder nutzt:

fun ggt(a: Int, b: Int): Int {
    var x = a
    var y = b
    var z: Int
    while (y != 0) {
        z = x.mod(y)
        x = y
        y = z
    }
    return x
}

Wie so oft sind die iterativen Implementierungen mehr Code als die rekursiven Lösungen. Dafür sind sie in der Regel einfacher lesbar bzw. nachvollziehbar, wenn der Algorithmus komplexer wird.

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