Задача №1432. Ремонт в Ханое
Постановлением ЮНЕСКО оригинал Ханойской башни был подвергнут реставрации. В связи с этим во время пользования головоломкой нельзя было перекладывать кольца с первого стержня сразу на третий и наоборот. Напишите рекурсивную процедуру, которая выводит последовательность перекладываний с учетом таких ограничений.
Входные данные
Вводится одно натуральное число N – количество колец на первом стержне (1 ≤ N ≤ 7).
Выходные данные
Требуется вывести последовательность ходов для перекладывания всех колец на третий стержень в таком порядке: номер кольца, с какого стержня, на какой стержень. Кольца нумеруются от самого маленького до самого большого. Количество ходов не должно превышать 105.
Примеры
Входные данные
1
Выходные данные
Сдать: для сдачи задач необходимо войти в систему