Ханойские башни без рекурсии

Задача. Написать нерекурсивную программу для нахождения последовательности перемещений дисков в задаче о ханойских башнях.
Решение. Рекурсивная программа имеет вид:

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-ый". Заказы упорядочены в соответствии с требуемым порядком их выполнения: самый срочный - вершина стека. Получаем такую программу:

procedure move(i,m,n: integer);
 begin
 | сделать стек заказов пустым
 | положить в стек тройку 
 | {инвариант: осталось выполнить заказы в стеке}
 | while стек непуст do begin
 | | удалить верхний элемент, переложив его в 
 | | if j = 1 then begin
 | | | writeln ('сделать ход', p, '->', q);
 | | end else begin
 | | | s:=6-p-q;
 | | | {s - третий стержень: сумма номеров равна 6}
 | | | положить в стек тройки , <1,p,q>, 
 | | end;
 | end;
 end;

Заметим, что сначала в стек кладется тройка, которую надо выполнять последней. Стек троек может быть реализован как три отдельных стека. Кроме того, в паскале есть специальный тип, называемый "запись", который может быть применен.