Tüftel & Rätselecke

Auflösung: Eine Variante der Türme von Hanoi

Eine triviale Lösung sind natürlich n Stapel. Trivial heißt in diesem Fall, auf jeden noch freien Stapel eine Scheibe und dann alle Scheiben der Größe nach auf den Zielstapel zu verschieben. Aber es geht natürlich besser:

Sobald die Anzahl der Stapel reduziert wird, lassen sich nicht mehr so viele Scheiben auf einmal trivial verschieben. Bis O(sqrt(n)) [c=2] viele Stapel bleibt bei dieser Vorgehensweise die Laufzeit noch linear:

Man verschiebt einfach Wurzel n mal jeweils einen Stapel der Größe Wurzel n, was jeweils in Wurzel n Zeit möglich ist. Die Hilfsstapel lassen sich genau so trivial wieder abbauen, um zum Zielstapel zu kommen. Falls c=2 gesetzt wird, ist obige Prozedur trivial durchführbar. Bei kleinerem c muß dann die ersten Male der Stapel größer gemacht werden, was dann natürlich mehr Laufzeit verursacht, aber es bleibt die obere Zeitgrenze erhalten.

Damit ergibt sich eine Laufzeit von O(sqrt(n))*O(sqrt(n))=O(n). O(sqrt(n)) Stapel ist gut, aber es geht besser: Der oben beschriebene Algorithmus benötigt, um x Scheiben in O(x) Zeit zu verschieben, O(sqrt(x)) Stapel. Benutzt man dieses Verfahren für n^(2/3) Scheiben, läßt sich durch eine kleine Variation mit O(n^(1/3)) Stapel das Gewünschte realisieren:

Mit Stapel läßt sich also ein Stapel der Größe in Zeit verschieben. Davon werden einfach viele gebildet, und schon hat man den ganzen Stapel weggeschoben [n^(1/3)*n^(2/3)=n]. Die kleineren Stapel lassen sich dann natürlich leicht wieder aufspalten und dann zum Zielstapel verschieben. Mit dem soeben vorgestellten Verfahren läßt sich die Anzahl der Hilfsstapel nun für beliebiges k aus N auf n^(1/k) reduzieren.

Die Induktionsverankerung ist oben gezeigt. Der Induktionsschritt k -> k+1 funktioniert anlog:

n^(1/(k+1)) erhält man, indem man nach Induktionvoraussetzung mit n^(1/(k+1)) Stapel n^(1/(k+1)) Scheiben je auf n^(1/(k+1) weitere Hilfsstapel in O(n^(1/(k+1)))*O(n^(1/(k+1)))=O(n) Zeit verschiebt.