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

Анимации, показанные в этой статье, построены на библиотеке Python под названием Manim. Эта конкретная анимация была основана на анимации, использованной Reducible в видео на YouTube.

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

Словарь и обозначения

  • Род: Вещи, куда можно поставить диски. Есть 3 стержня: крайний левый R0, средний R1 и крайний правый R2.
  • Диски: объекты, которые можно перемещать между стержнями. Верхний диск - D0, следующий по размеру - D1 и т. Д. Не может быть большего диска над меньшим, и движение состоит из одного диска за раз.
  • Перемещение будет обозначено Dn-Rm, где диск n перемещается к стержню m.

Два диска

Решение состоит из 3 шагов: D0-R1, D1-R2, D0-R2. У каждого движения есть важная особенность.

  1. Переместите D0 (самый маленький диск) в R1 (средний стержень).
  2. Проденьте D1 (самый большой диск) в R2 (последняя штанга).
  3. Переместите D0 (наименьший диск) на R2 (последняя штанга).

Три диска

Решение состоит из 7 шагов. Однако можно сказать, что решение состоит из трех основных частей, как и в случае выше. Обратите внимание, что на этапах 1 и 3 два верхних диска перемещаются с одного стержня на другой.

  1. Переместите D0 и D1 (все, кроме самого большого) в R1 (средний стержень). Шаги 1–3
  2. Проденьте D2 (самый большой диск) на R2 (последняя штанга). Шаг 4
  3. Переместите D0 и D1 (все, кроме самого большого) на R2 (последняя штанга). Шаг 4–7

Четыре диска и выше

Для этого начинает раскрываться закономерность. Опять же, алгоритм для каждого диска больше 3 аналогичен.

  1. Переместите самые верхние диски, кроме самого большого, в R1.
  2. Передайте самый большой R2.
  3. Переместите все диски с R1 на R2.

Вы видите закономерность? Вот где рекурсия может помочь с задачей.

Рекурсивный алгоритм

Если имеется n дисков, шаг 1 должен переместить n-1 самых верхних дисков на средний стержень. Это подзадача, которая может быть решена, если мы переместим самые верхние n-2 дисков на последний стержень R2. Опять же, это подзадача, и мы продолжаем чередовать R1 и R2, пока не дойдем до случая перемещения 2 дисков. Здесь и происходит рекурсия.

  • Функция move (n, R0, R1) перемещает n самых верхних дисков с R0 на R1.
  • Функция pass (Dn, R0, R2) перемещает только диск n из R0 в R2.

Как показано на диаграмме, стержни меняют каждую итерацию. Как мы можем узнать, какие стержни передать функции? Для этого нужен конкретный подход. У каждого стержня своя роль в зависимости от функции:

  • Актуальный стержень: Где диски.
  • Стержень цели: Куда нужно брать диски.
  • Другой стержень: оставшийся стержень.

Например: в функции move (n, R0, R2) R0 - это фактический стержень, R2 - это целевой стержень, а R1 - это другой стержень. Когда рекурсия переходит к перемещению (n-1, R0, R1), R0 - это фактический стержень, R1 - целевой стержень, а R2 - другой стержень.

На каждом этапе рекурсии при первом move () происходит следующее:

  • Фактический стержень остается фактическим стержнем
  • Жезл цели превращается в Другой Жезл
  • Другой Жезл превращается в Жезл цели

Во втором move ()

  • Настоящий Жезл превращается в Другой Жезл
  • Жезл цели остается жезлом цели
  • Другой Жезл превращается в Настоящий Жезл

С этим пониманием кодирование будет простым.

Реализация на Python

Инициализировать количество дисков, стержней и счетчика

num_disks = 3
R0 = list(range(num_disks, 0, -1))
R1 = []
R2 = []
cont = 0

Функция для рендеринга стержней и дисков

def render():
    global cont
    cont += 1
    print(R0)
    print(R1)
    print(R2)
    print('CONT: ', cont)
    print()

Рекурсия

def move(disks, actual, objective, other):
    if disks == 2:
        render()
        actual.pop()
        other.append(1)  # Disk 1 to other
        render()
        actual.pop()
        objective.append(2)  # Disk 2 to objective
        render()
        other.pop()
        objective.append(1)   # Disk 1 to objective
    else:
        move(disks - 1, actual, other, objective)
        render()
        actual.pop()
        objective.append(disks)  # Last disk to objective
        move(disks - 1, other, objective, actual)


move(num_disks, R0, R2, R1)
render()

Выход

На выходе получается пошаговое решение головоломки. Он повернут влево, так как каждый ряд представляет собой стержень. Например, шаг номер 5 на 4 дисках следующий:

[4]
[3]
[2, 1]
CONT:  5

Это представление на изображении ниже.

Подводить итоги

Чтобы решить эту проблему, мы сначала познакомились с простейшими случаями и нашли способ их понять. Затем мы увидели, что этот подход можно масштабировать для большего количества дисков. Это означало, что мы могли разбить большую проблему на более мелкие подзадачи, в этом случае большая проблема перемещения n дисков на R2 разбилась на три меньшие подзадачи. Каждая итерация имела одинаковую структуру, поэтому мы могли применять рекурсию.

В завершение я оставляю анимацию для 5 дисков просто потому, что я нашел их удовлетворительными и увлекательными. Теперь компьютер может решить эту проблему, а вы можете?

Надеюсь, вам понравилась эта статья!

Больше контента на plainenglish.io