ein Kapitel zurück                                           ein Kapitel weiter

Das Programm die Türme von Hanoi eignet sich sehr gut um das Kapitel der Rekursion besser zu verstehen. Um das Spiel zu verstehen kommt hierzu eine kleine Beschreibung....


Die Türme von Hanoi


Wir haben 3 Plattformen : A, B und C.Auf der Plattform A liegen n Platten. Nun sollen alle Platten nach C transportiert werden ohne das eine größere Platte auf eine kleinere Platte gelegt wird und es darf immer nur eine Scheibe pro Zug benutzt werden. Platte B darf als Zwischenablage verwendet werden. Wir verwenden in der Voreinstellung 3 Platten da dies die Erklärungszeit verkürzt.

Wir wollen uns die Funktion hanoi mal anschauen....

/*Download:hanoi1.c*/

#include <stdio.h>
#define SCHEIBEN 3

void hanoi(int hoehe, int stab1, int stab2, int stab3)
{
 if(hoehe==1)
  {
   printf("Hebe eine Scheibe von Stange %d nach Stange %d\n",stab1,stab3);
   return;
  }
 hanoi(hoehe-1,stab1,stab3,stab2);
 hanoi(1,stab1,stab2,stab3);
 hanoi(hoehe-1,stab2,stab1,stab3);
}

int main()
{
 hanoi(SCHEIBEN,1,2,3);
 return 0;
}

Als "Abbruchbedienung" haben wir wenn wir auf der Höhe der Unersten Platte sind also hoehe==1 ...


Die Türme von Hanoi


Folgende 3 rekursive Möglichkeiten haben wir hier.... 

hanoi(hoehe-1,stab1,stab3,stab2);
hanoi(1,stab1,stab2,stab3);
hanoi(hoehe-1,stab2,stab1,stab3);

Die erste Möglichkeit ist... 

hanoi(hoehe-1,stab1,stab3,stab2);

...wir legen 1 Scheibe (hoehe-1) vom Stab 1 über Stab 3 nach Stab 2. Die zweite Möglichkeit wäre dann... 

hanoi(1,stab1,stab2,stab3);

...wir legen 1 Scheibe vom Stab 1 nach Stab 3. Und die dritte Möglichkeit ist dann.... 

hanoi(hoehe-1,stab2,stab1,stab3);

...das wir 1 Scheibe(hoehe-1) vom Stab 2 über Stab 1 zum Stab 3 legen. Also nochmals kurz... 

Stab 1 zum Stab 2
Stab 1 zum Stab 3
Stab 2 zum Stab 3

Diese 3 Möglichkeiten reichen um alle Möglichkeiten durchzutesten. Zugegeben das ganze ist etwas kompliziert aber Versuchen sie mal zu diesem Programm die Iterative Lösung zu finden. Ich habe mir schon mehrere Stunden damit herumgeschlagen und habe vor lauter if-if else-else Anweisungen mit der Zeit total den Überblick verloren. Vielleicht hat ja mal einer von euch die Lust das ganze Iterativ zu Programmieren und schickt mir das Ding. Ein Tipp : Versuchen sie es wenigstens mal ;) Doch es ist möglich. In einem Buch habe ich folgenden Pseudocode entdeckt.... 

while(1)
{
 zuerst bewege die kleinste Scheibe
 von der aktuellen Position in
 Uhrzeigerrichtung;
 if(alle Scheiben auf dem Zielstab)
    break;

 jetzt bewege die einzige mögliche
 Scheibe die nicht die kleinste
 Scheibe ist;
}

Zugegeben das hört sich jetzt einfacher an als es ist. Aber das war bisher das einzige was ich gefunden habe die Türme von Hanoi Iterativ zu Programmieren.

Ich habe noch einen 2. Quellcode der Türme von Hanoi der etwas länger ist. Lassen sie sich aber davon nicht abschrecken. Das meiste dient der optischen Darstellung von den Türmen. Hierzu erst mal nur die Rekursive Funktion... 

void hanoi(int von, int nach, int h)
{
 int temp;

 if(h==1) //Falls nur eine Scheibe auf dem Stapel ist
   bewege(von,nach);

 else
  {
   temp=3-von-nach; //Hier wird die Nummer des freien Stabes ermittelt
   hanoi(von,temp,h-1);
   bewege(von,nach);
   hanoi(temp,von,h-1);
   hanoi(von,nach,h-1);
  }
}

Auch hierzu die Erklärung. Als erstes wird überprüft ob nur 1 Scheibe insgesamt auf dem Turm sind. So brauchen wir nur diese eine Scheibe von (quelle) nach (ziel) schieben. Nur wegen einer Scheibe benötigen wir kein solch Programm. Hier sind folgende 4 Schritte notwendig um die Arbeit zu bewältigen....

  1. Der Turm aus den oberen h-1 Scheiben wird von Stab von auf einen freien Stab transportiert. Den freien Stab ermitteln wir mittels : temp=3-von-nach; Die erledigen wir mit dem 1. Aufruf : hanoi(von,temp,h-1); ->Also 1 Scheibe(h-1) von nach temp (freier Stab).
  2. Die unterste Scheibe transportieren wir von von nach nach wenn h==1 ist.
  3. Mit dem 2. Rekursiven Funktionsaufruf (hanoi(temp,von,h-1);) von hanoi versetzten wir den in Schritt 1 versetzten Turm wieder auf dem Stab von zurück.
  4. Der jetzt um 1 Scheibe verkleinerte Turm auf der Stange von wir jetzt durch einen weiteren rekursiven Aufruf auf die Stange nach transportiert (hanoi(von,nach,h-1);).


Damit sie sich das ganze jetzt mal bildlich vorstellen können folgt nun das versprochene Programm womit sie die Schritte alle nachvollziehen können....

/*Download:hanoi2.c*/

/*Aus dem Buch Goto C von Guido Krüger welches ich hiermit gleich
  weiterempfehlen will*/

#include <stdio.h>
#define SCHEIBEN 3

int board[3][SCHEIBEN +1]; /*Zwei Dimensonales Array*/
int count=1;

void show()
{
 int i,j,k,width,space;

 for(i=SCHEIBEN; i>=0; i--) {
   for(j=0; j<3; j++)
    {
     width = 2 * board[j][i];     /*Breite der Scheibe*/
     space = (24 - width) / 2;    /*Leerzeichen vom Rand weg*/
     for(k=1; k<=space; k++)
        putchar(' ');

     for(k=1; k<=width/2; k++) /*Linke Seite der Scheibe*/
        putchar('H');

      putchar('I');           /*Mittelpunkt*/
      for(k=1; k<=width/2; k++) /*Rechte Seite der Scheibe*/
          putchar('H');

      for(k=1; k<=space;k++)
          putchar(' ');
      printf(" ");
      }
   printf("\n");
  }
 printf("------------------------------------------------------------------\n");
 printf("%d. Zug : ....\n",count++);
 while((i=getchar())!= '\n');
}

void bewege(int von, int nach)
{
 int i,j;
 printf("Bewege eine Platte von %d nach %d\n\n",von,nach);
 for(i=SCHEIBEN -1; !(board[von][i]); i--);
 for(j=SCHEIBEN -1; !(board[nach][j]) && j>=0; j--);
 board[nach][j+1] = board[von][i];
 board[von][i] = 0;
 show();
}

void hanoi(int von, int nach, int h)
{
 int temp;

 if(h==1) /*Falls nur eine Scheibe auf dem Stapel ist*/
    bewege(von,nach);

 else
  {
   temp=3-von-nach; /*Hier wird die Nummer des freien Stabes ermittelt*/
   hanoi(von,temp,h-1);
   bewege(von,nach);
   hanoi(temp,von,h-1);
   hanoi(von,nach,h-1);
  }
}

int main()
{
 int i,j;

 for(i=0; i<3; i++)
   for(j=0; j<=SCHEIBEN; j++)
     board[i][j] =0; /*Array initialisieren*/

 for(i=0; i<SCHEIBEN; i++) /*Alle Scheiben werden auf die erste Stange gelegt*/
   board[0][i] =SCHEIBEN -i; /*Zuerst die Größte mit 4 dann Scheibe m. 3,2,1*/

 printf("\n\n\n\t\tDie Türme von Hanoi\n");
 /*Zeigt uns die Grundstellung des Spieles*/
 printf("\t\t-------------------\n\n\n");show();

 hanoi(0,2,SCHEIBEN); /*Jetzt gehts los*/
 return 0;
}

Ein Tipp noch zu diesem Programm -> Vertrödeln sie nicht soviel Zeit an dem Code zur Bildlichen Darstellung, es ist einzig und alleine wichtig damit sie verstehen wie diese Rekursion funktioniert.

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf