Программа решения задачи о ханойской башне
Задача
Написать программу решения задачи о ханойской башне.
Решение
В одной из древних легенд говорится следующее. «В храме Бенареса находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 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.
Программа на языке Паскаль:
type st = (left, middle, right); nat = 1..maxint; var m: nat; {m – число дисков} procedure move(n: nat; s1, sw, sk: st); {перемещение n дисков с s1 на sk} procedure step; {перемещение одного диска с s1 на sk} procedure print(s: st); begin case s of left: write(' лев. '); middle: write(' средн. '); right: write(' прав. ') end; end; begin {step} write(' снять диск с '); print(s1); write(' надеть на '); print(sk); writeln end; begin {move} if n = 1 then step else begin move(n - 1, s1, sk, sw); step; move(n-1, sw, s1, sk) end end; begin read(m); {число дисков} writeln('для ', m:3, ' дисков следует произвести ', 'следующие действия:'); move(m, left, middle, right); readln end.
Комментарии
Никаких степеней нет
Потребуется m*m перемещений дисков. для m=11 нужно 121 перемещение.
Мой вариант самый короткий :)))
Предлагаю свой вариант
Задача о Ханойской башне
"В общем случае потребуется 2m-1 перемещений"
Нет. Потребуется 2 в степени m-1 перемещений.