BTSExo1

16.04.2020 10:27 •  Информатика

Несправедливые башни
В Ханое (смотрите ниже) несправедливо запретили класть самый маленький диск (номер 1) на средний колышек (номер 2).

Решите головоломку с учётом этих ограничений. Вам не нужно находить минимальное решение, но количество совершённых перемещений не должно быть больше 200000 при условии, что количество дисков не превосходит 10.

Входные данные

Задано натуральное число n≤10 — размер пирамидки.

Выходные данные

Программа должна вывести перекладывания пирамидки из данного числа дисков со стержня 1 на стержень 3.

Примеры
Ввод
3
Вывод
1 1 3
2 1 2
1 3 1
2 2 3
1 1 3
3 1 2
1 3 1
2 3 2
1 1 3
2 2 1
1 3 1
3 2 3
1 1 3
2 1 2
1 3 1
2 2 3
1 1 3
Ханой (эту задачу решать не надо! она нужна для понимания предыдущей)
Ханойские башни
Головоломка “Ханойские башни” состоит из трёх стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра дисков, если рассматривать их сверху вниз. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3, используя стержень 2 как вс за минимальное число перекладываний.

Напишите функцию, которая решает головоломку: для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня, с которого снимается данный диск, c — номер стержня, на который надевается данный диск.

Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

Входные данные

Задано натуральное число n≤10 — размер пирамидки.

Выходные данные

Программа должна вывести минимальный (по количеству произведённых операций перекладывания пирамидки из данного числа дисков.

Примеры
Ввод
3
Вывод
1 1 3
2 1 2
1 3 2
3 1 3
1 2 1
2 2 3
1 1 3