С рассмотренным ниже материалом стоит знакомится после изучения двумерных массивов и подпрограмм.
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Эту игру придумал французский математик Эдуард Люка в 1883 году, её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)», но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа — не более чем анаграмма фамилии изобретателя игры, профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).
Придуманная профессором Люка легенда гласит, что в Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем.
Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
Количество перекладываний в зависимости от количества колец вычисляется по формуле
.
Число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.*
* Источник: Википедия
Итак, приступим. Задачу можно было бы решить с помощью рекурсии, но... рекурсию я не люблю. Я думаю, что рекурсию можно использовать в академическом программировании, а вот в практическом, особенно если Вы программируете какую-нибудь железку с дефицитом памяти, рекурсия может сыграть злую шутку при увеличении вычислительной нагрузки на эту железку. Поэтому рекурсию я использовать не буду. Писать, конечно, придётся побольше, но скорость вычисления и нагрузка на процессор будет ниже. Особенно если Вы используете колец штук двадцать и более.
Алгоритмы решения, насколько я понял, есть разные, оптимальные и не очень. Я буду использовать следующий: на нечетном шаге перемещается самое маленькое кольцо, причем, перемещается оно всегда на следующий стержень: с первого на второй, со второго на третий, с третьего на первый (по кругу)... На чётном шаге перемещается любое другое (не самое маленькое) доступное кольцо на доступный стержень.
Для начала рассмотрим задачу попроще: возьмем не восемь, а три кольца, для перемещения каждого кольца напишем свою процедуру.
Так как шагов немного, сделаем так, чтобы для совершения каждого следующего шага нужно было бы нажимать какую-нибудь клавишу:
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; |