Ханойская башня алгоритм рекурсивный

Ханойская башня алгоритм рекурсивный

Есть три стержня 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 нельзя и класть больший на меньший тоже нельзя.

Отметим две закономерности:

  1. Hа каждом нечетном ходy происходит перенос наименьшего диска.
  2. 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.

Задача

Написать программу решения задачи о ханойской башне.

Решение

В одной из древних легенд говорится следующее. «В храме Бенареса находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 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.

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

Я понимаю базовый случай и концепцию разбиения проблемы на более мелкие части, пока вы не сможете переместить один диск. Однако я не могу понять, как два рекурсивных вызова в неосновном случае работают вместе. Может, кто-нибудь мне поможет? Спасибо.

23 ответов

на самом деле раздел, откуда вы взяли этот код представлено объяснение, а также:

для перемещения N дисков из колышка A в колышек C:

  1. переместить N-1 дисков из A В B. Это оставляет диск #N один на привязке a
  2. переместить диск #n из A в C
  3. переместите N-1 дисков из B В C, чтобы они сидели на диске #n

довольно ясно, что сначала вам нужно удалить n — 1 диски, чтобы получить доступ к nго. И что вы должны переместить их сначала на другой колышек, чем там, где вы хотите, чтобы полная башня появилась.

код в вашем посте имеет три аргумента, кроме количества дисков: a источник peg, a назначения колышек и временное peg на котором диски можно хранить между (где каждый диск с размером n — 1 подходит).

рекурсия происходит на самом деле дважды, там, один раз перед writeln , после. Один перед writeln будет двигаться n — 1 диски на временную привязку, используя привязку назначения в качестве временного хранилища (аргументы в рекурсивном вызове находятся в другом порядке). После этого оставшийся диск будет перемещен на привязку назначения, а затем вторая рекурсия принудит перемещение всей башни, переместив n — 1 башня от шпенька temp к шпеньку назначения, над диском n.

год назад у меня был курс функционального программирования и нарисовать эту иллюстрацию для алгоритма. надеюсь, это поможет!

Читайте также:  Как поделиться экраном в скайпе

задача о 3 кольцах была разбита на 2 задачи о 2 кольцах (1.x и 3.x)

существует хорошее объяснение рекурсивной реализации Ханоя в http://www.cs.cmu.edu /

резюме, если вы хотите переместить нижнюю пластину с палки A на палку B, вам сначала нужно переместить все меньшие пластины поверх нее от A до C. Второй рекурсивный вызов затем переместить пластины, которые вы переместили в C обратно на B после того, как ваш базовый корпус переместил одну большую пластину из A В B.

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

базовый вариант: ваша башня имеет размер 1. Таким образом, вы можете сделать это за один ход, от источника непосредственно к dest.

рекурсивный случай: ваша башня имеет размер n > 1. Таким образом, вы перемещаете верхнюю башню размера n-1 на дополнительный колышек (by), перемещаете нижнюю "башню" размера 1 на целевой колышек и перемещаете верхнюю башню из by в dest.

так с простым случаем, вы есть башня высотой 2:

первый шаг: переместите верхнюю башню 2-1 (=1) на дополнительный колышек (средний, скажем).

далее: переместите Нижний диск в пункт назначения:

и, наконец, переместить верхнюю башню (2-1)=1 в пункт назначения.

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

предположим, что мы хотим переместить диск из A В C через B:

  1. переместите меньший диск в B.
  2. перенести другой диск в с.
  3. переместить B В C.
  4. перейти от A к B.
  5. переместить все из C в A.

Если вы повторите все вышеуказанные шаги, то диск перенесет.

Я чувствую боль!

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

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

In Ханойская башня, ответ не в возвращенном результате как таковом, а в наблюдении за возвращенным результатом.

на магия возникает в упражнения rearrangment параметров функции.

да проблема действительно в трех частях:

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

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

решение также передает силу proof by induction и теплое сияние для всех программистов, которые боролись с обычными структурами управления.

Incidently, разрешить проблему вручную довольно удовлетворительный.

  • подсчитайте количество дисков
  • если даже, переместите первый диск на запасной колышек, сделайте следующий юридический шаг (не включая верхний диск). Затем переместите верхний диск на привязку назначения, сделайте следующий юридический ход(nittd). Затем переместите верхний диск на исходную привязку, сделайте следующий юридический ход(nittd).
  • если нечетно, переместите первый диск на привязку назначения, сделайте следующий юридический шаг (не включая верхний диск). Затем переместите верхний диск на запасной колышек, сделайте следующий законный ход (nittd). Затем переместите верхний диск на исходную привязку, сделайте следующий юридический ход(nittd).

лучше всего делать, всегда держа верхний диск одной рукой и всегда двигая эту руку в одном направлении.

Читайте также:  Ноутбук lenovo thinkpad p71

окончательное количество ходов для n дисков 2^n — 1 на move n disc to destination находится на середине процесса.

наконец, это смешно, как объяснением проблема к коллеге, вашим жене / мужу или даже собака (даже ее они не слушают) может цементировать просветление.

прочитав все эти объяснения, я решил взвесить метод, который мой профессор использовал для объяснения рекурсивного решения Ханойских башен. Вот алгоритм снова с n, представляющий количество колец, и A, B, C, представляющий колышки. Первый параметр функции-это количество колец, второй параметр представляет исходный колышек, третий-целевой колышек, а четвертый-запасной колышек.

меня учили в аспирантуре школа, чтобы никогда не стыдиться думать о малом. Итак, давайте рассмотрим этот алгоритм для n = 5. Вопрос, который нужно задать себе в первую очередь:Если я хочу переместить 5-е кольцо из A В B, где остальные 4 кольца? Если 5-е кольцо занимает peg A, и мы хотим переместить его на peg B, то другие 4 кольца могут быть только на peg C. В алгоритме выше функции Ханой (n-1, A, C, B) пытается переместить все эти 4 других кольца на колышек C, поэтому кольцо 5 сможет перейти от A к B. Следуя этому алгоритму, мы рассмотрим n = 4. Если кольцо 4 будет перемещено из A В C, где кольца 3 и меньше? Они могут быть только на колышке B. далее, для n = 3, Если кольцо 3 будет перемещено из A В B, где кольца 2 и 1? На колышке с, Конечно. Если вы продолжаете следовать этому шаблону, вы можете визуализировать, что делает рекурсивный алгоритм. Этот подход отличается от подхода новичка тем, что он смотрит на последний диск первым, а первый диск последним.

подумайте об этом как о стеке, диаметр дисков которого представлен целыми числами (4,3,2,1) Первый вызов рекурсии будет вызван 3 раза и, таким образом, заполнит стек времени выполнения следующим образом

  1. первый звонок : 1. Второй звонок : 2,1. и третий звонок: 3,2,1.

после окончания Первой рекурсии содержимое стека времени выполнения выводится на средний полюс от наибольшего диаметра до наименьшего (первый в последнем). Далее перемещается диск диаметром 4 к месту назначения.

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

все просто. Предположим, вы хотите, чтобы перейти от A к C

Если есть только один диск, просто переместить его.

Если есть более одного диска, сделать

  • переместить все диски (N-1 дисков), кроме нижнего от A до B
  • переместить Нижний диск С A на C
  • переместить N-1 дисков с первого шага от A до c

имейте в виду, что при перемещении N-1 дисков nth не будет проблемой вообще (как только он станет больше чем все остальные)

обратите внимание, что перемещение N-1 дисков повторяется по той же проблеме снова, пока n-1 = 1, в этом случае вы будете на первом if (где вы должны просто переместить его).

ответ на вопрос, как программа знает, что даже "src" для "aux", а нечетный "src" для " dst " для открытия хода лежит в программе. Если вы сломаете кулак с 4 дисками, то это выглядит так:

также первый ход с 4-мя дисками (четными) переходит от Src к Aux.

Как предположили некоторые из наших друзей, я удалил предыдущие два ответа, и я консолидируюсь здесь.

Ссылка на основную публикацию
Adblock detector