|
sitelink://S536// НАЗАД
В заключение параграфа приведем пример красивой программы, использующей рекурсию.
Рассмотрим классическую задачу, известную в литературе под названием «Ханойская башня». Задача о Ханойской башне и связанная с ней легенда принадлежат математику Эдуарду Люка.
На площадке (назовем ее А) находится пирамида, составленная из дисков уменьшающегося от основания к вершине размера.
Эту пирамиду в том же виде требуется переместить на площадку В. При выполнении этой работы необходимо соблюдать следующие ограничения:
· перекладывать можно только по одному диску, взятому сверху пирамиды;
· класть диск можно либо только на основание площадки, либо на диск большего размера;
· в качестве вспомогательной можно использовать площадку С.
Название «Ханойская башня» связано с легендой, согласно которой в давние времена монахи одного ханойского храма взялись переместить по этим правилам башню, состоящую из 64 дисков. С завершением их работы наступит конец света.
Монахи все еще работают, и, надеемся, еще долго будут работать!
Нетрудно решить эту задачу для двух дисков. Обозначая перемещения диска, например, с площадки А на В так: А ->В, напишем алгоритм для этого случая
А->С; А->В; С->В.
Всего 3 хода! Для трех дисков алгоритм длиннее:
А->В; А->С; B->С; А->В;С->А;С->В; А->В.
В этом случае уже требуются 7 ходов.
Подсчитать количество ходов (N) для к дисков можно по следующей рекуррентной формуле:
N(1) = 1; N(k) = 2*N(k - 1) + 1.
Например, N(10) = 1023, N(20) = 104857. А вот сколько перемещений нужно сделать ханойским монахам:
N(64) = 18446744073709551615.
Попробуйте прочитать это число.
Теперь составим программу, по которой машина рассчитает алгоритм работы монахов и выведет его для любого значения n (количества дисков). Пусть на площадке А находятся n дисков. Алгоритм решения задачи будет следующим:
1. Если n = 0, то ничего не делать.
2. Если n > 0, то переместить n — 1 диск на С через В;
переместить диск с А на В (АàВ)
переместить n — 1 диск с С на В через А.
При выполнении пункта 2 последовательно будем иметь три состояния.
Описание алгоритма имеет явно рекурсивный характер. Перемещение n дисков описывается через перемещение n—1 диска. А где же выход из этой последовательности рекурсивных ссылок алгоритма самого на себя? Он в пункте 1, каким бы ни показалось странным его тривиальное содержание.
Обратите внимание на разницу между «перенести n колец с A на B», что указывает на рекурсивное применение алгоритма к задаче в целом, и «переместить диск с A на B», что указывает на непосредственно выполняемое действие и является к тому же единственно элементарным действием, разрешаемым правилами игры, заключающимися в перемещении одного кольца с одного основания на другое.
Отметим, что в этой подпрограмме единственное реальное «действие» выполняется строкой переместить диск с А на В (А->В)
Остальное служит только для описания последовательности рекурсивных вызовов и соответствующих модификаций параметров.
НАЗАД
| 
