Ханойская башня

Привет!

Сегодня я хотел бы поговорить о «Ханойской башне» и показать пример программы на Python.

Что такое Ханойская башня?

Ханойская башня — это головоломка, состоящая из трех стержней и нескольких дисков. Диски имеют разный размер, и изначально они сложены на одном стержне в порядке убывания размера сверху вниз. Правила следующие:

За один раз можно перемещать только один диск.
Больший диск нельзя класть поверх меньшего.

Считается, что эта головоломка является отличным материалом для изучения рекурсивного мышления. Рекурсия — это метод решения проблемы путем разбиения её на более мелкие проблемы того же типа. В Ханойской башне для перемещения n дисков мы повторяем операцию перемещения n-1 дисков.

Давайте решим Ханойскую башню на Python

Ниже приведен пример кода на Python для решения головоломки Ханойская башня.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

# Пример: Перемещение 3 дисков с A на C
hanoi(3, 'A', 'C', 'B')

В этом коде функция hanoi вызывается рекурсивно, и отображаются шаги для перемещения дисков. Например, для 3 дисков будет получен следующий результат:

1
2
3
4
5
6
7
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Таким образом, используя рекурсивный подход, даже сложные проблемы можно решать довольно просто.

Сколько времени потребуется для перемещения 64 дисков?

Минимальное количество перемещений для Ханойской башни составляет 2^n - 1. Это означает, что для перемещения 64 дисков потребуется 2^64 - 1 раз, или около 1,84×10^19 перемещений. Даже если мы могли бы делать одно перемещение в секунду, это заняло бы около 584 миллиардов лет. Это примерно в 42 раза больше возраста Вселенной (около 13,7 миллиарда лет).

Следовательно, по мере увеличения количества дисков количество необходимых перемещений растет в геометрической прогрессии. В связи с этим перемещение 64 дисков в реальности не представляется возможным.

Заключение

Ханойская башня — это превосходная головоломка для изучения рекурсивного мышления. С помощью Python можно легко реализовать её решение. Однако стоит учитывать, что с увеличением числа дисков количество необходимых перемещений резко возрастает.

Понимая рекурсивный подход и самостоятельно написав код, вы сможете улучшить свои навыки программирования. Обязательно попробуйте решить задачу о Ханойской башне.