Легенда гласит, в Великом храме города Варанаси, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.
Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
Игра "Ханойские башни" состоит в следующем. Есть три стержня. На первый из них надета пирамидка из k колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить с использованием рекурсивного алгоритма программу, указывающую требуемые действия.
Решение
В случае, когда требуется переложить ОДИН диск со стержня номер m на стержень номер n, мы просто перекладываем его m ->n. Если требуется переложить со стержня m на стержень одного диска i, то для этого необходимо переместить i-1 диск на третий стержень с номером s (промежуточный), затем переложить оставшийся самый большой диск с m на n, после чего i-1 диск нужно с промежуточного s переложить на целевой стержень n. Таким образом, данный алгоритм сводит задачу к перемещению i-1 дисков вместо i.
