高分：堆栈以abcd顺序入栈，如何求所有合法的出栈序列 (300分)

L

lps

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-31

• #1

请给出算法或思路！
ps:全部入栈，也全部出栈，但入栈完成前就可出栈。

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-31

• #2

思路简单:深度优先搜索.

 

L

lps

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-31

• #3

清华 严蔚敏的数据结构题集中有一个相似的题，就是以S和X分别表示入栈和出栈，然后
分别判S和X的序列是否合法，那么如何判是否合法？

 

L

lqy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-31

• #4

我的理解是
栈其實是一個簡化的練表,
你只需要保存 栈基址,和栈首址
然後按先進後出,或先進先出的規則來出棧,
循序肯定沒問題啊,需要判斷循序嗎?

 

S

shenloqi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-01

• #5

哈哈，功力浅，不知道什么意思。
是不是abcd入栈，出栈只能是dcba,dcb,cba,dc,cb,ba,d,c,b,a还是只能是dcba,dcb,dc,d
还是dcba,dcb,dca,dba,cba,dc,db,da……？还是别的？

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-01

• #6

昨天的货箱用了非递归的,今天就用个递归的吧.
program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils;
type
TIntegerArr = array [1..4] of Integer;
var
PopedList: TIntegerArr;
Stack: TIntegerArr;
procedure TryDoIt(PopedIndex, UnPushIndex, StackTop: Integer;
Stack: TIntegerArr);
var
i: Integer;
begin
if PopedIndex=5 then
begin
for i:=1 to 4do
Write(Chr(Ord('a')-1+PopedList), ' ');
WriteLn;
Exit
end;

if StackTop>0 then
begin
PopedList[PopedIndex]:=Stack[StackTop];
TryDoIt(PopedIndex+1, UnPushIndex, StackTop-1, Stack)
end;
if UnPushIndex<=4 then
begin
Stack[StackTop+1]:=UnPushIndex;
TryDoIt(PopedIndex, UnPushIndex+1, StackTop+1, Stack)
end;
end;

begin
TryDoIt(1, 1, 0, Stack);
ReadLn
end.
另外,任何结果字符串的子串也是合法串.

 

大

大富翁WW

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-02

• #7

这样也行:
procedure TForm1.Button1Click(Sender: TObject);
const
Max = 3 + Ord('a');
var
AIntArray1: array[Ord('a')..Max, Ord('a')..Max, Ord('a')..Max, Ord('a')..Max] of Boolean;
i, j, k, l: Integer;
Flag: Boolean;
begin
Flag := False;
for i := Ord('a') to Maxdo
for j := Ord('a') to Maxdo
for k := Ord('a') to Maxdo
for l := Ord('a') to Maxdo
if (l <> k) and (l <> j) and (l <> i) and
(k <> j) and (k <> i) and (j <> i) then
begin
AIntArray1[j][k][l] := True;
if (j < i) and (j < k) then
if (k < i) then
Flag := True;
if (j < i) and (j < l) then
if l < i then
Flag := True;
if (K < j) and (k < l) then
if l < j then
Flag := True;
if Flag then
AIntArray1[j][k][l] := False;
if AIntArray1[j][k][l] then
Memo1.Lines.Add(Char(i) + ' ' + Char(j) + ' ' +
Char(k) + ' ' + Char(l));
Flag := False;
end;
end;

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-01

• #8

to 大富翁WW:
如果题目换成abcdefghijklmnopqrstuvwxyz,我看你用几重循环.呵呵.

 

大

大富翁WW

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-02

• #9

to LeeChange
见笑了, 没有深入研究[]

 

I

ike

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-02

• #10

up有分？

 

G

gglrobin

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-04

• #11

还是用深度优先算法更好吧

 

楼

楼兰魂

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-04

• #12

你等着我帮你找。我有书。

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-04

• #13

to gglrobin:
我用的不是深度优先搜索吗？呵呵。

 

楼

楼兰魂

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-04

• #14

有了。
只有s与x。
判别合法的充分必要条件
[Nsi(T)+Nxl(T)=l]与[Nsl(T)=Nxl(T)]与（对所有i） (1<=i<=l->Nsi(T)>=Nxi(T))
Nsi(T)表示序列T中前i个字符构成的子序列中‘S‘的数目；
Nxi(T)表示序列T中前i个字符构成的子序列中‘X‘的数目；
与和对所有的符号不会写。
将就一下。
si,xi,sl,xl都是下标。

 

L

lps

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-05-18

• #15

多人接受答案了。