Что такое ханойская башня

Ханойская башня: красивая легенда и элегантный алгоритм. Как решить?

В XIX веке была очень популярна одна головоломка, которую придумал математик Франсуа Эдуард Анатоль Люка (François Édouard Anatole Lucas) из колледжа Сен-Луи (Saint Louis). Она была выполнена в форме игрушки и продавалась в качестве развлечения. И носила странное название «Профессор Claus из колледжа Li-Sou-Stian». Пытливые умы еще до решения задачи разгадали первую загадку еще в названии — это анаграмма, скрывающая настоящую фамилию создателя игры и названия колледжа: Lucas и Saint Louis.

Легенда

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

Легенда заключалась в том, что в городе Ханой расположен храм бога Брамы. В нем находится плита с тремя стержнями из алмаза. При сотворении мира Брама нанизал на один стержень 64 золотых диска в форме пирамиды, и назвал это башней Брамы. Внизу лежал самый большой, а каждый следующий был все меньше и меньше. Если перенести все диски на другой стержень, соблюдая определенные условия, храм обратится в пыль, а мир — в небытие. А теперь, уважаемые знатоки, внимание, вопрос: через какое время наступит конец света, если жрецы будут беспрерывно переносить диски, скажем, по 1 в секунду?

Алгоритм

Эта задача — не просто забавная игра, а проверка интеллекта и функции мышления. Для ее решения есть несколько способов, мы рассмотрим алгоритм из 5 колец. Поняв его правила, мы сможем применить его к любому количеству колец и выяснить, когда же придет апокалипсис. Итак, у нас 3 правила:

У нас есть 3 стержня слева направо — A, B и C. На стержне A расположены кольца снизу вверх 1, 2, 3, 4 и 5. Простота решения заключается в том, чтобы перенести на соседний стержень всю пирамидку, кроме самого нижнего кольца:

Здесь у нас оказывается пирамидка, кроме самого большого кольца, на втором стержне. Далее нам необходимо перенести основание — 1 на самый дальний стержень — C, и далее так же за 15 ходов перенести остальную пирамидку на этот стержень.

Таким образом, количество перемещений равно 2 в степени Х минус 1, где Х — число колец. Проверяем: 2 в пятой степени = 32, 32 – 1 = 31 ход! Получается, монахам в храме Брамы нужно сделать 2 в 64-й степени перекладываний и минус одно: 18 446 744 073 709 551 615. Если взять один ход за одну секунду, то это 18 квинтиллионов 446 квадриллионов 744 триллиона 73 миллиарда 709 миллионов 551 тысяча 615 секунд или 584,9 миллиарда лет.

Чтобы щелкать такие задачки как орешки, не забывайте регулярно тренировать мозг. Постоянные нагрузки держат его в тонусе, и это помогает не только решать головоломки, но и быть продуктивнее в любых делах!

Источник

Ханойские башни — теоретическое решение без рекурсии

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

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

Классическое решение данной задачи с тремя стержнями предполагает, что для заданного количества колец n количество перекладываний вычисляется по формуле
.

Дополнительную привлекательность данной задаче придаёт и сопровождающая её легенда:

В Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

Между делом новичку предлагается оценить сложность данного решения, чтобы впечатлить результатом: число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.

Суть решения сводится к пониманию того, что для перемещения текущего диска необходимо решить задачу по переносу всех предыдущих дисков на свободный стержень, перемещению требуемого диска и последующему обратному перемещению всех предыдущих дисков меньшего размера на нужный стержень. Таким образом, решение задачи сводится к предыдущим решениям, что и иллюстрирует механизм рекурсии.

Александр Бусаров MrShoor написал очень информативный пост, отлично дополняющий соответствующую статью в Википедии, с очень подробным программным кодом, рекомендую ознакомиться с его реализацией рекурсии.

В том же посте имеется описание фрактальной природы алгоритма. Я попытаюсь продолжить это направление, раскрыв применение кода Грея для данной конкретной задачи.

Приведу цитату из соответствующей статьи в Википедии:

Коды Грея применяются в решении задачи о Ханойских башнях. Пусть N — количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i+1)). Поставим в соответствие каждому I-ому биту текущего кода Грея I-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита I как перемещение I-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t->.

Оптимальное решение задачи сводится к определению положения дисков после очередного хода. В самом начале (при нулевом ходе) все диски находятся на одном и том же стартовом стержне f. Нумерация весов дисков осуществляется с номера 1 по возрастанию. Требуется описать положение дисков на ходе с номером m.

Очевидно, что при оптимальном решении после хода m количество перемещаемых дисков n будет не более

(1).
Остальные диски большего размера можно не брать в расчёт, что очень удобно при более общем предположении о бесконечном количестве дисков в начальной задаче с тремя стержнями.

Далее, определившись с количеством перемещенных дисков, определимся с их положением.

Ввиду фрактальности решения, которое описывалось в упомянутых выше источниках, становится очевидным, что благодаря «вложенности» решений друг в друга просматривается связь между двоичным кодом номера хода и номером перемещаемого диска.

В частности, во время данного хода перемещается тот диск, чей «вес» i коррелирует с максимальной степенью двойки в двоичном разложении номера m текущего хода минус единицу:
(2).

В той же нотации Pascal/Delphi, которую использует MrShoor в своем коде, это может быть записано следующим образом:

Таким образом, для каждого из дисков с весом i мы можем определить тот ход j, на котором диск данного веса был перемещен последний раз:

.

Код для определения номера хода num_move последнего перемещения диска с весом i может выглядеть подобным образом (с условием включения модуля Math):

Стоит обратить внимание на тот факт, что попутно в переменной q_move получено количество перемещений диска с весом i с начала игры.

Итак, в промежуточном итоге, мы знаем, сколько раз каждый диск был перемещен в течение игры после каждого хода. Теперь определимся с тем, куда перемещался каждый из дисков.

Как отмечено в Википедии, перемещение верхнего диска циклично и, при выборе определенного стержня назначения t, если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t->…

Вспоминая о фрактальности, можно заметить, что если отбросить верхнюю часть предшествующих дисков, то текущий диск также совершает подобное циклическое движение во время своих собственных ходов. Учитывая этот факт, становится очевидным, что в зависимости от четности номера диска, цикл перемещения нечетного диска совпадает с циклом перемещения первого диска, а цикл перемещения четных дисков разнится очередностью стержней t и r.
В частности, зная количество перемещения q_move и четность номера текущего диска, можно простым делением на 3 по остатку определить последний стержень, куда был перемещен данный диск.

Следовательно, имея на входе общее количество дисков N, выбранный стержень назначения t и номер текущего хода m, можно восстановить положение всех дисков при оптимальном решении без обращения к рекурсивным алгоритмам.

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

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

Стиль и язык немного суховаты и годятся скорее для академических работ, потому прошу не судить особо строго, особенно с учетом попытки выправить карму и выбраться из минуса. Всем всего наилучшего и светлого, с Новым 2017 Годом: успехов и удач во всем хорошем!

UPD: Спасибо всем за комментарии, замечания и подсказки. Пример работающего по приведенному выше алгоритму скрипта доступен по этой ссылке. Использовалась библиотека GMP для обеспечения работы с большими числами.

Источник

Сортировка «Ханойская башня»

Ханойские башни
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.)

Данный пост посвящается памяти истинного гуру программирования Андрея Mrrl Астрелина, который когда-то мне просто и доходчиво объяснил этот алгоритм. Псевдокод ниже по тексту — его авторства.

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

Кроме того, размеры дисков предполагаются уникальными. Не будем цепляться за это ограничение и разрешим повторы.

Если позволить себе только эти две вольности, то начальные условия головоломки можно интерпретировать как массив (диски — это числа), а задача сводится к тому, что данный массив требуется отсортировать.

Остальные условия мы (почти) не меняем:

… и превратить его в сортировку!

На самом деле, от того что мы разрешили начальную неупорядоченность и повторы для размеров дисков — от этого принципиально не поменялось ничего. По большому счёту задача решаема всё тем же классическим рекурсивным способом. Самое главное что нужно понять — все перемещения дисков разделяются на несколько этапов, каждый из которых — это классичекий «ханой» в миниатюре.

То есть мы на каждом этапе рассматриваем не все имеющиеся диски, а только совокупность тех из них, которые удовлетворяют старым условиям. Отсортировав по классике это небольшое множество мы приблизим общее состояние системы к классической головоломке. Тогда мы опять берём то множество дисков, которое соответствует классике и применяем известный алгоритм вновь. И это множество будет бо́льшим, чем на предыдущем шаге! И так повторяем до тех пор, пока все диски на всех шестах вдруг не станут отличаться от классического состояния.

Нарушенная изначально система (тем, что на входе диски не упорядочены) самовосстанавливается с каждой итерацией.

Что касается разрешения повторов, то это вообще не имеет никакого значения. Потому что подряд идущие одинаковые диски мы просто перемещаем как один диск.

Алгоритм

Назовем столбики A, B, C (A в начале непустой).

А->С() — переложить один диск с А на С.
top(A), top(С) — размер верхнего диска А или С. Если столбик пуст, то этот размер = MaxInt.
В->С(К) — переложить с В на С все диски, размер которых меньше К (мы это можем сделать, если верхние диски А и С не меньше К).
swap() — переставить столбики В и С (или переименовать их — нам ведь все равно, где окажутся диски).
while(A) — цикл пока А не пуст.

Тогда работает такой алгоритм:

Сложность

В худшем случае сортировка стремится к сложности по времени для классического алгоритма, который хоть прост и изящен, но при этом максимально неэффективен. Насчёт лучшей и средней предположить затрудняюсь.

Насчёт памяти можно сказать, что если используется рекурсия, то и затраты будут соответствующие.

Реализация

Свой вариант на Python пока не написал (сделаю это позже). Однако ниже в разделе «Ссылки» накидал несколько ссылок, по которым можно посмотреть имплементации на различных языках. Особенно интересен вариант на Джаве. Автор не стал брать за основу общеизвестный рекурсивный способ для решения головоломки, а построил кратчайшее дерево путей. Предположительно, это является самым эффективным решением, если писать сортировку в стиле «Ханойской башни».

Характеристики алгоритма

Ссылки

Tower of Hanoi / Ханойская башня

Статьи серии:

Также есть ограничение на размер массива — не более 20-ти элементов. Сделано это сугубо в Ваших же интересах — если возьмёте слишком большой массив, то, может так статься, что сортировать его придётся до глубокой старости.

Статья написана при поддержке компании EDISON Software, которая профессионально разрабатывает умное городское освещение и поддерживает сайты на питоне

Источник

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

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

Содержание

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

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

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

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

Легенды

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

Примечания

Полезное

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

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

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

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

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

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

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

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

Источник

Ханойская башня

Постоянный интерес к старым задачам обусловлен множеством причин. Это и красивые легенды, обрамляющие условие, и изящные решения, и интересные расширения, вытекающие из исходных ограничений. В «Сборнике задач по курсу информатики» к учебникам за 10-11 класс автора Белоусова, Веприк представлены более 600 задач разного уровня сложности для абитуриентов и школьников. Задача о Ханойских башнях, представленная в задачнике, сопровождается одной из самых интригующих легенд о конце света. Дополнительный колорит ей придает блеск золотых дисков и алмазных стержней

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

Правила игры «Ханойская башня» состоят в следующем:

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

При перестановке должны соблюдаться некоторые правила.

1) кружки переставляются с одного стержня на другой, при этом их укладывают друг на друга, так что получаются маленькие башни. Нельзя откладывать кружки в сторону или ставить один кружок вместо другого;

2) при каждом ходе двигается только один кружок. Нельзя переносить несколько кружков одновременно. Например, запрещено брать по кружку в каждую руку;

3) можно брать кружок лишь с вершины какой–нибудь башни и класть его только на вершину другой башни. Нельзя брать кружок из середины башни или вставлять его в середину другой башни;

4) запрещено класть больший кружок на меньший.

На рисунке изображены несколько разрешенных и несколько запрещенных ходов.

Так можно: Так нельзя:

Эту романтическую легенду, придумал в 1883 году французский математик ЭДУАРД ЛЮКА.

Франсуа Эдуард Анатоль Люка (François Édouard Anatole Lucas; 4 апреля 1842, Амьен- 8 октября 1891) французский математик, профессор. Работал в лицее Лунле-Гран в Париже. Важнейшие работы Люка относятся к теории чисел и неопределенному анализу. Считал, что с помощью машин или каких-либо приспособлений сложение удобнее производить в двоичной системе, чем в десятичной.

• Описал свойства последовательностей, удовлетворяющих однородным линейным рекуррентным уравнениям второго порядка, частным случаем которых являются числа Фибоначчи. Такие последовательности теперь называются последовательностями Люка.

• Придумал ряд интересных задач, в том числе известную головоломку Ханойская башня.

Где-то в непроходимых джунглях, недалеко от города Ханоя, есть монастырь бога Брахмы. В начале времен, когда Брама создавал Мир, он воздвиг в этом монастыре три высоких алмазных стержня и на один из них возложил 64 диска, сделанных из чистого золота. Он приказал монахам перенести эту башню на другой стержень (в соответствии с правилами, разумеется) С этого времени монахи работают день и ночь. Когда они закончат свой труд- наступит конец света.

III. Решение головоломки:

А) Формула зависимости ходов от числа кружков башни

Если составить таблицу зависимости ходов от числа кружков игры, то результат будет очевиден:

Число кружков : Оптимальное число ходов:

Получилась числовая последовательность: 1,3,7,15,31,.

Первое решение. Второе решение.

Вопрос: «Как узнать очередное число последовательности, зная предыдущее?» Выпишем степени числа 2

Если умножить предыдущее число на 2 и прибавить один, получим требуемое. 21 =2 ; 22=4; 23=8 ; 24=16; 25=32

7= 2*3+1 Вычитаем единицу из этих чисел, получаем нашу последовательность:

B) Решение задачи на языке программирования.

Как уже говорилось во введении: Ханойская башня является одной из популярных головоломок XIX века.

Алгоритм решения задачи:

1. Если n>0, остановиться

2. Переместить верхние n-1 дисков со стержня А на стержень В, используя стержень С как вспомогательный.

3. Переместить оставшийся диск со стержня А на стержень С

4. Переместить n-1 дисков со стержня В на стержень С, используя стержень А как вспомогательный.

Нетрудно заметить, что этот алгоритм рекурсивный. Действительно, на шаге 2 и шаге 4 алгоритма требуется решить задачу, аналогичную первоначальной, только для меньшего числа дисков.

Рекурсивный алгоритм- это алгоритм, использующий в качестве вспомогательного самого себя.

Листинг программы на языке программирования Turbo Pascal.

PROGRAM hanoy; typebachnia =char; var a,b,c: bachnia; k, kol: integer;

<процедура, описывающая рекурсивный алгоритм>procedure H (n: integer; a,b,c :bachnia); begin if n>0 then begin

<основная программа>begin write (‘ввести количество кружков =’); readln (k); a:=’A’; b:=’B’ ; c:=’C’;

H (k,a,b,c); writeln (‘количество шагов=’, kol); end.

Результат тестирования программы

При количестве кружков К=3

КОЛИЧЕСТВО ШАГОВ = 7

КОЛИЧЕСТВО ШАГОВ = 15

Листинг программы на языке программирования QBasic.

REM ОСНОВНАЯ ПРОГРАММА

PRINT “количество шагов=”; kol

REM РЕКУРСИВНАЯ ПОДПРОГРАММА

1: IF N=0 THEN RETURN

PRINT “переместить диск “;N ; A; “->”;C

C) Время от «начала» и до «конца» света.

Интересно подсчитать, за сколько времени монахи монастыря Брамы (см. легенду) закончат работу и наступит «конец» света.

Предположим, что монахам требуется 1 секунда на выполнение одного хода игры. Оценим приблизительно, сколько времени им понадобиться для выполнения всего задания, или можно сказать и так: Сколько времени должно пройти от «начала» до «конца» света?

264 = 24 * 260 = 16* 260 ( 16 * (210 ) 6 ( 16*(10 3)6 ( 16 *1018 т. к. 210 = 1024 ( 1000 = 10 3 получили, что число ходов приблизительно равно шестнадцати квинтильонам.

В одних сутках 24 часа, в часе 60*60=3600 секунд.

Значит, в сутках 24* 3600= 86 400 секунд

В году- в 365 больше, т. е. приблизительно 32 миллиона секунд, или 32 * 106 секунд

Чтобы узнать, сколько лет необходимо монахам, нужно разделить одно из полученных нами чисел на другое:

(16 *1018 ) / (32 * 106 ) = 0,5 * 10 12 = 500 000 000 000 лет

Так что если вас беспокоит наступающий «конец» света, то можно не волноваться, пятьсот миллиардов лет- срок достаточно большой.

D) Решение задачи на суперкомпьютере.

Представим себе вместо монахов будущий суперкомпьютер: Пусть он совершает в секунду 1 миллиард операций. Сколько времени понадобиться компьютеру переложить башню из 64 кружков?

Существует одна притча:

-Мир давно уже должен быть погибнуть!

-Почему ты так думаешь?

-Знаешь, существует древнее предание, по которому стоит перенести всего лишь 64 кружка и наступит конец света

— Всего лишь 64, стоит задуматься, что если один ход проделывать за 1 секунду, то в час можно сделать 3 600 перенесений

— А в сутки- около ста тысяч. В десять дней- миллион ходов. Миллионом же ходов можно, я уверен, перенести хоть тысячу кружков.

— Ошибаешься. Чтобы перенести всего 64 кружка, нужно уже круглым счетом 500 миллиардов лет!

— Да, это очень большой срок»

Источник