Türme von Hanoi...



  • Hi @all.
    Ich habe eine Aufgabe erhalten, das Programm Türme von Hanoi zu schreiben. Dazu gab es eine Vorgabe, in die praktisch nur noch die Rekursion eingebaut werden soll. Nun die Vorgabe:

    #include <iostream.h>
    #include <stdlib.h>
    
    	int n ; const int h = 11 ;  	// benutzt wird A [3][1] ...A [3][10]
    	int A [4] [h] ;		   	// dies sind die drei Türme, 
                                                  // maximale Höhe 10
    	void vorzeigen ( )
      	{ cout << "\n" ;
    	  for ( int k = n ; k > 0 ; k -- )
    	 	 { cout << "  " ;
    		   for ( int i = 1; i < 4 ; i++ )
    		        if ( A[i][k] > 0 ) 
     				 cout << " " << A [i][k] << " " ; 
    		        else cout << "   " ;
    		    cout << endl ;
    		  }
    	  cout << "   A  B  C \n\n" ;
       system("PAUSE");
    }
    
    void transport (int k, int a, int b, int c) 	
    // Scheibe k von a nach b über c
      	{ if ( k > 1 ) transport (k - 1, a, c, b) ;
    
       //  Entwicklung der Rekursion
    
    	  vorzeigen ( ) ;
    	  if (k > 1) transport (k - 1, c, b, a) ; 
    }
    
    	void main ( )
    { cout << "Wieviele Scheiben sollen versetzt werden ? " ; 
           cin >> n ;
    	  for ( int k = 1 ; k <= n ; k++ )
    		 { A [1] [k] = n + 1 - k ; 
                  A [2] [k] = 0 ; A [3] [k] = 0 ; }
    	  vorzeigen ( ) ; 
           transport (n, 1, 2, 3) ;
    
          system("PAUSE");
      //  NB: Insgesamt 2n - 1 Schritte
    }
    

    An der Stelle "//Entwicklung der..." soll die Rekursion rein. Nun die Rekursion (glaube ich) einigermaßen hingekriegt zu haben. Aber an dem Tauschen der Scheiben gibt es noch Probleme...

    Der Source-Code:

    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    void schieben (int a, int b);
    	int n; const int h = 11 ;  	// benutzt wird A [3][1] ...A [3][10]
    	int A [4] [h] ;		   	// dies sind die drei Türme, 
                                        // maximale Höhe 10
    	void vorzeigen ( )
      	{ cout << "\n" ;
    	  for ( int k = n ; k > 0 ; k -- )
    	 	 { cout << "  " ;
    		   for ( int i = 1; i < 4 ; i++ )
    		        if ( A[i][k] > 0 ) 
     				 cout << " " << A [i][k] << " " ; 
    		        else cout << "   " ;
    		    cout << endl ;
    		  }
    	  cout << "   A  B  C \n\n" ;
    }
    
    void transport (int k, int a, int b, int c) 
    {
    if ( k > 1 )
        {
            transport (k - 1, a, c, b);
            transport (1, a, b, c);
            transport (k - 1, c, b, a);
        }     
        else
        {
            schieben(a,b);
        }
    
        vorzeigen ( ) ;
        if (k > 1) transport (k - 1, c, b, a) ;
    }
    
    	void main ( )
    { cout << "Wieviele Scheiben sollen versetzt werden ? " ; 
           cin >> n ;
    	  for ( int k = 1 ; k <= n ; k++ )
    		 { A [1] [k] = n + 1 - k ; 
                  A [2] [k] = 0 ; A [3] [k] = 0 ; }
    	  vorzeigen ( ) ; 
           transport (n, 1, 2, 3) ;
      //  NB: Insgesamt 2n - 1 Schritte
    }
    
    void schieben (int a, int b)
    {
    //Hier soll geschoben werden, aber ich weiss nicht,
    wie ich das mit den Arrays hinkriegen soll.
    Wir sollen zwingend diese Ausgabeform benutzen,
    aber ich weiss jedoch nicht, wohin ich dann verschieben soll,
    da ich auch keinerlei informationen über die Turmhöhen habe :(
    }
    

    wisst ihr wie man das machen könnte? oder ist da grundlegend was falsch?

    danke für eure hilfe!!



  • Du brauchst du Höhe für jede der 3 Türme.
    Entweder speicherst du die in einem zweiten Array oder du schreibst eine Funktion um die Höhe zu berechnen.

    int hoehe(int t) {
       for(int i=1; i < h; i++) {
          if(A[t][i]==0) return i-1;
       }
      return h-1;
    }
    

Log in to reply