VPF::[Delphi] Ханойские башни. Нерекурсивное решение.

WhiteBard

Дата 28.4.2009, 09:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 17
Регистрация: 4.5.2008

Репутация: нет
Всего: нет

Уважаемые программисты. Нужна помощь в решении задачи "Ханойские башни". Задача вроде бы тривиальная, но решена она должна быть нерекурсивным способом при помощи стека (обязательно!). В общем, выручайте. Вот код программы, который у меня есть:

Код


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. Необходимо от нее избавиться. Чего-то я не могу сообразить как.
Жду помощи. Заранее благодарю.

Это сообщение отредактировал(а) WhiteBard - 28.4.2009, 09:04

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »