Ханойские башни

Ханойские башни
Модель Ханойской башни с восемью дисками

Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Содержание

История создания головоломки

Эту известную игру придумал французский математик Эдуард Люка, в 1883 году[1] её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Коллеж Ли-Су-Стьян (Li-Sou-Stian)»[2] но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа — не более чем анаграмма фамилии изобретателя игры — профессора Люка (Lucas) из коллежа Сен-Луи (Saint Louis).

Алгоритм решения

Ход решения головоломки с четыремя дисками.

Начнем с самого маленького кольца и переложим его на любую отметку. В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании. Затем произведем единственно возможное перемещение оставшихся колец, после чего снова переложим самое маленькое кольцо и т. д. (Интересно заметить, что, перенумеровав «кольца» по порядку, мы добьемся неожиданного эффекта: четные кольца будут перемещаться из одной вершины треугольника в другую в одном направлении, а не­четные — в противоположном направлении.)

Легенды

В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света. Количество перекладываний в зависимости от количества колец вычисляется по формуле 2n − 1. Для 64-х колец это 18 446 744 073 709 551 615 перекладываний, и, если учесть скорость одно перекладывание в секунду, получится около 584 942 417 355 лет, то есть апокалипсис наступит нескоро.

Применение кода Грея для решения

Примечания

  1. ↑ Мартин Гарднер, Математические головоломки и развлечения
  2. ↑ Мартин Гарднер, Математические головоломки и развлечения



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Ханойские башни" в других словарях:

  • Ханойская башня — Модель Ханойской башни с восемью дисками Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются …   Википедия

  • Рекурсивный алгоритм — Рекурсия  метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или …   Википедия

  • У попа была собака — Рекурсия  метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или …   Википедия

  • Парадигма — (Paradigm) Определение парадигмы, история возникновения парадигмы Информация об определении парадигмы, история возникновения парадигмы Содержание Содержание История возникновения Частные случаи (лингвистика) Управленческая парадигма Парадигма… …   Энциклопедия инвестора

  • Неопределённое поведение — Не следует путать с неуточняемым поведением. Неопределённое поведение (англ. undefined behaviour)  свойство некоторых языков программирования (наиболее заметно в Си), программных библиотек и аппаратного обеспечения в определённых… …   Википедия

  • Visual Prolog — Тип Язык программирования Разработчик Prolog Development Center Операционная система MS Windows 2000/XP/Vista/Seven Последняя версия 7.3 (13 мая 2010) …   Википедия

  • Неопределенное поведение — Неопределённое поведение (англ. Undefined behaviour)  свойство некоторых языков программирования (наиболее заметно в C) в определённых маргинальных ситуациях выдавать результат, зависящий от реализации компилятора. Другими словами, спецификация… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»