Возможно, самое захватывающее приложение рекурсии
На прошлой неделе я говорил о последовательности Фибоначчи, а за неделю до этого я объяснил, как написать функцию, которая вычисляет факториал с использованием рекурсии. Это последняя часть нашего разговора о рекурсии и, вероятно, самая захватывающая.
Ханойские башни - математическая игра со следующими правилами. Учитывая три стержня и n дисков разного диаметра, нам нужно переместить весь пакет дисков с одного стержня на другой. Однако есть три правила:
- Диск большего размера никогда не может быть поверх меньшего. Например, вы не можете поместить диск с d = 3 поверх диска с d = 1.
- Вы можете перемещать только один диск за раз, поэтому вы не можете просто взять всю стопку и положить ее на другой стержень.
- Вы не можете взять диск из-под другого. Вы можете перемещать только тот, который находится сверху.
Итак, нам нужна программа, которая вернет инструкции об успешной победе в этой игре с минимальным количеством шагов. И, конечно же, эта программа будет использовать для этого рекурсию.
Как мы помним из предыдущих примеров, рекурсия - это разделение большой проблемы на более мелкие подзадачи, которые легче решить. Итак, давайте перепроектируем его и начнем с самого простого случая: у нас есть три стержня и только один диск. Подносим прямо к стержню C (или B, неважно), правильно?
И код будет выглядеть примерно так:
def towers_of_hanoi(n, source_rod, destination_rod, auxilliary_rod): if n == 1: print(“Move disk 1 from rod”, source_rod ,”to rod”, destination_rod)
Даже когда у нас есть 2 диска разного размера, алгоритм довольно интуитивно понятен:
А что, если у нас есть, скажем, 5 дисков? Какое оптимальное решение?
Если вы когда-нибудь попробуете сыграть в эту игру на самом деле, вы поймете, что ходы, которые вы делаете, могут быть двух типов: когда у вас есть выбор, что делать дальше, и когда нет. Например, в случае n = 5 (см. Рисунок выше) у нас есть выбор, куда поставить оранжевый диск: на стержень B или на стержень C. Но после этого мы этого не делаем: если оранжевый диск находится на стержне B, мы можем положить только фиолетовый на стержень C, иначе мы нарушим правило №1 этой игры, которое гласит, что диск большего размера не может быть помещен поверх меньшего. Это наблюдение переформулирует нашу проблему: нам нужны только инструкции, чтобы выяснить, какой выбор сделать на шагах, когда он у нас есть.
Сногсшибательный факт: чтобы выиграть в этой игре, нужно считать в двоичном формате. Помните двоичный код? Вместо 9 цифр (0–9) мы используем только два, 0 и 1: 0, 1, 10, 11, 100 и т. Д. Чтобы понять, почему двоичный счет имеет отношение к этой проблеме и к чему вся эта игра рекурсии нам нужно еще больше разбить проблему. Независимо от того, сколько дисков у нас есть на стержне A, все наши задачи по существу сводятся к следующей проблеме: если бы мы могли переместить все диски, кроме одного в самом низу (красный на моем изображении выше), на стержень B, мы могли бы просто переместить красный диск на стержень C, а затем переместить сваю на стержень C. Три простых шага, как в задаче с двумя дисками. Единственная уловка заключается в том, что шаг «переместить стопку» на самом деле представляет собой набор шагов, которые нам также необходимо выяснить. Следовательно, рекурсивная функция должна управлять n-1 дисками (команда «переместить стопку») и вызывать себя, пока не достигнет n = 1, чтобы выиграть игру:
def towers_of_hanoi(n, source_rod, destination_rod, auxilliary_rod): if n == 1: print(“Move disk 1 from rod”, source_rod,”to rod”, destination_rod) return towers_of_hanoi(n-1, source_rod, auxilliary_rod, destination_rod) print(“Move disk”, n, “from “, source_rod, “to “, destination_rod) towers_of_hanoi(n-1, auxilliary_rod, destination_rod, source_rod)
Итак, для n = 3:
towers_of_hanoi(3, ‘A’, ‘B’, ‘C’)
Результатом будет:
Move disk 1 from rod A to rod B Move disk 2 from A to C Move disk 1 from rod B to rod C Move disk 3 from A to B Move disk 1 from rod C to rod A Move disk 2 from C to B Move disk 1 from rod A to rod B
Итак, как счет в двоичном формате помогает? Давайте посмотрим на случай, когда n = 2. Мы берем две цифры, обе ноль 00, и счет представляет перемещение: 01 означает, что мы перемещаем диск сверху к стержню B справа. Затем мы считаем еще 10, что означает, что мы берем ранее нетронутый диск на нижней части стержня A и перемещаем его. Где? Конечно, на стержень C, потому что мы не можем поставить больший диск поверх меньшего. Затем мы снова считаем 11, что означает, что мы берем меньший диск на стержне B и перемещаем его на стержень C. Место, где меняются цифры, обозначает, какой диск мы перемещаем!
Итак, если бы мы решали проблему для n = 3 (как в коде выше), мы бы разбили проблему на две части: подсчет до 2, что мы уже знаем, как это сделать, и последний шаг. Как и в примерах факториала и Фибоначчи, если мы знаем, что делать с первыми двумя числами (0 и 1 или 1 и 2), это вся информация, которая нам нужна для решения задачи для такого количества n, которое они бросают в нас.
Источники:
