Ханойская башня - старая загадка. Тем не менее, он продолжает удивлять своим элегантным решением, которое скрывается за его простотой.
Анимации, показанные в этой статье, построены на библиотеке Python под названием Manim. Эта конкретная анимация была основана на анимации, использованной Reducible в видео на YouTube.
Сначала нам нужно разобраться в небольших случаях. Затем мы собираемся обобщить для других дисков. Наконец, мы построим рекурсивный алгоритм, который решает эту проблему за минимальное количество шагов. В пути помогут анимации.
Словарь и обозначения
- Род: Вещи, куда можно поставить диски. Есть 3 стержня: крайний левый R0, средний R1 и крайний правый R2.
- Диски: объекты, которые можно перемещать между стержнями. Верхний диск - D0, следующий по размеру - D1 и т. Д. Не может быть большего диска над меньшим, и движение состоит из одного диска за раз.
- Перемещение будет обозначено Dn-Rm, где диск n перемещается к стержню m.
Два диска
Решение состоит из 3 шагов: D0-R1, D1-R2, D0-R2. У каждого движения есть важная особенность.
- Переместите D0 (самый маленький диск) в R1 (средний стержень).
- Проденьте D1 (самый большой диск) в R2 (последняя штанга).
- Переместите D0 (наименьший диск) на R2 (последняя штанга).
Три диска
Решение состоит из 7 шагов. Однако можно сказать, что решение состоит из трех основных частей, как и в случае выше. Обратите внимание, что на этапах 1 и 3 два верхних диска перемещаются с одного стержня на другой.
- Переместите D0 и D1 (все, кроме самого большого) в R1 (средний стержень). Шаги 1–3
- Проденьте D2 (самый большой диск) на R2 (последняя штанга). Шаг 4
- Переместите D0 и D1 (все, кроме самого большого) на R2 (последняя штанга). Шаг 4–7
Четыре диска и выше
Для этого начинает раскрываться закономерность. Опять же, алгоритм для каждого диска больше 3 аналогичен.
- Переместите самые верхние диски, кроме самого большого, в R1.
- Передайте самый большой R2.
- Переместите все диски с 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