EssayAI
Блог
Блог
Естественные науки

Ханойские башни и рекурсия: решение по шагам

8 ноября 2026Время чтения: 8 минут
#ханойские башни#рекурсия#алгоритмы#сложность алгоритма#программирование
Ханойские башни и рекурсия: решение по шагам

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

Для трёх дисков хватит семи ходов. Но сколько понадобится для десяти и почему меньше не получится? Выберите высоту башни в калькуляторе: он покажет минимум и сравнит его с результатами для меньших башен.

Правила и цель

Обозначим стержни буквами А, Б и В. В начале все nn дисков лежат на А в порядке убывания размера снизу вверх; нужно перенести их на В, сохранив этот порядок. Стержень Б служит временной опорой. Диски различаются по размеру, и за ход разрешено брать только верхний диск одного стержня и класть его на пустой стержень или на больший диск.

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

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

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

Рекурсивная идея: две меньшие задачи

Чтобы перенести самый большой диск с А на В, сначала нужно снять с него все n−1n-1 меньших. Они не могут лежать на В в момент этого переноса: большой диск нельзя поставить на меньший. Значит, непосредственно перед переносом большого диска вся меньшая башня должна стоять на Б.

Отсюда возникает порядок действий:

  1. Перенести n−1n-1 дисков с А на Б, используя В как вспомогательный стержень.
  2. Перенести самый большой диск с А на В.
  3. Перенести n−1n-1 дисков с Б на В, используя А как вспомогательный.

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

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

Пример: семь ходов для трёх дисков

Нумеруем диски от меньшего к большему: 1, 2, 3. Исходная стопка находится на А, цель - В. Полная оптимальная последовательность получается так:

ХодДискОткуда → куда
11А → В
22А → Б
31В → Б
43А → В
51Б → А
62Б → В
71А → В

Первые три хода переносят башню из двух дисков на Б. Четвёртый освобождённый большой диск перемещает на В. Последние три собирают меньшую башню поверх него. Для проверки на бумаге после каждой строки записывайте содержимое всех трёх стержней снизу вверх; такой способ разобран в материале о трассировке алгоритма.

Роли букв меняются от подзадачи к подзадаче. Например, на первых трёх ходах Б - цель, а В - вспомогательный стержень. Если в каждом вызове считать В постоянной целью, последовательность нарушит план уже на втором уровне рекурсии.

Код и стек вызовов

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

def hanoi(n, source, target, spare):
    if n == 0:
        return
    hanoi(n - 1, source, spare, target)
    print(source, '→', target)
    hanoi(n - 1, spare, target, source)

hanoi(3, 'А', 'В', 'Б')

В первом вложенном вызове прежняя цель становится вспомогательной, а прежний вспомогательный стержень - целью. Во втором источником становится вспомогательный стержень родителя. Строка print выполняется после возврата первого вызова и до начала второго; перестановка строк меняет смысл алгоритма.

Каждый активный вызов хранит свои аргументы и место продолжения. Пока программа спускается к базовому случаю, эти записи находятся в стеке вызовов; при возврате выполнение продолжается после соответствующего вызова. Не нужно одновременно держать в памяти все будущие ходы. Предусловие кода: nn - неотрицательное целое, а три имени обозначают разные стержня. Для отрицательного nn такой базовый случай не наступит.

Сколько ходов нужно

Обозначим минимум через H(n)H(n). Пустой башне нужно H(0)=0H(0)=0 ходов. Построенный алгоритм даёт соотношение

H(n)=2H(n−1)+1,H(0)=0.H(n)=2H(n-1)+1,\qquad H(0)=0.

Два слагаемых H(n−1)H(n-1) - перенос меньшей башни до и после большого диска, единица - ход самого большого. Подстановка последовательно даёт H(1)=1H(1)=1, H(2)=3H(2)=3, H(3)=7H(3)=7, H(4)=15H(4)=15, H(5)=31H(5)=31. В общем случае получается

H(n)=2n−1.H(n)=2^n-1.

Проверим формулу индукцией. При n=0n=0 она равна нулю. Если для n−1n-1 верно H(n−1)=2n−1−1H(n-1)=2^{n-1}-1, то 2H(n−1)+1=2(2n−1−1)+1=2n−12H(n-1)+1=2(2^{n-1}-1)+1=2^n-1. Так формула согласуется с базой и переходом. Само рекуррентное соотношение и разбиение на три этапа используются и в учебном разборе Carnegie Mellon University.

Столбцы показывают минимум ходов для башен из одного, двух, трёх, четырёх и пяти дисков: 1, 3, 7, 15 и 31
Столбцы показывают минимум ходов для башен из одного, двух, трёх, четырёх и пяти дисков: 1, 3, 7, 15 и 31

Добавление диска почти удваивает работу: для десяти дисков необходимо уже 1023 хода. График считает число отдельных переносов, а не число строк программы или секунд выполнения. Никакая скорость исполнителя не меняет эту комбинаторную величину.

Почему это именно минимум

Формула описывает построенный способ, но для доказательства оптимальности нужна нижняя граница для любого допустимого способа. Рассмотрим момент первого переноса самого большого диска на целевой стержень. Все меньшие в этот момент должны находиться на единственном оставшемся стержне: они не могут ни лежать на большом, ни занимать его цель. Чтобы собрать их там из исходного положения, требуется не меньше H(n−1)H(n-1) ходов.

После этого большого диска меньшие ещё надо собрать на нём. На это требуется ещё как минимум H(n−1)H(n-1) ходов, а сам перенос большого занимает один. Даже если какой-то способ двигал большой диск раньше или позднее двигал его снова, он не может обойти эту нижнюю границу. Рекурсивный способ достигает её, следовательно, он оптимален для трёх стержней и описанных правил. При другом числе стержней или изменённых правилах это доказательство нельзя переносить автоматически.

Время и память алгоритма

Функция печатает ровно 2n−12^n-1 строк, поэтому при постоянной стоимости одного вывода её время составляет Θ(2n)\Theta(2^n). Оно экспоненциально по числу дисков. Одновременно активна только одна цепочка вложенных вызовов: от nn до нуля. Поэтому дополнительная память стека равна O(n)O(n), если выводить ходы сразу. Если сохранить весь список ходов, потребуется дополнительно Θ(2n)\Theta(2^n) памяти для результата.

Здесь рекурсия удобна для описания неизбежно длинного ответа; она не устраняет экспоненциальный размер последовательности. Для сравнения, в алгоритме Карацубы рекурсивное разбиение применяется к другой задаче и с другой оценкой времени. Формальная связь определения через предыдущий случай с классом функций обсуждается отдельно в статье о примитивно рекурсивных функциях.

Частые ошибки

  • Забыть базовый случай. Без остановки при n=0n=0 вызовы для неотрицательного входа продолжатся за пределы смысла задачи.
  • Не менять роли стержней. В первой подзадаче временный стержень становится целью; во второй - источником.
  • Считать перемещение стопки одним ходом. Подзадача скрывает множество отдельных переносов и стоит H(n−1)H(n-1) ходов.
  • Считать формулу доказательством минимума сама по себе. Нужна нижняя граница для любого допустимого решения, а не только подсчёт ходов выбранной программы.
  • Путать стек и сохранённый ответ. Стек занимает O(n)O(n), но полный список ходов имеет экспоненциальный размер.

FAQ

Можно ли решить задачу без рекурсии?

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

Обязательно ли двигать самый маленький диск первым?

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

Сколько вызовов одновременно находится в стеке?

В приведённой реализации максимум n+1n+1 вызовов, включая базовый вызов с нулём. Это не число всех вызовов за всё время работы и не число напечатанных ходов.

Коротко

Ханойские башни показывают рекурсию в действии: перенести меньшую башню, переместить большой диск и снова решить меньшую задачу. При трёх стержнях минимальное число ходов равно 2n−12^n-1; программа, печатающая ходы по мере нахождения, работает за Θ(2n)\Theta(2^n) времени и использует O(n)O(n) памяти стека.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Обходы двоичного дерева: порядки и примеры

Обходы двоичного дерева: порядки и примеры

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

8 ноября 20268 минут
Поиск максимума и минимума в массиве

Поиск максимума и минимума в массиве

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

8 ноября 20269 минут
Задача Иосифа Флавия: формула и решение

Задача Иосифа Флавия: формула и решение

Задача Иосифа Флавия: разбор счёта по кругу, рекуррентная формула, пример с семью участниками и решение для каждого второго с помощью двоичной записи.

8 ноября 20269 минут
Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77 на пошаговом примере: как скользящее окно находит повторы, что означают расстояние и длина, как работает перекрытие и от чего зависит размер результата.

8 ноября 20268 минут
Числа Белла: разбиения множества и формула

Числа Белла: разбиения множества и формула

Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

8 ноября 20269 минут
Числа Люка: формула, примеры и связь с Фибоначчи

Числа Люка: формула, примеры и связь с Фибоначчи

Числа Люка начинаются с 2 и 1 и строятся сложением двух предыдущих членов. Разбираем формулу, связь с числами Фибоначчи, примеры и алгоритм вычисления.

8 ноября 20268 минут