Задача №314. Ханойские башни
Головоломка "Ханойские башни" состоит из трех колышков, пронумерованных числами 1, 2, 3. На колышек 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного колышка на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку с колышка 1 на колышек 2 за минимальное число перекладываний.
Напишите программу, которая решает головоломку для данного числа дисков n.
Входные данные
Вводится 1 число n.
Выходные данные
Необходимо вывести последовательность перекладываний в формате "Disk 1 move from 1 to 2" (диск 1 переложить c колышка 1 на колышек 2), печатая по одной инструкции в строке. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.
Примеры
Входные данные
2
Выходные данные
Disk 1 move from 1 to 3 Disk 2 move from 1 to 2 Disk 1 move from 3 to 2
Сдать: для сдачи задач необходимо войти в систему