Подготовка к алгоритмическим задачам

Ханойские башни: классическая задача на рекурсию с разбором

10 мин чтения

алгоритмы

рекурсия

python

Условие

Есть три стержня и n дисков разного размера, надетых на первый стержень по убыванию — самый большой снизу. Нужно перенести всю башню на третий стержень, соблюдая два правила:

За один ход перекладывается только один диск, причём верхний.
Больший диск нельзя класть на меньший.

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

Ключевая мысль

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

Ответ очевиден: над ним не должно быть ничего, а целевой стержень должен быть пуст. То есть все остальные n−1 дисков должны оказаться на вспомогательном стержне.

Отсюда решение из трёх шагов:

1. Перенести n-1 верхних дисков со СТАРТА на ВСПОМОГАТЕЛЬНЫЙ
2. Переложить самый большой диск со СТАРТА на ЦЕЛЬ
3. Перенести n-1 дисков со ВСПОМОГАТЕЛЬНОГО на ЦЕЛЬ

Шаги 1 и 3 — та же самая задача, только меньшего размера. Это и есть рекурсия: мы не решаем её целиком, мы сводим её к себе же.

Базовый случай: перенести ноль дисков — не делать ничего.

Код на Python

def hanoi(n: int, source: str = 'A', target: str = 'C', auxiliary: str = 'B') -> None:
    if n == 0:
        return  # переносить нечего

    # 1. освобождаем самый большой диск
    hanoi(n - 1, source, auxiliary, target)

    # 2. перекладываем его на место
    print(f'диск {n}: {source} → {target}')

    # 3. возвращаем остальные поверх него
    hanoi(n - 1, auxiliary, target, source)


hanoi(3)

Вывод:

диск 1: A → C
диск 2: A → B
диск 1: C → B
диск 3: A → C
диск 1: B → A
диск 2: B → C
диск 1: A → C

Семь ходов для трёх дисков. Всё решение — четыре строки, и в нём нет ни одного условия про «какой диск куда можно». Правила соблюдаются автоматически, потому что рекурсия всегда работает с корректной подбашней.

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

Почему ровно 2ⁿ − 1 ходов

Обозначим T(n) — количество ходов для n дисков. Из структуры алгоритма:

T(n) = T(n-1) + 1 + T(n-1) = 2·T(n-1) + 1
T(0) = 0

Раскроем:

T(1) = 2·0 + 1 = 1
T(2) = 2·1 + 1 = 3
T(3) = 2·3 + 1 = 7
T(4) = 2·7 + 1 = 15

Закономерность видна: T(n) = 2ⁿ − 1. Строгое доказательство — по индукции: если T(n−1) = 2ⁿ⁻¹ − 1, то T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1.

Важно: это не просто оценка алгоритма, а доказанный минимум. Меньше чем за 2ⁿ − 1 ход задачу решить невозможно, потому что самый большой диск обязан сдвинуться хотя бы раз, а перед этим все остальные обязаны собраться на одном стержне.

Сложность — O(2ⁿ) по времени и O(n) по памяти на стек рекурсии.

Про легенду с 64 дисками

По легенде монахи в храме Бенареса перекладывают 64 золотых диска, и когда закончат — наступит конец света.

Посчитаем: 2⁶⁴ − 1 ≈ 1.8 × 10¹⁹ ходов. Если делать один ход в секунду без перерывов, понадобится около 585 миллиардов лет — это в сорок раз больше возраста Вселенной.

Пример хорош тем, что даёт физическое ощущение экспоненциального роста. Алгоритм с O(2ⁿ) не «медленный» — он невыполнимый уже при небольших n.

Возвращаем список ходов

Печать в консоль неудобна для тестирования. Соберём ходы в список:

def hanoi_moves(n: int, source: str = 'A', target: str = 'C',
                auxiliary: str = 'B') -> list[tuple[int, str, str]]:
    if n == 0:
        return []

    return [
        *hanoi_moves(n - 1, source, auxiliary, target),
        (n, source, target),
        *hanoi_moves(n - 1, auxiliary, target, source),
    ]


moves = hanoi_moves(4)
print(len(moves))   # 15 = 2^4 - 1
print(moves[:3])    # [(1, 'A', 'B'), (2, 'A', 'C'), (1, 'B', 'C')]

Такую версию легко проверить тестом: количество ходов должно равняться 2ⁿ − 1, а симуляция ходов не должна нарушить правило «большой на маленький».

Итеративное решение

Рекурсию можно убрать. Существует красивое правило, дающее оптимальную последовательность без единого рекурсивного вызова:

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

def hanoi_iterative(n: int) -> list[tuple[str, str]]:
    source, target, auxiliary = 'A', 'C', 'B'
    if n % 2 == 0:
        target, auxiliary = auxiliary, target

    pegs = {'A': list(range(n, 0, -1)), 'B': [], 'C': []}
    moves = []

    def move(frm: str, to: str) -> None:
        # кладём меньший на больший, направление определяем сами
        if not pegs[frm]:
            frm, to = to, frm
        elif pegs[to] and pegs[to][-1] < pegs[frm][-1]:
            frm, to = to, frm
        pegs[to].append(pegs[frm].pop())
        moves.append((frm, to))

    for i in range(1, 2 ** n):
        if i % 3 == 1:
            move(source, target)
        elif i % 3 == 2:
            move(source, auxiliary)
        else:
            move(auxiliary, target)

    return moves


print(len(hanoi_iterative(3)))  # 7

Итеративная версия не быстрее — количество ходов то же самое, 2ⁿ − 1. Она лишь не расходует стек. И, как хорошо видно, читается заметно хуже рекурсивной. Это показательный пример ситуации, где рекурсия — не роскошь, а самый понятный способ выразить решение.

Чему учит эта задача

Рекурсия — это про доверие. Самый тяжёлый психологический барьер у новичков — желание «раскрутить» все уровни в голове. Не надо. Достаточно поверить, что вызов hanoi(n-1, ...) корректно перенесёт n−1 дисков, и правильно описать один шаг.

Базовый случай обязателен. Без if n == 0: return рекурсия уйдёт в бесконечность и упадёт по переполнению стека.

Экспонента — это приговор. Задача показывает, что оптимальный алгоритм не обязан быть быстрым. Здесь 2ⁿ − 1 это минимум, и улучшить его невозможно в принципе.

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

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

Базовый случай n == 1 вместо n == 0. Работать будет, но код станет длиннее — придётся отдельно печатать ход. Вариант с нулём короче и симметричнее.

Попытка проверять правила вручную. Некоторые пишут условия «можно ли класть этот диск». Это лишнее: корректный рекурсивный алгоритм не может их нарушить.

Что запомнить

Решение сводится к трём шагам: перенести n−1 наверх, переложить большой, вернуть n−1 обратно.
Роли стержней меняются в каждом рекурсивном вызове — это ключевая деталь.
Минимальное число ходов ровно 2ⁿ − 1, и это доказанный предел, а не особенность алгоритма.
Сложность O(2ⁿ) по времени, O(n) по памяти на стек.
Итеративная версия существует, но читается хуже и не даёт выигрыша в скорости.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→