3. Türme von Hanoi

Türme von Hanoi

  • M

    Das Problem der Türme von Hanoi lässt sich wie folgt beschreiben: Gegeben sind 3
    senkrechte Stangen 1, 2 und 3. Auf Stange 1 liegen n durchlöcherte Scheiben, die nach
    oben zu immer kleiner werden. Dieser Scheibenstapel ist nach folgenden Regeln auf
    Stange 3 zu verlagern: es darf immer nur eine Scheibe bewegt werden und es darf nie
    eine größere auf einer kleineren Scheibe zu liegen kommen.
    Der folgende Algorithmus löst das Problem der Türme von Hanoi rekursiv. Es wird
    dabei ein Protokoll ausgegeben, von welcher Stange auf welche die Scheiben bei den
    einzelnen Zügen bewegt werden müssen. Erklären Sie die Funktionsweise dieses
    Algorithmus.

    #include<stdio.h>

void tower(int quelle, int hilf, int ziel, int n);

int main(void) {
  tower(1,2,3,3);
  return 0;
}

void tower(int quelle, int hilf, int ziel, int n) {
  if(n == 0) {
    printf("Bewege von %d nach %d\n", quelle, ziel);
  }
  else {
    tower(quelle, ziel , hilf , n-1);
    tower(quelle, 0 , ziel , 0);
    tower(hilf , quelle, ziel , n-1);
  }
}

    checkt das irgendwer wirklich?

    mfg

    0
  • G

    Jo! Die Idee dahinter ist, dass sich der Algorithmus jeweils nur um die letzte, größte Scheibe kümmert. Davor verlegt er durch einen rekursiven Aufruf einen Turm der Größe n-1 auf die Hilfsstange, danach verlegt er durch einen rekursiven Aufruf diesen Turm der Größe n-1 von der Hilfsstange auf die Zielstange. In einem Aufruf selbst wird nur die jeweils größte Scheibe des Turms auf die Zielstange verlegt.

    [ Dieser Beitrag wurde am 16.12.2002 um 22:18 Uhr von Gregor editiert. ]

    0
  • M

    ok...das prinzip ist ja nicht so schwer, aber wie kann man erkennen, das der code genau das macht?

    welcher rekursionsaufruf ist für was zuständig (was soll mit jedem einzelnen erreicht werden?)...

    mfg

    0
  • ?

    Ich habe keine Ahnung^^ :xmas1:

    0
  • C

    Kurz gesagt: Jeder der drei Aufrufe kümmert sich um einen Teilsatz von Gregor's Aussage:

    Gregor schrieb:

    Davor verlegt er durch einen rekursiven Aufruf einen Turm der Größe n-1 auf die Hilfsstange,

    -> tower(quelle, ziel , hilf , n-1);

    Gregor schrieb:

    Jo! Die Idee dahinter ist, dass sich der Algorithmus jeweils nur um die letzte, größte Scheibe kümmert.

    -> tower(quelle, 0 , ziel , 0); (theoretisch könnte man diesen Aufruf auch direkt durch die printf()-Anweisung ersetzen)

    Gregor schrieb:

    danach verlegt er durch einen rekursiven Aufruf diesen Turm der Größe n-1 von der Hilfsstange auf die Zielstange.

    -> tower(hilf , quelle, ziel , n-1);

    Edit: Ich sehe gerade das Datum des Beitrags 😮
    @Rick: Was für einen Sinn siehst du darin, einen Uralt-Thread mit so einem sinnlosen Kommentar zu reanimieren?

    0

  • Vielleicht möchte hier jmd. demonstrieren wie doof er ist?

    0
Anmelden zum Antworten