Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.
Напишите программу, которая решает головоломку; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск.
Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.
Входные данные
Вводится натуральное число n.
Выходные данные
Программа должна вывести минимальный (по количеству произведенных операций) способ перекладывания пирамидки из данного числа дисков.
смотри ты уже знаешь решение фактически, если ты знаешь что верхние n - 1 переносишь на 2ой стержень, а затем n на третий. Давай рассмотрим этот процесс подробнее, для того чтобы перенести n - 1 с первой на второй стержень, тебе нужно перенести сначала n - 2 диска на 3ий, положить n - 1-ый на второй стержень, и затем перенести n - 2 диска с 3го на 2ой. Это собственно и все решение, просто теперь попробуй симулировать ручкой в тетради такой процесс и поймешь мб как рекурсией делать
если нет:
Т.е в том что я делал у нас была изначальная функция rec(n,start,end), я делаю rec(n - 1,start, которая не start и не end), ложу n на end, делаю rec(n - 1,которая не start и не end, end)
