Ханойские башни

В конце 19-го столетия в Европе появилась игра под названием "Ханойская башня".

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

Предметами игры служили медная платформа с укрепленными на ней тремя алмазными иглами с насажанными на них шестьюдесятью четырьмя золотыми дисками (рис. _).

В современных магазинах эта игра распространяется в комплекте из восьми картонных колец, насажанных на трех деревянных стержнях.

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

Предположим, что иглы пронумерованы (I, II, III) и монахам надо перенести 64 кольца с иглы I на иглу III. обозначим поставленную задачу следующим образом:

Перенести башню (64,I,III) или сокращенно ПБ(64,I,III)

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

К простому решению приводит догадка о том, что основное внимание нужно обратить на нижний диск иглы I, а не на верхний. То есть, если мы сможем снять с иглы I все кольца, кроме самого нижнего, то перенесем его на иглу III.

Приходим к задаче:

Перенести башню (63, 1, 2)

Перенести диск с иглы 1 на иглу 3

Перенести башню (63, 2, 3)

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

Например, задача "Перенести башню (63, I ,II)" может быть выражено как:

Перенести башню (62, I, III)

Перенести диск с иглы I на иглу II (или ПД(I, II))

Перенести башню (62, III, II)

Представим последовательность действий в виде схемы:

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

Перенести башню (n, a, b, c)

Это означает, что необходимо перенести n дисков с начальной иглы a на конечную иглу b, используя иглу c для временной башни.

Задача перенести башню (n, a, b, c) может быть решена за три шага:

Перенести башню (n-1, a, c, b)

Перенести диск с иглы a на иглу b

Перенести башню (n-1, c, b, a)

Этот алгоритм не имеет смысла для случая n<=1, поэтому добавляем правило:

Ничего не делать, если n<=1.

Представим схематично (выполняем до n ≤ 1):

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

Program Hanoy_Tower;

Var Kol_diskov: Integer;

Procedure move_tower (h, s, na, rab: integer);

{h — высота башни, s — номер иглы, с которой нужно снять башню, na — номер иглы, на которую нужно ее перенести, rab — игла, используемая в качестве рабочей}

begin

if h>0 then

begin

move_tower (h-1, s, rab, na);

move_disk (s,na);

move_tower (h-1, rab, na, s);

end;

end;

procedure move_disk (take, place: integer);

{ take — номер иглы, с которой нужно взять диск, place — номер иглы, на которую нужно положить диск}

begin

writeln (take, '->', place);

end;

Begin

write ('Введите число дисков:');

readln (kol_diskov);

move_tower (kol_diskov, 1, 3, 2);

End.

Рассмотрим выполнение программы при задании количества дисков равным трем (Kol_diskov = 3).

Выясним, куда необходимо перекладывать кольца (номер в рамке означает порядок вызова действия).

21 шаг:

На экране после выполнения программы будет выведено:

1->3

1->2

3->2

1->3

2->1

2->3

1->3