Problem bei binär rekursivem Prozeduraufbau

[Thorben86]

Ich bin gerade dabei den Aufbau der Strucktur der Hanoi-prozedur zu verstehen.(ein ähnliches Program hat Matze geschrieben)

Der aufbau sieht volgendermaßen aus:

Delphi-Quellcode:

if (n > 0) and (not Abbruch) then
  begin
    showmessage('1');
         Berechnen_graf(n-1, Startstapel, Hilfsstapel,  Zielstapel);
    showmessage('2');
    inc(Anzahl);
.
.
.
   {Animation aufrufen}
   Animation(Startstapel, Zielstapel);
.
.
.
   showmessage('3');
        Berechnen_graf(n-1, Hilfsstapel , Zielstapel,Startstapel );
   showmessage('4');
  end;

Ich hab die Showmessages reingesetzt, um rauszukriegen, in welcher reihenfolge die aufgerufen werden, das ergebnis ist jedoch auch etwas kopfzerreibend. (Wenn bedarf besteht, kann ich die liste und die ausgabe, von wo nach wo verschoben mit anhängen)

Kann mir wer irgendwie den Aufbau erklären, warum man das mit einer binären Rekursion löst (halt die zwei Aufrufe).
Also die Grundzüge hab ich so verstanden, aber irgendwie ist da auch schluss.

[Niko]

Hi,

eigentlich will man die unterste Scheibe vom Startstapel auf den Zielstapel verlegen. Da dass aber nicht geht so lange noch andere Scheiben auf dieser Scheibe liegen müssen die erstmal weg.

Also ruft man die Methode Berechnen_graf für die zweite Scheibe von unten auf (n - 1) und gibt für diese Scheibe als Ziel den Hilfsstapel an (damit der Zielstapel danach für die unterste Scheibe frei ist). Liegen auf der zweiten Scheibe von unten weitere Scheiben, so wird dieser Aufruf so lange wiederholt, bis als Scheibenzahl 0 übergeben wird. 0 Scheiben verlegen heißt, die Methode muss nichts machen und kehrt sofort zurück.

Jetzt kann die oberste Scheibe vom Startstapel entweder auf den Ziel- oder Hilfsstapel verlegt werden (der Aufruf von Animation(Startstapel, Zielstapel)).

Anschließend muss dafür gesorgt werden, dass der andere Stapel (auf dem jetzt noch die Scheiben liegen, die oberhalb der aktuellen gelegen waren) für den nächsten Schritt wieder frei gemacht wird, in dem diese Scheiben auf die gerade umgelegte Scheibe verlegt werden (der zweite rekursive Aufruf von Berechnen_graf). Im Falle der obersten Scheibe muss hier nichts mehr verlegt werden, der neue Aufruf von Berechnen_graf kehrt sofort zurück. Jetzt ist die oberste Scheibe vom Stapel entfernt, wieder ein leerer Stapel als Hilfsstapel vorhanden und es kann die nächste Scheibe vom Startstapel verlegt werden usw.

Am Besten einfach mal überlegen, wie du das Problem von Hand lösen würdest - der Algorithmus macht nichts anderes.