Dort stehen drei Pfosten, auf denen 64 zylindrische Scheiben von jeweils verschiedenem Durchmesser liegen. Anfangs lagen alle Scheiben auf dem ersten Pfosten, und sie sollen auf den dritten Pfosten einzeln umgelegt werden; dabei kann der zweite Pfosten als Zwischenablage verwendet werden, aber es darf nur immer eine kleinere auf einer größeren Scheibe zu liegen kommen.

Wenn diese Arbeit einst vollendet sein wird, ist der Zweck des Weltalls erreicht; die Menschheit wird vom Zwang der ewigen Wiedergeburt erlöst und darf ins Nirvana eingehen.

Das Problem sieht sehr kompliziert aus, vor allem was die dabei nötige Buchhaltung betrifft, und wir wollen die Mönche bei ihrem sehr lobenswerten Werk durch eine Computersimulation unterstützen. Nach längerer Überlegung zeigt sich, daß es nützlich ist, einige Hilfsbegriffe einzuführen:

• ein Turm  ist ein Stapel von Scheiben;  dabei liegt immer eine kleinere Scheibe auf einer größeren;
• die Höhe  eines Turmes ist die Anzahl der Scheiben; sie kann 0 sein, weil wir auch leere  Türme betrachten wollen;
• der Durchmesser  eines Turmes sei gleich dem Durchmesser seiner untersten Scheibe, oder 0 für einen leeren Turm;
• ein Turm ist entweder leer, oder er besteht aus einer Scheibe und einem darauf stehenden Turm kleineren Durchmessers und um 1 kleinerer Höhe.

• für einen leeren Turm ist nichts zu tun;
• um einen nichtleeren Turm von einem Pfosten A auf einen Pfosten E zu verlagern, bringen wir den auf der untersten Scheibe stehenden kleineren Turm (auf die gleiche Weise) auf den dritten Pfosten Z, legen die verbliebene Scheibe von A nach Z um, und holen dann den kleineren Turm (auf die gleiche Weise) vom Hilfspfosten Z nach E.

	TYPE Pfosten = (Anfang, Zwischen, Ende);

	PROCEDURE bewegeTurm(A, Z, E: Pfosten; h: Cardinal);
	BEGIN IF h > 0 (* sonst ist nichts zu tun *)
	      THEN bewegeTurm(A, E, Z, h-1);
	           umlegeScheibe(A, E);
	           bewegeTurm(Z, A, E, h-1)
	      END
	END bewegeTurm;
	

Daß das Verfahren terminiert, ist leicht zu sehen: wir können als Größenmaß für das Problem wahlweise die Höhe h oder den Durchmesser des Turmes ansehen, und in beiden Fällen sind die Teilprobleme kleiner. Nicht so leicht zu sehen ist, daß das Verfahren korrekt  ist insoweit, daß dabei immer kleinere Scheiben auf größeren zu liegen kommen. Dies zu beweisen ist Übungsaufgabe; uns kommt es hier auf etwas anderes an, nämlich auf den Aufwand.

Sei A(n) der Aufwand, einen Turm der Höhe n zu bewegen, und c1, c2, c3 irgendwelche Konstanten. Dann kann man aus dem Programm sofort ablesen:

A(n) = 2 * A(n-1) + c1für n > 0, A(0) = c2

A(n) + c1 = 2 * (A(n-1) + c1)
oder mit B(n) = A(n) + c1, A(n) = B(n) - c1:
B(n) = 2 * B(n-1) = c3 * 2**n mit irgend einem Faktor c3

A(n) = (c1+c2) * 2**n - c1

2**10 = 1024 10**3, 2**20 10**6, 2**60 10**18,