На этом шаге мы приведем это решение.

    Как можно решить задачу о Ханойских башнях? Предположим, что мы пытаемся переместить только один диск. Тогда мы бы знали, как это сделать, верно? Фактически перемещение одного диска - базовый случай для рекурсивного решения данной задачи. Перемещение нескольких дисков является рекурсивным случаем. Ключевой момент в том, что у нас, по сути, есть два сценария, которые необходимо закодировать: перемещение одного диска (базовый случай) и перемещение нескольких дисков (рекурсивный случай).

    Чтобы понять рекурсивный случай, рассмотрим конкретный пример. Предположим, у нас есть три диска - верхний, средний и нижний, расположенные на башне А, и мы хотим переместить их на башню С. (Впоследствии это поможет схематически описать задачу.) Сначала мы могли бы переместить верхний диск на башню С. Затем - переместить средний диск на башню В, а после этого - верхний диск с башни С на башню В. Теперь у нас есть нижний диск, все еще расположенный на башне А, и два верхних диска на башне В. По существу, мы уже успешно переместили два диска с одной башни (А) на другую (В). Перемещение нижнего диска с А на С является базовым случаем (перемещение одного диска). Теперь можем переместить два верхних диска с В на С посредством той же процедуры, что и с А на В. Перемещаем верхний диск на А, средний - на С и, наконец, верхний - с А на С.

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

    В примере с тремя дисками был простой базовый случай перемещения одного диска и рекурсивный случай перемещения остальных дисков (в данном случае двух) с применением временной третьей башни. Мы можем разбить рекурсивный случай на следующие этапы.

1. Переместить верхние n - 1 дисков с башни Ана башню В (временная), используя С в качестве промежуточной башни.

2. Переместить нижний диск с А на С.

3. Переместить n - 1 дисков с башни В на башню С, башня А - промежуточная.

    Удивительно, но этот рекурсивный алгоритм работает не только для трех, а для любого количества дисков. Закодируем его как функцию hanoi(), которая отвечает за перемещение дисков с одной башни на другую, используя третью временную башню.

def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None:
    if n == 1:
        end.push(begin.pop())
    else:
        hanoi(begin, temp, end, n - 1)
        hanoi(begin, end, temp, 1)
        hanoi(temp, end, begin, n - 1)

if __name__ == "__main__":
    print("Начальная позиция")
    print(tower_a)
    print(tower_b)
    print(tower_c)
    hanoi(tower_a, tower_c, tower_b, num_discs)
    print("Конечная позиция")
    print(tower_a)
    print(tower_b)
    print(tower_c)

Рис.1. Результат работы приложения

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

    Кстати, функция hanoi() будет выполняться экспоненциальное число раз в зависимости от количества дисков, что делает решение задачи даже для 64 дисков непригодным. Вы можете попробовать выполнить ее с другим числом дисков, изменяя переменную num_discs. По мере увеличения количества дисков число шагов выполнения задачи о ханойских башнях растет экспоненциально, подробнее об этом можно прочитать во множестве источников.

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

Предыдущий шаг Содержание Следующий шаг