Ханойские Башни: большая задача из маленьких

Перед вами разбор классической задачи, когда требуется перенесите все диски со стержня A на стержень C, используя B как вспомогательный. За один ход можно переместить только верхний диск. Большой диск нельзя класть на маленький.

Решение. Чтобы перенести башню из пяти дисков, сначала перенесём четыре верхних диска на B. Затем переместим самый большой диск на C и положим на него четыре оставшихся. Перенос четырёх дисков решается точно так же, через перенос трёх, и так далее — до одного диска.

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

Нажимайте «Шаг», чтобы наблюдать каждый ход, или «Авто / пауза», чтобы включить или остановить автоматическое выполнение. «Сначала» возвращает диски на A. Модель демонстрирует готовое решение; выбирать ходы самостоятельно не требуется.

Для пяти дисков достаточно 31 хода. Для N дисков минимальное число ходов равно 2^N − 1. Измените константу N в коде (от 1 до 7) и сравните число ходов: добавление всего одного диска почти удваивает работу.