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

С рассмотренным ниже материалом стоит знакомится после изучения двумерных массивов и подпрограмм.

tower_of_hanoi_4

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

Эту игру придумал французский математик Эдуард Люка в 1883 году, её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)», но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа — не более чем анаграмма фамилии изобретателя игры, профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).

Придуманная профессором Люка легенда гласит, что в Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.

Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

Количество перекладываний в зависимости от количества колец вычисляется по формуле 2^{n}-1.

Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.*

* Источник: Википедия

Итак, приступим. Задачу можно было бы решить с помощью рекурсии, но... рекурсию я не люблю. Я думаю, что рекурсию можно использовать в академическом программировании, а вот в практическом, особенно если Вы программируете какую-нибудь железку с дефицитом памяти, рекурсия может сыграть злую шутку при увеличении вычислительной нагрузки на эту железку. Поэтому рекурсию я использовать не буду. Писать, конечно, придётся побольше, но скорость вычисления и нагрузка на процессор будет ниже. Особенно если Вы используете колец штук двадцать и более.

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

Для начала рассмотрим задачу попроще: возьмем не восемь, а три кольца, для перемещения каждого кольца напишем свою процедуру.

hanoi

Так как шагов немного, сделаем так, чтобы для совершения каждого следующего шага нужно было бы нажимать какую-нибудь клавишу:

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Text_IO; use Ada.Text_IO;
 
procedure Hanoi_Simple is
    subtype Tower is Integer range 0..3;
    type Matrix is array(1..4, 1..3) of Tower;
    mas : Matrix;
    ch : Character;
    imin, jmin, imid, jmid, imax, jmax : Integer;
    step: Integer := 1;
 
    --Вывод текущего состояния башни на экран
    procedure Show_Tower(mas : in Matrix) is
    begin
        for i in 1..mas'Last(1) loop
            for j in 1..mas'Last(2) loop
                if mas(i, j) = 0 then
                    Put("   |   ");
                elsif mas(i, j) = 1 then
                    Put("  ###  ");
                elsif mas(i, j) = 2 then
                    Put(" ##### ");
                elsif mas(i, j) = 3 then
                    Put("#######");
                end if;
            end loop;
            New_Line;
        end loop;
    end Show_Tower;
 
    --С целью упрощения понимания для перемещения каждого кольца будет использована своя процедура
 
    --Перемещение самого маленького кольца
    procedure Move_Min(mas : in out Matrix; imin, jmin : in out Integer) is
    begin
        mas(imin, jmin) := 0; --"Снимаем" кольцо со стержня
        jmin := jmin + 1;
        --Проверка выхода кольца за пределы стержней (их всего 3, так что индекс больше 3 быть
        --не может)
        if jmin = 4 then
            jmin := 1;
        --elsif jmin = 5 then
            --jmin := 2;
        end if;
        --Проверяем, есть ли на целевом стержне ещё какое-нибудь кольцо. Если есть, то размещаем
        --самое маленькое кольцо сверху.
        imin := mas'Last(1);
        while mas(imin, jmin) /= 0 loop
            imin := imin -1;
        end loop;
        mas(imin, jmin) := 1; --"Надеваем" кольцо на стержень
    end Move_Min;
 
    --Перемещение среднего кольца
    --Процедура аналогична перемещению самого маленького кольца, но добавлена проверка
    --на то, что кольцо не может быть надето на стержень, на котором уже размещено кольцо
    --меньшего диаметра
    procedure Move_Mid(mas : in out Matrix; imid, jmid : in out Integer) is
    begin
        mas(imid, jmid) := 0;
        jmid := jmid + 1;
        if jmid = 4 then
            jmid := 1;
        end if;
        if jmid = jmin then
            jmid := jmid + 1;
        end if;
        imid := mas'Last(1);
        while mas(imid, jmid) /= 0 loop
            imid := imid - 1;
        end loop;
        mas(imid, jmid) := 2;
    end Move_Mid;
 
    --Перемещение самого большого кольца
    --Все то же самое, что и в предыдущих процедурах, но самое большое кольцо
    --может быть надето только на пустой стержень
    procedure Move_Max(mas : in out Matrix; imax, jmax : in out Integer) is
    begin
        mas(imax, jmax) := 0;
        jmax := jmax + 1;
        if jmax = 4 then
            jmax := 1;
        end if;
        while mas(mas'Last(1), jmax) /= 0 loop
            jmax := jmax + 1;
        end loop;
        mas(imax, jmax) := 3;
    end Move_Max;
 
begin
    mas := ((0, 0, 0), 
            (1, 0, 0),
            (2, 0, 0),
            (3, 0, 0));
    imin := 2; jmin := 1;
    imid := 3; jmid := 1;
    imax := 4; jmax := 1;
 
    Put_Line("Исходное размещение башни:");
    Show_Tower(mas);
    Get_Immediate(ch); --Ожидание нажатия клавиши для выполнения следующего шага
    New_Line;
    loop
        Put_Line("Шаг" & Integer'Image(step));
        Move_Min(mas, imin, jmin);
        Show_Tower(mas);
        step := step + 1;
        Get_Immediate(ch);
        New_Line;
        exit when imin = 2;
 
        Put_Line("Шаг" & Integer'Image(step));
        if jmid = jmin then
            Move_Max(mas, imax, jmax);
        else
            Move_Mid(mas, imid, jmid);
        end if;
        Show_Tower(mas);
        step := step + 1;
        Get_Immediate(ch);
        New_Line;
        exit when imin = 2;
    end loop;
    step := step - 1;
    Put_Line("Перемещение башни завершено. Произведено" & Integer'Image(step) & " шагов.");
end Hanoi_Simple;

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

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
 
procedure Hanoi_2 is
    rings : Integer := 0; --Количество колец (вводит пользователь)
    shaft : constant Integer := 3; --Количество стержней
    count : Integer := 3; --Ширина колец (для рисунка)
    --Массив для хранения текущего положения колец на стержнях
    type Matrix is array(Integer range <>, Integer range <>) of Integer;
    --ch : Character;
    --Для запоминания местоположения самого маленького кольца, стержня-источника и
    --стержня-приёмника
    jmin, jsrc, jdest : Integer := 0;
    step : Integer := 1; --Количество ходов
    --Массив для хранения позиций верхних колец на каждом из трёх стержней. Т.е по индексу
    --1..3 хранятся номера строк массива, расположенные сразу над верхними кольцами стержней.
    --Для каждого стержня номер строки будет свой
    type Valt is array(1..3) of Integer;
    top : Valt; --Для запоминания вершин стержней. Индекс - номер столбца, значение - номер строки
 
    --Первоначальное заполнение массива (все кольца на первом стержне)
    procedure Fill_Tower(mas : in out Matrix; count : in out Integer) is
    begin
        for i in 1..mas'Last(1) loop
            for j in 1..mas'Last(2) loop
                if i = 1 then
                    mas(i, j) := 0;
                elsif j = 1 then
                    mas(i, j) := count;
                    count := count + 2;
                else
                    mas(i, j) := 0;
                end if;
            end loop;
        end loop;
    end;
 
    --Вывод текущего состояния колец на экран
    procedure Show_Tower(mas : in Matrix; count : in Integer) is
        n : Integer;
    begin
        declare
            --Строка для создания "снимка" элемента массива. Сюда записываем "рисунок" из '#' и
            --пробелов
            str : String(1..count);
        begin
            --Преобразуем информацию из массива в рисунок
            for i in 1..mas'Last(1) loop
                for j in 1..mas'Last(2) loop
                    str := (others => ' '); --Изначально строка заполнена пробелами
                    if mas(i, j) /= 0 then
                        --С какой позиции строки должны быть символы '#'
                        n := ((count + 1) / 2) - ((mas(i, j) - 1) / 2);
                        str(n..(n + mas(i, j) - 1)) := (others => '#');
                    else
                        str((count + 1) / 2) := '|';
                    end if;
                    Put(str);
                    Put(" ");
                end loop;
                New_Line;
            end loop;
        end;
    end Show_Tower;
 
    --Перемещает самое маленькое кольцо
    procedure Move_Min(mas : in out Matrix; top : in out Valt; jmin : in out Integer; shaft : in Integer) is
        n : Integer;
    begin
        n := mas(top(jmin) + 1, jmin); --Запомнить размер кольца
        --Обнулить позицию, на которой размещалось кольцо до перемещения:
        mas(top(jmin) + 1, jmin) := 0;
        --Вершина уменьшилась на 1 (массив заполняется в обратном порядке, поэтому '+'), запомнить
        --новую вершину
        top(jmin) := top(jmin) + 1;
        jmin := jmin + 1; --Стержень-приёмник
        --Если при выборе стержня-приёмника вышли за пределы стержней
        if jmin > shaft then
            jmin := jmin - shaft;
        end if;
        mas(top(jmin), jmin) := n; --Кладём кольцо на стержень-приёмник
        top(jmin) := top(jmin) - 1; --Вершина стержня увеличилась на 1. Запомнить новую вершину.
    end Move_Min;
 
    --Получить стержень источник и стержень приёмник для хода, не связанного с перемещением самого
    --маленького кольца
    procedure Get_Src_Dest(mas : in out Matrix; top : in out Valt; jsrc, jdest, jmin, step : in out Integer; shafr : in Integer) is
        Set_Src, Set_Dest : Boolean := False;
        tmp : Integer;
    begin
        --Выбираем два стержня, на которых нет самого маленького кольца
        --Выбираем первый стержень. Пусть это будет стержень-источник
        jsrc := 1;
        while not Set_Src loop
            if jsrc /= jmin and top(jsrc) /= mas'Last(1) then
                Set_Src := True;
            else
                jsrc := jsrc + 1;
            end if;
            if jsrc > shaft then jmin := 1; end if;
        end loop;
        --Выбираем второй стержень, пусть это будет стержень-приёмник
        jdest := 1;
        while not Set_Dest loop
            if jdest /= jmin and jdest /= jsrc then
                Set_Dest := True;
            else
                jdest := jdest + 1;
            end if;
            if jdest > shaft then jdest := 1; end if;
        end loop;
        --Если размер кольца на стержне-приёмнике меньше, чем на стержне-источнике, меняем
        --источник и приёмник местами. Проверяем, что при этом на стержне приёмнике есть
        --хотя бы одно кольцо
        if top(jdest) /= mas'Last(1) then
            if mas(top(jsrc) + 1, jsrc) > mas(top(jdest) + 1, jdest) then
                tmp := jsrc;
                jsrc := jdest;
                jdest := tmp;
            end if;
        end if;
    end Get_Src_Dest;
 
    procedure Move_Next(mas : in out Matrix; top : in out Valt; jsrc, jdest : in Integer) is
        n : Integer;
    begin
        n := mas(top(jsrc) + 1, jsrc);
        mas(top(jsrc) + 1, jsrc) := 0;
        top(jsrc) := top(jsrc) + 1;
        mas(top(jdest), jdest) := n;
        top(jdest) := top(jdest) - 1;
    end Move_Next;
 
begin
    Put("Введите количество колец башни: ");
    Get(rings);
    --Добавим один уровень, чтобы кончики стержней "выглядывали" над кольцами - для красоты :)
    rings := rings + 1;
    declare
        mas : Matrix(1..rings, 1..shaft);
    begin
        top := (1, mas'Last(1), mas'Last(1));
        Fill_Tower(mas, count); --Заполнить стержни
        Show_Tower(mas, count);
        jmin := 1;
 
        loop
            --Перемещаем самое маленькое кольцо
            --Get_Immediate(ch); --Ожидание нажатия клавиши
            Put_Line("Шаг" & Integer'Image(step) & ":");
            Move_Min(mas, top, jmin, shaft);
            Show_Tower(mas, count);
            exit when (top(jmin) + 1) = 2;
            step := step + 1;
 
            --Перемещаем следующее доступное кольцо
            --Get_Immediate(ch); --Ожидание нажатия клавиши
            Get_Src_Dest(mas, top, jsrc, jdest, jmin, step, shaft);
            Put_Line("Шаг" & Integer'Image(step) & ":");
            Move_Next(mas, top, jsrc, jdest);
            Show_Tower(mas, count);
            exit when (top(jmin) + 1) = 2;
            step := step + 1;
        end loop;
    end;
end Hanoi_2;

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *