Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.
Напишите программу, которая решает головоломку; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск.
Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.
Программа должна вывести минимальный (по количеству произведенных операций перекладывания пирамидки из данного числа дисков.
На питоне
РОПОР и ТОПОР
Объяснение:
Представим что имеем дело с 4-ичной системой счисления { 0 - О, 1 - П, 2 - Р, 3 - Т }. В таком случае вышенаписанный ряд можно представить в такой виде:
1. (00000) = 0 в 10ичной СС
2. П (00001) = 1 в 10ичной СС
3. Р (00002) = 2 в 10ичной СС
4. Т (00003) = 3 в 10ичной СС
5. ОООПО (00010) = 4 в 10ичной СС
...
Исходя из этого, чтобы получить слово, находящееся на 531 месте и 787 месте, достаточно перевести числа 530 и 786 в 4-ичную систему счисления и заменить цифры буквами.
1.
530 / 4 = 132 (2 остаток)
132 / 4 = 33 (0 остаток)
33 / 4 = 8 (1 остаток)
8 / 4 = 2 (0 остаток)
530(10) = 20102 (4)
Замена: РОПОР
2.
786 / 4 = 196 (2 остаток)
196 / 4 = 49 (0 остаток)
49 / 4 = 12 (1 остаток)
12 / 4 = 3 (0 остаток)
786(10) = 30102(4)
Замена: ТОПОР
Python 3.8.1
n = 10
a = []
while n != 0:
b = int(input('Enter number 1 - 30: '))
n -= 1
if b <= 10:
a.append(b)
if len(a) == 10:
c = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8] + a[9]
elif len(a) == 9:
c = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]
elif len(a) == 8:
c = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]
elif len(a) == 7:
c = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6]
elif len(a) == 6:
c = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
elif len(a) == 5:
c = a[0] + a[1] + a[2] + a[3] + a[4]
elif len(a) == 4:
c = a[0] + a[1] + a[2] + a[3]
elif len(a) == 3:
c = a[0] + a[1] + a[2]
elif len(a) == 2:
c = a[0] + a[1]
elif len(a) == 1:
c = a[0]
else:
c = 0
print(c);
q = int(input('Enter any number to quit'))