Программа решения задачи о ханойской башне

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