Senior Sanchez
2006-06-22, 20:32:11
Hoi allerseits.
An den Türmen von Hanoi habe ich irgendwie was gefressen. Ich verstehe es eigentlich grob wie die rekursive Standardlösung funktioniert, aber so wirklich steige ich noch nicht dahinter obwohl mir sonst Rekursion überhaupt keine Probleme macht. Wahrscheinlich checke ich die Lösungsidee noch nicht richtig.
Aber das ist jedenfalls nicht der Punkt. Die Anzahl der Verschiebungen entspricht ja (2^n)-1, sprich bei 3 Scheiben muss 7 mal verschoben werden.
Nun habe ich im Sedgewick folgenden Satz gefunden, den ich überhaupt nicht raffe (es ging dabei noch um das zeichnen von Strichen auf nem lineal, was ich auch total verstehe und zum Hanoi-Problem ähnlich sein soll und auch um das Zeichnen von Fraktalen):
"Wie die Lösungen für das Zeichnen eines Lineals und die Türme von Hanoi sind diese Algorithmen bezüglich der Schrittanzahl linear, während die Anzahl mit der Tiefe der Rekursion exponentiell zunimmt."
An den Türmen von Hanoi habe ich irgendwie was gefressen. Ich verstehe es eigentlich grob wie die rekursive Standardlösung funktioniert, aber so wirklich steige ich noch nicht dahinter obwohl mir sonst Rekursion überhaupt keine Probleme macht. Wahrscheinlich checke ich die Lösungsidee noch nicht richtig.
Aber das ist jedenfalls nicht der Punkt. Die Anzahl der Verschiebungen entspricht ja (2^n)-1, sprich bei 3 Scheiben muss 7 mal verschoben werden.
Nun habe ich im Sedgewick folgenden Satz gefunden, den ich überhaupt nicht raffe (es ging dabei noch um das zeichnen von Strichen auf nem lineal, was ich auch total verstehe und zum Hanoi-Problem ähnlich sein soll und auch um das Zeichnen von Fraktalen):
"Wie die Lösungen für das Zeichnen eines Lineals und die Türme von Hanoi sind diese Algorithmen bezüglich der Schrittanzahl linear, während die Anzahl mit der Tiefe der Rekursion exponentiell zunimmt."