Ханойская башня
Три стержня и конус из дисков, самый большой внизу. Перенесите всю башню на правый стержень. За раз можно перекладывать только один диск, и больший диск никогда не может лежать на меньшем. Кратчайшее решение занимает 2ⁿ − 1 ходов: 1, 3, 7, 15, 31 и так далее. Перекладывайте по одному диску на больший диск или на пустой стержень. Вся башня должна оказаться на правом стержне. Кратчайшее решение занимает 2ⁿ − 1 ходов. Перетащите диск или щёлкните один стержень, а затем другой.
Как это работает
- Откройте эту страницу. На начальном стержне лежат четыре диска. Минимум — пятнадцать ходов.
- Перетащите верхний диск на другой стержень или щёлкните стержень, а затем нужный. Больший диск на меньшем не допускается.
- Нажмите «Решить», чтобы посмотреть кратчайшее решение, или пройдите его кнопкой «Шаг». Затем сохраните PNG.
Один диск, и никогда больший на меньший
Ход — это взять верхний диск с одного стержня и положить его на другой стержень или на пустой стержень. Других ходов нет. Диск, который вы кладёте, должен быть меньше того, на который он ложится. При этих правилах диски на каждом стержне всегда остаются упорядоченными, самый большой внизу.
2ⁿ − 1 ходов, и не меньше
Чтобы перенести n дисков, сначала уберите с дороги n − 1 дисков над самым большим, один раз переложите самый большой диск, а затем перенесите n − 1 дисков на него. Если n − 1 дискам нужно T ходов, то n дискам нужно 2T + 1. Это и есть 2ⁿ − 1: 1, 3, 7, 15, 31. Восемь дисков, самая высокая башня здесь, требуют 255 ходов.
Та же головоломка, на один диск меньше
Перенесите верхние n − 1 дисков на вспомогательный стержень. Перенесите самый большой диск на цель. Перенесите n − 1 дисков со вспомогательного стержня на цель. Каждая из этих меньших задач — снова та же головоломка. «Шаг» и «Решить» проигрывают кратчайший путь. Из идеальной башни это и есть эта рекурсия. Из перемешанной позиции это всё равно кратчайший путь, найденный перебором допустимых положений.
Часто задаваемые вопросы
Каковы правила Ханойской башни?
Перекладывайте по одному диску. Возьмите верхний диск со стержня и положите его на другой стержень. Никогда не кладите больший диск на меньший.
Сколько ходов занимает кратчайшее решение?
2ⁿ − 1. Один диск — 1 ход, два диска — 3, три — 7, четыре — 15, пять — 31.
Кто придумал Ханойскую башню?
Эдуард Люка представил головоломку в 1883 году. История о жрецах, перекладывающих 64 золотых диска, — это легенда, которую он рассказал вместе с ней.
Можно посмотреть решение?
Да. «Шаг» проигрывает один ход кратчайшего решения. «Решить» проигрывает остальное. «Смотреть 3 диска» показывает классическую рекурсивную стратегию с самого начала.
Сопутствующие инструменты
Ханойская башня
Ханойская башня: три стержня, по одному диску, и никогда больший на меньший. Кратчайшее решение — 2ⁿ−1 ходов. Эдуард Люка представил головоломку в 1883 году.
Ход коня
Проведите шахматного коня по всем полям доски, побывав на каждом ровно один раз. Играйте сами с подсказками Варнсдорфа или смотрите, как «Решить» завершает открытый или замкнутый маршрут. Сохраните путь в PNG.
Восемь ферзей
Расставьте восемь ферзей на шахматной доске так, чтобы ни один не бил другого. Попробуйте сами, посмотрите, как поиск с возвратом шаг за шагом находит решение, и переберите все 92 решения.
Пятнашки
Играйте в классические пятнашки в браузере: деревянные фишки на поле 3×3, 4×4 или 5×5. Перемешивайте, сдвигайте целые ряды за раз, попробуйте невозможную позицию 14-15 Сэма Лойда или посмотрите, как «Решить» доводит игру до конца.
Игла Бюффона
Бросайте иглы на разлинованный пол прямо в браузере. Считайте пересечения и смотрите, как опыт Бюффона 1777 года оценивает π.
Круги умножения
Соедините каждое число на круге с его кратным. Нарисуйте таблицу умножения, кардиоиду или фигуру из нити на бумаге, мелом или на дереве.
Гипотеза Коллатца
Исследуйте задачу Коллатца 3n+1 в браузере. Проходите последовательности «градин», выращивайте геометрическое дерево Коллатца и приближайте непрерывный фрактал Коллатца.
Муравей Лэнгтона
Запустите муравья Лэнгтона в браузере. Посмотрите на симметрию, хаос и шоссе с циклом в 104 шага, а затем попробуйте многоцветные правила, нескольких муравьёв, шестиугольную сетку и турмитов.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор