Башни Ханой
Даны 3 стержня (левый — 1, средний — 2 и правый — 3). На первом стержне размещены
n круглых дисков разных размеров, расположенных по возрастанию диаметра от верхнего к нижнему. Разрешается снимать верхний диск с одного стержня и перекладывать его на другой, при этом диск должен быть помещён только поверх другого, большего по размеру. Класть более крупный диск на меньший запрещено.Требуется вывести все операции, необходимые для переноса всех дисков с первого стержня на третий, при этом общее количество перемещений должно быть минимальным.
Входные данные
В единственной строке содержится целое число
n (1 ≤ n ≤ 16), указывающее количество дисков на первом стержне.Выходные данные
Программа должна напечатать все шаги, необходимые для перестановки дисков с первого стержня на третий, при соблюдении условия, что каждый диск может быть помещён только на больший. Число операций не должно превышать .
Примеры
Входные данные | Выходные данные |
2 | 1 -> 2
1 -> 3
2 -> 3 |
3 | 1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB