Вот Вам в помощь отрывок из книги
А. Шень. Программирование: теоремы и задачи 2-е изд., М.: МЦНМО, 2004, 296 с. (pdf, 2.1M) здесь правда используется язык Паскаль:
8.2.1. Написать нерекурсивную программу для нахождения последовательности перемещений колец в задаче о ханойских башнях.
Решение.
Вспомним рекурсивную программу, перекладывающую
i верхних колец с
m на
n:
procedure move(i,m,n: integer);
var s: integer;
begin
if i = 1 then begin
writeln (’сделать ход ’, m, ’->’, n);
end else begin
s:=6-m-n; {s - третий стержень: сумма номеров равна 6}
move (i-1, m, s);
writeln (’сделать ход ’, m, ’->’, n);
move (i-1, s, n);
end;
end;
Видно, что задача "переложить
i верхних дисков с
m-го стержня на
n-ый" сводится к трём задачам того же типа: двум задачам с
i-1 дисками и к одной задаче с единственным диском. Занимаясь этими задачами, важно не позабыть, что ещё осталось сделать.
Для этой цели заведём
стек отложенных заданий, элементами которого будут тройки
(i,m,n). Каждая такая тройка интерпретируется как заказ "переложить
i верхних дисков с
m-го стержня на
n-ый". Заказы упорядочены в соответствии с требуемым порядком их выполнения: самый срочный - вершина стека. Получаем такую программу:
procedure move(i,m,n: integer);
begin
сделать стек заказов пустым
положить в стек тройку <i,m,n>
{инвариант: осталось выполнить заказы в стеке}
while стек непуст do begin
удалить верхний элемент, переложив его в <j,p,q>
if j = 1 then begin
writeln (’сделать ход’, p, ’->’, q);
end else begin
s:=6-p-q;
{s - третий стержень: сумма номеров равна 6}
положить в стек тройки <j-1,s,q>, <1,p,q>, <j-1,p,s>
end;
end;
end;
(Заметим, что первой в стек кладётся тройка, которую надо выполнять
последней.) Стек троек может быть реализован как три отдельных стека. (Кроме того, в паскале есть специальный тип, называемый "запись" (
record), который может быть применён.)
