singlepost

Рекурсия -> Стек << На главную или назад  

Товарищи, помогите кто чем может. Нужна программа, которая выводит все перестановки N чисел, используя стек (не через рекурсию). Понимаю, что можно просто взять рекурсивную и имитировать рекурсию через стек, но вот с этой программой не удается такого:

const n=3;
var x:array [1..n] of integer;
i:integer;

procedure printm;
var i:integer;
begin
for i:=1 to n do write(x[i],' ');
writeln;
end;

procedure swap(var a,b:integer);
var v:integer;
begin
v:=a; a:=b; b:=v
end;

procedure perest(k:integer);
var i:integer;
begin
if k=n-1 then printm
else
for i:=k+1 to n do
begin
swap(x[k+1],x[i]);
perest(k+1);
swap(x[k+1],x[i]);
end;
end;

begin
for i:=1 to n do x[i]:=i;
perest(0);
readln;
end.

Кто что посоветует? В сети не смог найти нужного мне алгоритма, может кто-нибудь посоветует другую рекурсивную программу, которую проще переделать или даст мысль как переделать эту?
Сделал дерево перебора для N=4.. была мысль заносить в стек пары чисел – тех что меняются местами на данном шаге. На бумаге вроде работает, но все равно не получается додумать до готового кода.
И кстати желательно не использовать массивов с флагами типа "число занято".

41 ответов в теме “Рекурсия -> Стек”

  1. 2
    Алексей Казаев ответил:

    скажу проще – переделать вот эту программу в нерекурсивную, работающую через стек вместо рекурсии. у меня не получается.

  2. 1
    Михаил Пеньков ответил:

    А если так:

    const n=4;
    var x:array [1..n] of integer;
    i:integer;

    procedure printm;
    var i:integer;
    begin
    for i:=1 to n do write(x[i],' ');
    writeln;
    end;

    procedure swap(var a,b:integer);
    var v:integer;
    begin
    v:=a; a:=b; b:=v
    end;

    procedure perest(k:integer);
    var i:integer;
    begin
    if k=n-1 then printm
    else
    for i:=k+1 to n do
    begin
    swap(x[k+1],x[i]);
    perest(k+1);
    swap(x[k+1],x[i]);
    end;
    end;

    begin
    for i:=1 to n do x[i]:=i;
    perest(0);
    readln;
    end.

    ????
    Мне задача не очень ясна.

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.