Напишем программы, которые решают Ханойскую башню, на Python и на C. Каждая выводит ходы для переноса 3 дисков с левого стержня на правый. Идея объясняется в статье Алгоритм Ханойской башни, поэтому здесь мы сосредоточимся на коде и запуске.

Решение с рекурсией на Python

Это самый основной вариант. Порядок «убрать верхние n − 1 дисков → переместить диск n → вернуть n − 1 дисков» прямо превращается в функцию.

def hanoi(n, src, dst, via, moves):
    if n == 0:
        return
    hanoi(n - 1, src, via, dst, moves)  # убираем верхние n-1 дисков
    moves.append((n, src, dst))         # перемещаем диск n
    hanoi(n - 1, via, dst, src, moves)  # возвращаем n-1 дисков


moves = []
hanoi(3, "левый", "правый", "средний", moves)
for i, (disc, src, dst) in enumerate(moves, 1):
    print(f"Ход {i}: диск {disc}: {src} → {dst}")
print(f"Всего ходов: {len(moves)}")

Сохраните код в файле hanoi.py и запустите командой python3 hanoi.py. Будет выведено следующее.

Ход 1: диск 1: левый → правый
Ход 2: диск 2: левый → средний
Ход 3: диск 1: правый → средний
Ход 4: диск 3: левый → правый
Ход 5: диск 1: средний → левый
Ход 6: диск 2: средний → правый
Ход 7: диск 1: левый → правый
Всего ходов: 7

Если изменить число 3 в hanoi(3, ...), программа решит задачу для любого числа дисков. Но число ходов равно 2ⁿ − 1, поэтому для 20 дисков это около миллиона ходов, для 30 — около миллиарда, то есть очень быстро становится огромным. У Python есть предел глубины рекурсии (по умолчанию около 1000 уровней), но глубина рекурсии в Ханойской башне равна числу дисков плюс 1, так что число ходов станет слишком большим раньше, чем это станет проблемой.

Решение без рекурсии на Python

Здесь порядок действий при решении вручную (два правила из статьи о том, как решать головоломку) записан прямо в виде цикла. Стержни обозначены номерами 0 (левый), 1 (средний) и 2 (правый).

def hanoi_loop(n):
    names = ["левый", "средний", "правый"]
    pegs = [list(range(n, 0, -1)), [], []]  # снизу вверх
    order = [0, 2, 1] if n % 2 == 1 else [0, 1, 2]  # порядок обхода диска 1
    pos = 0  # стержень, где диск 1 (какой по счёту в order)
    moves = []
    for m in range(1, 2 ** n):
        if m % 2 == 1:
            # нечётный ход: диск 1 на следующий стержень в выбранном направлении
            a = order[pos]
            pos = (pos + 1) % 3
            b = order[pos]
        else:
            # чётный ход: из двух стержней без диска 1 меньший диск на больший
            a, b = [p for p in range(3) if p != order[pos]]
            if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
                a, b = b, a
        pegs[b].append(pegs[a].pop())
        moves.append((pegs[b][-1], names[a], names[b]))
    return moves


for i, (disc, src, dst) in enumerate(hanoi_loop(3), 1):
    print(f"Ход {i}: диск {disc}: {src} → {dst}")

Вывод — те же 7 ходов, что и в варианте с рекурсией. Мы проверили, что при любом числе дисков от 1 до 10 получается тот же порядок ходов, что и в варианте с рекурсией.

Прямое вычисление из двоичной записи на Python

Здесь то, что делать на ходу m, вычисляется без прослеживания предыдущих ходов. Смысл формул объясняется в статье об алгоритме.

def hanoi_bits(n):
    for m in range(1, 2 ** n):
        disc = (m & -m).bit_length()     # число нулей в конце + 1
        src = (m & (m - 1)) % 3
        dst = ((m | (m - 1)) + 1) % 3
        yield disc, src, dst


print(list(hanoi_bits(3)))

При запуске выводится [(1, 0, 2), (2, 0, 1), (1, 2, 1), (3, 0, 2), (1, 1, 0), (2, 1, 2), (1, 0, 2)]. Это тройки (диск, исходный стержень, целевой стержень), и они совпадают с 7 ходами выше. Эта формула даёт порядок для переноса со стержня 0 на стержень 2 при нечётном числе дисков и со стержня 0 на стержень 1 при чётном, поэтому, чтобы перенести чётное число дисков вправо, меняйте местами стержни 1 и 2.

Решение с рекурсией на C

На C вид тот же, что и на Python.

#include <stdio.h>

static int count = 0;

void hanoi(int n, const char *src, const char *dst, const char *via) {
    if (n == 0) return;
    hanoi(n - 1, src, via, dst);
    count++;
    printf("Ход %d: диск %d: %s → %s\n", count, n, src, dst);
    hanoi(n - 1, via, dst, src);
}

int main(void) {
    hanoi(3, "левый", "правый", "средний");
    printf("Всего ходов: %d\n", count);
    return 0;
}

Сохраните код в файле hanoi.c, скомпилируйте командой cc -o hanoi hanoi.c и запустите командой ./hanoi: будут выведены те же 7 ходов, что и в варианте с рекурсией на Python, и строка «Всего ходов: 7». В строках используется кириллица, поэтому сохраняйте файл в кодировке UTF-8.

Где можно ошибиться при написании

  • Перепутать порядок аргументов: при первом вызове меняют местами «запасной стержень» и «стержень назначения», при втором — «исходный стержень» и «запасной». Если ошибиться здесь, появятся ходы, нарушающие правила.
  • Забыть условие остановки: если не остановиться при n == 0 (или n == 1), вызовы будут повторяться без конца.
  • Как проверить: приложите полученный порядок ходов к доске и убедитесь, что нигде большой диск не кладут на маленький и что число ходов равно 2ⁿ − 1.