Ханойская башня
Ханойская башня — классическая математическая головоломка. Три стержня, стопка дисков разного размера и два строгих правила: перекладывайте по одному диску и никогда не кладите больший диск на меньший.
Три стержня и конус из дисков
На доске три стержня. Все диски разного размера и надеваются на стержни. В начале весь набор находится на одном стержне, упорядоченный по размеру: самый большой внизу, самый маленький наверху, так что стопка образует конус. Цель — перенести всю башню на другой стержень.
Три правила
1. Перекладывайте только один диск за раз. 2. Ход — это взять верхний диск из стопки и положить его на другую стопку или на пустой стержень. 3. Больший диск никогда не может лежать на меньшем. Эти три правила и есть вся игра. При них каждое допустимое положение — это способ распределить диски по стержням так, чтобы на каждом стержне сохранялся порядок.
Кратчайшее решение — 2ⁿ − 1
Наименьшее число ходов, решающее башню из n дисков, равно 2ⁿ − 1. Один диск требует 1 хода. Два диска — 3. Три — 7, четыре — 15, пять — 31. Каждый новый диск удваивает предыдущее решение и добавляет один ход, переносящий самый большой диск: если n − 1 дискам нужно T ходов, то n дискам нужно 2T + 1. Это рекуррентное соотношение даёт ровно 2ⁿ − 1. Восемь дисков, самая высокая башня в приложении PictorX, требуют 255 ходов. Более короткого допустимого пути нет.
Как работает рекурсия
Чтобы перенести n дисков с начального стержня на целевой, используя оставшийся стержень как вспомогательный: 1. Перенесите верхние n − 1 дисков с начального стержня на вспомогательный. 2. Перенесите самый большой диск с начального стержня прямо на целевой. 3. Перенесите n − 1 дисков со вспомогательного стержня на целевой, поверх самого большого диска. Шаг 2 допустим, потому что самый большой диск может лежать на любом стержне. Шаги 1 и 3 — та же головоломка, на один диск меньше. Рекурсия заканчивается на одном диске, который перекладывается один раз. Если её развернуть, получатся 2ⁿ − 1 ходов, и ни один шаг не кладёт больший диск на меньший.
Легенда о 64 золотых дисках
Французский математик Эдуард Люка представил головоломку в 1883 году. Вместе с ней он рассказал легенду об индийском храме в Каши Вишванатхе, где жрецы по тем же правилам перекладывают стопку из 64 золотых дисков. Когда будет сделан последний ход, гласит легенда, наступит конец света. Шестьдесят четыре диска требуют 2⁶⁴ − 1 ходов: 18 446 744 073 709 551 615. При одном безошибочном ходе в секунду, днём и ночью, это около 585 миллиардов лет. Жрецы не закончат.
Играйте в PictorX
Откройте «Ханойскую башню» — на начальном стержне уже стоит башня из четырёх дисков. Минимум — пятнадцать ходов. Перетащите верхний диск на другой стержень или щёлкните стержень, а затем нужный. Клавиши 1, 2 и 3 делают то же самое. Больший диск на меньшем не допускается. «Диски» меняются от 1 до 8, так что можно сверить 1, 3, 7, 15, 31, 63, 127 и 255 с формулой. «Шаг» проигрывает один ход кратчайшего решения. «Решить» проигрывает остальное. «Смотреть 3 диска» показывает рекурсивную стратегию в движении. «Отменить» и «Повторить» проводят по вашим ходам. Сохраните PNG или откройте доску в редакторе PictorX.
Часто задаваемые вопросы
Каковы правила Ханойской башни?
Перекладывайте по одному диску. Возьмите верхний диск со стержня и положите его на другой стержень. Никогда не кладите больший диск на меньший. Вся башня начинает на одном стержне и должна оказаться на другом.
Сколько ходов занимает кратчайшее решение?
2ⁿ − 1. Один диск — 1 ход, два диска — 3, три — 7, четыре — 15, пять — 31. Каждый добавленный диск удваивает предыдущее решение и добавляет один ход.
Кто придумал Ханойскую башню?
Французский математик Эдуард Люка представил её в 1883 году. История о жрецах и 64 золотых дисках в Каши Вишванатхе — легенда, которую он связал с головоломкой.
Сколько времени заняли бы 64 диска?
2⁶⁴ − 1 ходов, то есть 18 446 744 073 709 551 615. При одном ходе в секунду это около 585 миллиардов лет.
Сопутствующие инструменты
Ханойская башня
Перенесите в браузере башню из дисков между тремя стержнями. По одному диску, никогда больший на меньший. Кратчайшее решение — 2ⁿ − 1 ходов.
Игла Бюффона
Бросайте иглы на разлинованный пол прямо в браузере. Считайте пересечения и смотрите, как опыт Бюффона 1777 года оценивает π.
Игла Бюффона
Задача Бюффона об игле (1777): почему игла, брошенная на параллельные линии, оценивает π, как вероятность 2l/(πd) для короткой иглы получается из площади под синусоидой и почему опыт сходится медленно.
Круги умножения
Соедините каждое число на круге с его кратным. Нарисуйте таблицу умножения, кардиоиду или фигуру из нити на бумаге, мелом или на дереве.
Гипотеза Коллатца
Исследуйте задачу Коллатца 3n+1 в браузере. Проходите последовательности «градин», выращивайте геометрическое дерево Коллатца и приближайте непрерывный фрактал Коллатца.
Муравей Лэнгтона
Запустите муравья Лэнгтона в браузере. Посмотрите на симметрию, хаос и шоссе с циклом в 104 шага, а затем попробуйте многоцветные правила, нескольких муравьёв, шестиугольную сетку и турмитов.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Играть в Ханойскую башню