Ниже представлен текст одной из классических головоломок и, по совместительству, алгоритмических задач по программированию. С ней знакомы многие, в том числе и те, кто с программированием никак не связан.
Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из N дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.
Напишите программу, которая решает головоломку; для данного числа дисков N печатает последовательность перекладываний в формате A B C, где A — номер перекладываемого диска, B — номер стержня с которого снимается данный диск, C — номер стержня на который надевается данный диск.
Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.
Программа должна вывести минимальный (по количеству произведенных операций) способ перекладывания пирамидки из данного числа дисков.
Решение оформите в виде функции move (n, x, y), которая печатает последовательность перекладываний дисков для перемещения пирамидки высоты N со стержня номер X на стержень номер Y.
Пример:
Введите количество дисков: 2
Переложить диск 1 со стержня номер 1 на стержень номер 2
Переложить диск 2 со стержня номер 1 на стержень номер 3
Переложить диск 1 со стержня номер 2 на стержень номер 3
ЧИТАТЬ ДАЛЕЕ …