Ханойские башни

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

Правила: за ход перемещается один диск, только верхний со стержня, и класть больший на меньший нельзя.

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

Индукция

База. Один диск переносится одним ходом.

Переход. Пусть мы умеем переносить $n-1$ дисков с любого стержня на любой. Тогда $n$ дисков переносятся так:

1. перенести верхние $n-1$ дисков на промежуточный стержень;
2. переложить самый большой диск на целевой;
3. перенести $n-1$ дисков с промежуточного на целевой.

Почему шаг 1 законен, хотя внизу лежит большой диск: он самый большой из всех, значит, ни один диск не может оказаться под ним неправильно. Для перекладывания верхних $n-1$ его как будто нет.

Шаг 2 законен, потому что целевой стержень к этому моменту пуст.

Шаг 3 — то же предположение индукции.

flowchart LR
    A["n дисков<br/>на стержне A"] -->|"шаг 1<br/>рекурсия для n−1"| B["n−1 на B,<br/>большой на A"]
    B -->|"шаг 2<br/>один ход"| C["n−1 на B,<br/>большой на C"]
    C -->|"шаг 3<br/>рекурсия для n−1"| D["n дисков<br/>на стержне C"]

Индукция замкнулась: решение существует всегда, для любого $n$.

Код

vector<pair<int, int>> moves;

int thirdPeg(int from, int to) { return 3 - from - to; }   // стержни 0, 1, 2

void hanoi(int from, int to, int count) {
    if (count == 0) return;
    int middle = thirdPeg(from, to);
    hanoi(from, middle, count - 1);
    moves.push_back({from, to});
    hanoi(middle, to, count - 1);
}

Функция thirdPeg возвращает единственный стержень, не совпадающий с двумя данными. Приём 3 - from - to работает, потому что сумма всех трёх номеров равна $0 + 1 + 2 = 3$; писать шесть условий не нужно.

Проверено: для $n$ от 1 до 16 последовательность корректна (ни один диск не кладётся на меньший), пирамида собирается на третьем стержне в правильном порядке, и число ходов равно ровно $2^n - 1$.

Число ходов

Из рекурсии сразу следует $T(n) = 2T(n-1) + 1$, откуда $T(n) = 2^n - 1$.

Это и минимально возможное число ходов: чтобы переложить нижний диск, надо освободить его стержень, то есть увести $n-1$ дисков на промежуточный, а это не меньше $T(n-1)$ ходов; после его перекладывания их надо вернуть — ещё $T(n-1)$.

Практическое следствие: выводить сами ходы можно лишь при $n$ примерно до 25. Для больших $n$ задачи спрашивают только их количество — а это уже формула, а не перебор.

Чему это учит

Ханойские башни — лучший пример двух вещей.

Иногда правильно не понимать решение целиком. Никто не держит в голове порядок из тысячи ходов. Достаточно поверить, что для $n-1$ решение есть, — и построить шаг.

Рекурсия строит не только числа, но и ответы. Здесь она выдаёт последовательность действий, накапливая её в общем массиве. Тот же приём — в восстановлении ответа в динамике и в выводе пути в графе.

И наоборот: попытка расписать ходы «руками», по шаблону, ни к чему не приводит. Задача разрешима именно потому, что её удаётся свести к себе же меньшего размера.

Родственные задачи

Четыре стержня. Задача становится заметно сложнее: оптимальное число ходов даётся алгоритмом Фрейма—Стюарта, а его оптимальность доказана лишь недавно.

Найти $k$-й ход, не выписывая остальные. Решается рассуждением: первые $2^{n-1}-1$ ходов — это рекурсия для $n-1$, следующий — большой диск, дальше опять рекурсия. Спуск по этой структуре занимает $O(n)$.

Восстановить, где какой диск после $k$ ходов. Тот же спуск, только следим за положением каждого диска.

Все три — упражнения на ту же индукцию, и все три решаются тем, что вы понимаете структуру последовательности ходов, а не саму последовательность.