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

Задача. Игра "Ханойские башни" состоит следующем. Есть $n$ дисков и три стержня: 1, 2 и 3. В начальной конфигурации все диски надеты на один из стержней, образуя башню в виде пирамиды (меньшие диски в ней расположены поверх больших). Ход -- это перекладывание одного диска. Можно переместить верхний диск со стержня на стержень, но нельзя помещать больший диск поверх меньшего. Требуется указать последовательность ходов, перемещающих всю башню с исходного стержня на заданный.

Решение. Будем строить рекурсивный алгоритм, сводя решение задачи с большим числом дисков к задачам с меньшим числом. Пусть диски на исходном стержне $S_1$ занумерованы сверху вниз от 1 до $n$.

Легко осуществить перенос башни, если диск один.

Для случая, когда $n>1$ перенос башни на заданный стержень $S_2$ можно осуществить с помощью следующей последовательности действий:

(1) сначала применяем наш алгоритм для переноса башни из ($n$-1) дисков c исходного стержня $S_1$ на рабочий стержень $S_3$ (он отличен от $S_1$ и $S_2$),

(2) после этого $n$-й диск на исходном стержне становится верхним, и его можно перенести на заданный стержень $S_2$,

(3) еще раз применяем наш алгоритм для переноса на заданный стержень $S_2$ башни из ($n$-1) дисков, находящейся на рабочем стержне $S_3$. Получаем следующую программу:

module ХанойскиеБашни;
    const M = 3;
    type Стержень= integer;
    var N: integer; S1, S2: Стержень;
    procedure Диск(N: Integer; S1, S2: Стержень);
        begin writeln('Перенести диск ', N, 'со стержня ', S1,' на стержень ', S2) end Диск;
    procedure Башня(N: Integer; S1, S2: Стержень);
            var M: integer; S3: Стержень;
        begin
            if N = 1 then Диск(N, S1, S2)
            else (* {S1+S2+S3=6}*)
                    S3:= 6-S1-S2; M:=N-1;
                    Башня(M, S1, S3); Диск(N, S1, S2); Башня(M, S3, S2)
            end
        end Башня;
begin
    read(N,S1,S2);
    writeln('Для переноса башни из ', N, ' дисков со стержня ', S1,' на стержень ', S2,
                ' требуется выполнить следующие действия: ');
    Башня(N, S1, S2);
end ХанойскиеБашни.

Доказательство окончания процедуры Башня вытекает из того, что в ее рекурсивных вызовах значение первого параметра всегда понижается (на единицу меньше) и мы обязательно придем в конце концов к вызову процедуры со значением параметра равным 1, а в таком случае она не порождает новых своих вызовов.