Классика: Ханойская башня!
Утверждается, что эту задачу сформулировали и решают до сих пор монахи каких-то из монастырей Тибета. Задача состоит в том, чтобы пирамидку из колец (на манер детской игрушки), нанизанную на один из 3-х стержней, перенести на другой такой же стержень, придерживаясь строгих правил:
• пирамидка состоит из N колец разного размера, уложенных по убыванию диаметра колец один на другой;
• перекладывать за одну операцию можно только одно кольцо с любого штыря на любой …
• но только при условии, что класть можно только меньшее кольцо сверху на большее, но никак не наоборот;
• нужно, в итоге, всю исходную пирамидку, лежащую на штыре №1, переместить на штырь №3, используя штырь №2 как промежуточный.
Например, для 2-х колец результат получается такой вот последовательностью перекладываний: 1 => 2 , 1 => 3 , 2 => 3
- hanoj.jpg (32.03 КБ) 1169 просмотров
По преданию, эту задачу по перекладыванию N=10 колечек, решают тибетские монахи, и когда они её, наконец, решат, тогда и наступит конец света … Армагедон, в нашей западной нотации.
A: Ханойская башня:
Код: Выделить всё
#!/usr/bin/env python3
import sys
line = 10 # длина строки вывода
pos = 0
def put(fr:int, to:int): # операция переноса fr=>to
global pos
if pos != line - 1:
print("{} => {}".format(fr, to), end=" | ")
else:
print("{} => {}".format(fr, to))
pos = (pos + 1) % line
return
def temp(fr:int, to:int) -> int: # выбор промежуточной позиции
for i in range(1, 3):
if i not in (fr, to):
break
return i
def move(fr:int, to:int, n:int) -> int:
if(1 == n):
put(fr, to)
m = 1
else:
m = move(fr, temp(fr, to), n - 1)
put(fr, to)
m += (move(temp(fr, to), to, n - 1) + 1)
return m
try:
if len(sys.argv) > 1: n = int(sys.argv[1])
else: n = int(input("число колец?: "))
except ValueError:
print("ошибочное значение!")
exit()
print("размер пирамиды: n=", n)
n = move(1, 3, n) # вот и всё решение!!!
if pos != 0: print()
print("общее число перемещений:", n)
Выполнение:
Код: Выделить всё
olej@R420:~/2021/own.BOOKs/tasks-Python/DRAFT$ ./hanoj.py 5
размер пирамиды: n= 5
1 => 2 | 1 => 2 | 2 => 2 | 1 => 2 | 2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 2 => 1
2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 1 => 3 | 2 => 1 | 2 => 2 | 1 => 2 | 2 => 1
2 => 2 | 2 => 1 | 2 => 1 | 2 => 3 | 1 => 2 | 1 => 2 | 2 => 2 | 1 => 3 | 2 => 1 | 2 => 3
1 => 3 |
общее число перемещений: 31
Код: Выделить всё
olej@R420:~/2021/own.BOOKs/tasks-Python/DRAFT$ ./hanoj.py 7
размер пирамиды: n= 7
1 => 2 | 1 => 2 | 2 => 2 | 1 => 2 | 2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 2 => 1
2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 1 => 2 | 2 => 1 | 2 => 2 | 1 => 2 | 2 => 1
2 => 2 | 2 => 1 | 2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 1 => 2 | 2 => 1 | 2 => 2
1 => 2 | 1 => 2 | 2 => 2 | 2 => 1 | 2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 2 => 1
2 => 1 | 2 => 2 | 1 => 2 | 2 => 1 | 2 => 2 | 2 => 1 | 2 => 1 | 2 => 2 | 1 => 2 | 1 => 2
2 => 2 | 1 => 2 | 2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 2 => 1 | 2 => 1 | 2 => 2
1 => 2 | 1 => 2 | 2 => 2 | 1 => 3 | 2 => 1 | 2 => 2 | 1 => 2 | 2 => 1 | 2 => 2 | 2 => 1
2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 1 => 2 | 2 => 1 | 2 => 2 | 1 => 2 | 2 => 1
2 => 2 | 2 => 1 | 2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 2 => 1 | 2 => 1 | 2 => 2
1 => 2 | 2 => 1 | 2 => 2 | 2 => 1 | 2 => 1 | 2 => 3 | 1 => 2 | 1 => 2 | 2 => 2 | 1 => 2
2 => 1 | 2 => 2 | 1 => 2 | 1 => 2 | 2 => 2 | 2 => 1 | 2 => 1 | 2 => 2 | 1 => 2 | 1 => 2
2 => 2 | 1 => 3 | 2 => 1 | 2 => 2 | 1 => 2 | 2 => 1 | 2 => 2 | 2 => 1 | 2 => 1 | 2 => 3
1 => 2 | 1 => 2 | 2 => 2 | 1 => 3 | 2 => 1 | 2 => 3 | 1 => 3 |
общее число перемещений: 127
Это особый образец плодотворности рекурсии! Попробуйте записать решение этой задачи в не рекурсивной форме. А ещё лучше — попробуйте затем кому-то объяснить ваше решение в не рекурсивной форме.
Примечание: О том, насколько это непростое занятие, не рекурсивное решение этой задачи, и как придётся поуродоваться
- вы можете почитать вот в этой очень интересной статье:
В лабиринтах Ханойских башен и по ссылкам оттуда на публикации … как изощряются профессионалы. Там же утверждается, что общее число операций равно 2^N-1, где N количество дисков – что и подтверждает наше выполнение.
