Ханойские башни
Помните детскую пирамидку с осью и деревянными дисками, нанизанными на неё?
Задача:
У вас есть такая пирамидка из трёх осей: A, B, C и 4 диска.
Вам нужно перенести все диски с оси А на ось Б, используя промежуточную ось С, руководствуясь двумя правилами:
- за один ход можно переносить только один диск
- нельзя на меньший диск класть больший
Сколько минимально ходов нужно сделать, чтобы решить её?
Кстати,
Существует такая персидская легенда:
Легенда гласит, что в Великом храме города Бенарас под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены три алмазных стержня высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брамой. Разгневанный, Брама воздвиг три высоких стержня и на один из них возложил 64 диска из чистого золота, причём так, что каждый меньший диск лежит на большем. Монахи обязаны постоянно перекладывать диски, перемещая их с одного стержня на другой по указанным выше правилам. Как только все 64 диска будут переложены со стержня, на который Бог Брама сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
