Türme von Hanoi



  • Hallo zusammen,
    Ich bräuchte einmal Hilfe bei der Umsetzung eines Programmes.
    Ich soll einen rekursiven Algortihmus schreiben um das Probem der "Türme von Hanoi" zu lösen.
    Dazu gibt es auch ein Programmgerüst.
    Die genaue Aufgabe lautet:
    a)Ergänzen Sie den Inhalt der Funktion move(int from, int to), so dass die obere Scheibe des Stabs from auf den Stab to verschoben wird.
    b) Ergänzen Sie den Inhalt der Funktion hanoi(int discs, int from, int to, int aux), so dass discs viele Scheiben von from nach to verschoben werden. Nutzen Sie die Tatsache, dass es mit Hilfe eines rekursiven Aufrufs möglich ist, discs-1 viele Scheiben (z.B. auf den Hilfsstab aux) zu verschieben.

    Das vorgegebene Programmgerüst so:

    #include <iostream>
    
    using namespace std;
    
    const int g_numDiscs = 3;
    
    
    int g_pile_1[g_numDiscs];
    int g_pile_2[g_numDiscs];
    int g_pile_3[g_numDiscs];
    
    int* g_pile_array[3] = { g_pile_1, g_pile_2, g_pile_3 };
    
    int main(int argc, char* argv[]);
    
    void hanoi(int discs, int from, int to, int aux);
    
    void move(int from, int to);
    
    void draw();
    
    int main(int argc, char* argv[])
    {
    	for (int i = 0; i < g_numDiscs; i++)
    	{
    		g_pile_array[0][i] = g_numDiscs - i;
    		g_pile_array[1][i] = 0;
    		g_pile_array[2][i] = 0;
    	}
    
    	draw();
    
    	
    	hanoi(g_numDiscs, 0, 1, 2);
    	getchar();
    	return 0;
    }
    
    void hanoi(int discs, int from, int to, int aux)
    {
    	
    }
    
    void move(int from, int to)
    {
    
    }
    
    
    void draw()
    {
    	for (int i = 0; i < g_numDiscs; i++)
    	{
    		for (int j = 0; j < 3; j++)
    		{
    			int discs = g_pile_array[j][g_numDiscs - 1 - i];
    			for (int k = g_numDiscs - 1; k >= 0; k--)
    				if (k >= discs) cout << " ";
    				else cout << "<";
    			cout << "|";
    			for (int k = 0; k < g_numDiscs; k++)
    				if (k >= discs) cout << " ";
    				else cout << ">";
    			cout << "  ";
    		}
    		cout << "\n";
    	}
    	for (int i = 0; i < g_numDiscs * 3 * 2 + (3 - 1) * 2 + 3; i++)
    		cout << "-";
    	cout << "\n\n";
    }
    
    

    Nun wird in der Aufgabe ja eigentlich genau gesagt, was zu tun ist. Aber irgendwie versteh ich es nicht. Soll ich einen Stack einbauen oder alles über einen Zwischenspeier speichern ?
    Hätte jemand vielleicht einen Ansatz oder kann mir erklären, was ich tun muss ?
    Vielen Lieben Dank.



  • Was ist ein rekursiver Algorithmus oder eine rekursive Funktion?



  • So wie ich es verstanden habe, ist ein rekursiver Algorithmus bzw. eine rekursive Funktion, ein in sich selbst wieder aufrufende Funktion.
    Also eine Funktion oder Methode ruft sich in sich selbst wieder auf und wiederholt sich so. Wie z.B. eine matroschka-Puppe, als Beispeil außerhalb der Informatik 🙂



  • @student35 wenn du also das Problem mit einem rekursiven Algorithmus lösen sollst, sollst du dann einen Stack oder „Zwischenspeicher“ (was auch genau du darunter verstehst) einbauen?



  • @manni66 das genau weiß ich eben nicht 😅
    Das wäre eine Vermutung von mir, vielleicht einen Stack zu verwenden. Allerdings, wenn man sich die Aufgaben durchließt, hört es sich nicht so an, als ob ich dafür einen benötige.
    Ich weiß allerdings nicht, wie ich anfangen soll



  • @student35 sagte in Türme von Hanoi:

    Das wäre eine Vermutung von mir, vielleicht einen Stack zu verwenden.

    Warum?



  • Nun ja, eine der Reglen von diesem Rätsel (Türme von Hanoi) ist ja, dass immer nur die oberste Scheibe weggenommen werden darf. Das würde ja zu einem Stack passen, dort kann man ja auch immer nur das oberste Element entfernen. Durch "push" und "pop" könnte man dann eventuell eine schnelle Lösung finden. Allerdings sind das alles nur Vermutungen, da ich erst am Anfang meines Studiums stehe.



  • @student35 sagte in Türme von Hanoi:

    dass immer nur die oberste Scheibe weggenommen werden darf

    Nein, die oberste Scheibe darf auf einem der beiden anderen Türme/Turmbauplätze abgelegt werden. Du kannst sie nicht irgendwo verschwinden lassen.


Anmelden zum Antworten