Есть три стержня A, B, и C. На стержень A надето N дисков, наверху самый маленький, каждый следующий диск больше предыдущего, а внизу самый большой. На другие стержни дисков не надето.
Hеобходимо перенести диски со стержня A на стержень C, пользуясь стержнем B, как вспомогательным, так, чтобы диски на стержне C располагались в том же порядке, в каком они располагаются на диске A перед перемещением.
При перемещении никогда нельзя класть больший диск на меньший.
Решение
Рекурсивный метод
Для того, чтобы переложить всю пирамиду, надо сначала переложить все, что выше самого большого диска, с первого на вспомогательный стержень, потом переложить это самое большой диск с первого на третий стержень, а потом переложить оставшуюся пирамиду со второго на третий стержень, пользуясь первым стержнем, как вспомогательным.
Всего получается 2 N-1 перекладываний.
Нерекурсивный метод
Стержню, на котором диски находятся в начале, дадим номер 0; стержню, на который их надо перенести — номер 2; и, соответственно, оставшемуся стержню — номер 1.
Пусть всего дисков N. Занумеруем диски в порядке увеличения радиуса числами 0,1,2. N-1.
Как известно, задача решается за 2 N-1 ходов. Занумеруем ходы числами 1,2. 2 N-1 .
Любое натуральное число i единственным образом представимо в виде i=(2t+1)*2 k , где t и k — целые (т.е. как произведение нечетного числа на некоторую степень двойки). Так вот, на i-ом ходе переносится диск номер k со стержня номер ((-1) N-k *t mod 3) на стержень номер ((-1) N-k *(t+1) mod 3).
если пpедставить что стержни, на котоpые одеваются диски, pасположены в yглах pавностоpоннего тpеyгольника, то самый маленький диск каждым нечетным ходом движется по (или пpотив, это от пеpвоначального кол-ва дисков зависит) часовой стpелки.
Все четные ходы опpеделяются однозначно. Какой диск меньше — тот и перекладывать (иначе противоречит условию). Т.к. тpогать диск 0 нельзя и класть больший на меньший тоже нельзя.
Отметим две закономерности:
- Hа каждом нечетном ходy происходит перенос наименьшего диска.
- Hаименьший диск всегда переносится циклически: либо A-B-C-A-B-C-. (в слyчае четного количества дисков), либо A-C-B-A-C-B-. (в слyчае нечетного).
А посемy полyчаем алгоритм:
1. Определяем число дисков, откyда находим как бyдет перемещаться наименьший диск (данный шаг делается в начале, притом один раз).
2. Смотрим номер хода: если нечетный — переносим наименьший диск в направлении, определенном в п.1. если четный — то возможный ход один единственный — берем наименьший из двyх верхних дисков и переносим его.
Можно написать немного по другому:
Для N от 1 до 2 k-1 выполнять
1. В двоичном представлении N найти самый правый ненулевой разряд. Обозначим номер этого разряда t.
2. Обозначим номер стержня, на котором находится диск t через i. Переместить диск t со стержня i на стержень (i+(-1) t ) mod 3.
Задача Ханойских башен — одна из самых первых задач, которые предлагаются начинающим программистам, в основном, чтобы проиллюстрировать концепцию рекурсивных решений. В этой статье приводится метод, который позволяет теоретическим путем, без рекурсии, указывать оптимальное решение для текущего хода.
«Ханойская башня» является одной из популярных головоломок 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 для обеспечения работы с большими числами.
Вы можете помочь и перевести немного средств на развитие сайта
Задача
Написать программу решения задачи о ханойской башне.
Решение
В одной из древних легенд говорится следующее. «В храме Бенареса находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разного диаметра из чистого золота так, что наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это – башня Брамы. Работая день и ночь, жрецы переносят диски с одного стержня на другой, следуя законам Брамы:
1. диски можно перемещать с одного стержня на другой только по одному;
2. нельзя класть больший диск на меньший.
Когда все 64 диска будут перенесены с одного стержня на другой, и башня, и храмы, и жрецы-брамины превратятся в прах, и наступит конец света».
Эта древняя легенда породила задачу о Ханойской башне: переместить m дисков с одного из трех стержней на другой, соблюдая «законы Брамы».
Назовем стержни левым (left), средним (middle) и правым (right). Задача состоит в переносеm дисков с левого стержня на правый.
Задача может быть решена одним перемещением только для одного (m = 1) диска. В общем случае потребуется 2m-1 перемещений.
Построим рекурсивное решение задачи, состоящее из трех этапов:
a) перенести башню, состоящую из m – 1 диска, с левого стержня на средний;
b) перенести один оставшийся диск с левого стержня на правый;
c) перенести башню, состоящую из m – 1 диска, со среднего стержня на правый.
Таким образом, задача о перемещении m дисков сводится к задаче о перемещении m – 1диска. Обращаясь опять к этому же алгоритму, сведем задачу к перемещению m – 2 дисков. Продолжая этот процесс, получим, в конце концов, задачу о перемещении одного диска. Эта задача решается за один ход. Таким образом, в процессе решения возникают промежуточные задачи: переместить башню из нескольких n дисков с одного стержня на другой.
Обозначим тот стержень, с которого следует снять диски, через s1, на который надеть – через sk, а вспомогательный стержень через sw.
Оформим алгоритм решения задачи о переносе башни из n дисков с s1 на sk в виде процедуры move с 4-мя параметрами: n, s1, sw, sk; алгоритм для n = 1 выделим в отдельную процедуру step, которая перемещает один диск со стержня s1 на sk.
