TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Ханойские башни
Что ты узнаешь
- Рекурсивный план: чтобы перенести n дисков, убери n - 1 с дороги, перенеси самый большой, потом верни n - 1 сверху.
- Два меньших переноса это та же головоломка, поэтому функция вызывает себя дважды. Базовый случай это 0 дисков: ничего не делать.
- Ходы каждый раз удваиваются плюс один: 2^n - 1. 64 диска заняли бы около 585 миллиардов лет при одном ходе в секунду.
Как идёт урок
Монахи переносят 64 золотых диска. Когда закончат, наступит конец света. Стоит ли волноваться?
Сначала попробуй 3 диска. Перенеси башню с A на C: по одному диску, никогда не кладя больший на меньший.
Ещё один диск. Сколько ходов для 4?
3 диска в лучшем случае заняли 7.
Считай верхние 3 диска одним блоком.
Сними блок с большого диска, перенеси большой диск на C, верни блок сверху.
Большой диск может двинуться, только когда всё над ним лежит на запасном стержне. Перенести туда 3 диска это головоломка из 3 дисков (7 ходов); потом 1 ход; потом снова головоломка из 3 дисков (7 ходов).
Рекурсивный план.
Чтобы перенести n дисков с A на C: перенеси n - 1 дисков с A на B, перенеси самый большой с A на C, перенеси n - 1 дисков с B на C.
Оба меньших переноса это та же головоломка с одним диском меньше, поэтому функция вызывает себя дважды. Это рекурсивный план.
Базовый случай: 0 дисков, делать нечего. Ходы: 2 x (ходы для n - 1) + 1.
Обгони монаха: 4 диска вручную.
Норма 15. Пользуйся планом: 3 с дороги, большой на другую сторону, 3 обратно.
Запиши план кодом.
hanoi(n, a, b, c) переносит n дисков с a на b, используя c как запасной. Сделай так, чтобы она печатала 3 хода для 2 дисков.
hanoi(n - 1, a, c, b) расчищает путь на запасной c. print переносит самый большой диск. hanoi(n - 1, c, b, a) переносит меньшую башню с запасного на цель b.
Пусть твоя рекурсия сыграет 5 дисков.
Твой код печатает каждый ход. Стержни следуют за ним.
Как растут ходы вместе с башней?
Дойди до 10 дисков.
У монахов 64 диска, и они делают один ход в секунду. Сколько это займёт?
2^64 - 1 секунд. Оцени это в годах, потом «Проверить». Засчитывается, если ошибка не больше чем в 3 раза в любую сторону.
2^64 - 1 это около 1,8 x 10^19 секунд. Раздели примерно на 3,16 x 10^7 секунд в году: около 5,8 x 10^11, то есть 585 миллиардов лет.
Скоростной раунд: куда сначала идёт самый маленький диск?
Башни от 1 до 6 дисков, всегда с A на C. Нажми на стержень для самого первого хода.
Предыдущий урок: Запоминаем ответы: мемоизация · Следующий урок: Рисуем фракталы · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
