5.7.1 «Ханойские башни»

Чтобы проиллюстрировать практическое применение принципа «разделяй и властвуй» рассмотрим хорошо известную головоломку «Ханойские башни». Имеются три стержня A, B и C. Вначале на стержень A нанизаны несколько дисков: диск наибольшего диаметра находится внизу, а выше – диски последовательно уменьшающегося диаметра. Цель головоломки – перемещать диски (по одному) со стержня на стержень так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра, и чтобы, в конце концов, все диски оказались нанизанными на стержень B. Стержень C можно использовать для временного хранения дисков.

Рисунок 5.16 – Головоломка «Ханойские башни»

Задачу перемещения n наименьших дисков со стержня A на стержень B можно представить себе состоящей из двух подзадач размера n-1. Сначала нужно переместить n-1 наименьших дисков со стержня A на стержень C, оставив на стержне A n-й наибольший диск. Затем этот диск нужно переместить с A на B. Потом следует переместить n-1 дисков со стержня C на стержень B. Это перемещение n  1 дисков выполняется путем рекурсивного применения указанного метода. Поскольку диски, участвующие в перемещениях, по размеру меньше тех, которые в перемещении не участвуют, не нужно задумываться над тем, что находится под перемещаемыми дисками на стержнях A, B или C. Хотя фактическое перемещение отдельных дисков не столь очевидно, а моделирование вручную выполнить непросто из-за образования стеков рекурсивных вызовов, с концептуальной точки зрения этот алгоритм все же довольно прост для понимания и доказательства его правильности (а если говорить о быстроте разработки, то ему вообще нет равных). Именно легкость разработки алгоритмов по методу декомпозиции обусловила огромную популярность этого метода; к тому же, во многих случаях эти алгоритмы оказываются более эффективными, чем алгоритмы, разработанные традиционными методами.

var N: integer;

procedure MoveDisks(k: integer; X, Y, Z: char);

begin

if k=0 then exit; (выход из рекурсии) MoveDisks(k-1, X, Z, Y); (подзадача 1)

writeln(X,' -> ',Y); (подзадача 2) МоvеDisks(k-1, Z, Y, X);(подзадача 3)

end;

begin

read(N);

MoveDisks(N, 'А', 'В', 'С');

end.

Листинг 5.19 – Алгоритм решения задачи «Ханойские башни»

procedure Try(next_element); begin

<включить next_element в искомое множество>;

if <достигнут нужный результат> then begin

<запомнить этот результат> и/или

<вывести его на печать> и/или <проверить на оптимальность>;

<выйти из процедуры, возможно исключив next element

из этого множества>;

end;

<цикл перебора всех оставшихся или допустимых элементов rest_element, который не обязательно должен быть реализован в виде цикла for, while или repeat> begin (в цикле)

<подсчет необходим локальных величин (*), если надо>; if <условие обрезания дерева

перебора, которого может и не быть>

then Try(rest element);

<обратные действия к (*), если (*} имели место>;

еnd;

<исключить пехt_е1еment из искомого множества»

end;

Листинг 5.20 – Обобщенный алгоритм решения задачи методом перебора