Уважаемые программисты. Нужна помощь в решении задачи "Ханойские башни". Задача вроде бы тривиальная, но решена она должна быть нерекурсивным способом при помощи стека (обязательно!). В общем, выручайте. Вот код программы, который у меня есть:
| Код |
const
masmax=100;
type
Mas=array [0..masmax] of byte;
stack=record
M:Mas;
n:byte;
name:char;
end;
var
count:longint; {счетчик количества перекладываний колец}
procedure move_all(var A,B,C:stack;k:byte);
procedure move_one(var S1,S2:stack);
procedure put(var S:stack;e:byte);
function get(var S:stack):byte;
function top(S:stack):byte;
implementation
{$R *.dfm}
function top(S:stack):byte; {возвращает верхний эл-т стека не извлекая его}
begin
top:=S.M[S.n];
end;
function get(var S:stack):byte; {Извлекает верхний элемент из стека}
begin
get:=S.M[S.n];
S.n:=S.n-1;
end;
procedure put(var S:stack;e:byte); {кладет элемент в стек}
begin
S.n:=S.n+1;
S.M[S.n]:=e;
end;
procedure move_one(var S1,S2:stack); {Перемещает кольцо с S1 на S2, если на стержне S1 есть хоть одно кольцо и оно "меньше" верхнего кольца на S2}
begin
if (S1.n>0) and (top(S1)<top(S2)) then begin
put(S2,get(S1));
end;
count:=count+1;
end;
procedure move_all(var A,B,C:stack;k:byte);{Рекурсивная процедура. Замыкающее соотношение-надо перекинуть одно кольцо}
begin
if k=1 then begin
move_one(A,C);
exit;
end;
move_all(A,C,B,k-1);
move_one(A,C);
move_all(B,A,C,k-1);
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
close;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
A,B,C:stack;
i,k,n:byte;
begin
{A-исходный стержень, B-пустой, C-на который надо перекинуть кольца}
count:=0;
k:=strtoint(edit1.text);
n:=k;
{Забиваем стержень A}
for i:=1 to k do begin
put(A,n);
dec(n);
end;
A.n:=k;
B.n:=0;
C.n:=0;
A.M[0]:=masmax+1;
B.M[0]:=masmax+1;
C.M[0]:=masmax+1;
A.name:='1';
B.name:='2';
C.name:='3';
move_all(A,B,C,k);
listbox1.Items.add('Количество перемещений: '+inttostr(count));
end;
end.
|
Эта программа использует стек, но содержит рекурсивную процедуру move_all. Необходимо от нее избавиться. Чего-то я не могу сообразить как.
Жду помощи. Заранее благодарю. |