Ханойская башня

Дорогие ребята!

Сегодня хочу познакомить вас с одной из популярных головоломок XIX века - Ханойская башня.
Даны три стержня, на левый нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на правый стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Но, прежде чем вы приступите к решению этой задачи, прочтите легенду о Буддийских монахах:

В Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный, Брахма воздвиг три высоких стержня и на один из них возложил 64 диска сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.
Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

Подробности на сайте

Для верного решения этой задачи, вам необходимо знать, что минимальное количество перекладываний вычисляется по формуле 2^n-1.
Если мы применим эту формулу к задаче, которую решают монахи, то получим, что число перемещений дисков, равно 18446744073709551615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, и не ошиблись бы ни разу, их работа продолжалась бы 584000000000 лет.

Ну что, попробуем?
Удачи!