Tag Archives: Source

Die Türme von Hanoi in C

Ein beliebtes Beispiel für rekursives Programmieren ist das 1883 vom Mathematiker Eduard Lucas erfundene (Mathematik-)Denkspiel “Die Türme von Hanoi“.

Das Spiel besteht darin, einen Stapel A von verschieden großen Scheiben, welche der Größe nach sortiert sind, auf einen Stapel C mithilfe eines “Zwischenlager”-Stapel B zu bewegen ohne dabei eine größere Scheibe auf eine kleinere Scheibe zu legen. Am Ende muss auf dem Stapel C die selbe geordnete Reihenfolge vorliegen, wie auf dem Ursprungs-Stapel A. Zusätzlich gilt, dass jeweils nur eine Scheibe bewegt werden darf.

Der Stapel A mit 4 Scheiben wird so gelöst:

Türme von Hanoi

Dazu gibt es nun einen rekursiven Lösungsweg in der Programmierung. Man löst jeweils das kleinste Problem und wendet das selbe auf das nächt größere Problem an. Das heißt, man löst das Problem eines Stapels mit zwei Scheiben, kann dieses Problem gelöst werden, löst man das Problem für 2+1 bzw. schlussendlich n+1 Scheiben.

Der entsprechende Algorithmus in C:

void hanoi(int h, char src, char dest, char tmp) {
    if (h == 1) {
        moveDisk(src, dest);
    } else {
        hanoi(h-1, src, tmp, dest);
        moveDisk(src, dest);
        hanoi(h-1, tmp, dest, src);
    }
}
 
void moveDisk(char src, char dest) {
    printf("Move %c to %c\n", src, dest);
}

(Als simples Beispiel wird moveDisk() lediglich die entsprechenden Züge ausgeben.)

isPrime.c

Ja, man würde vielleicht vermuten, dass es überhaupt keine Schwierigkeit ist, herauszufinden ob eine Zahl eine Primzahl ist oder nicht. Es soll jedoch Leute geben, die sich damit schwer tun (und zufälligerweise des öfteren neben mir in den Vorlesungen sitzen).

Deswegen von mir (auch wenn man dieses Problem wohl niemals rekursiv lösen würde) der entsprechende Source-Code dazu:

int isPrime(int num, int i) {
    if (num == 0) return 0;
    if (i*i > num) return 1;
    if ((num%i) == 0) return 0;
    return isPrime(num, (i+1));
}