当先锋百科网

首页 1 2 3 4 5 6 7

数据结构堆栈习题

ps:同学优秀答案 

3.7、整数1,2,3,4,5依次进栈，最后都出栈，可能的出栈序列 

法一：（李） 

 法二：(马)

这是一个动态规划问题。用一个f[i][j]数组记录栈内有i个元素，栈外有j个元素时所有的可能情况。目的是f[0][5],已知f[i][0]=1;每种情况都与相邻情况有以下关系
if(i == 0) f[i][j] = f[1][j-1];//只能push.
If(i != 0) f[i][j] = f[i-1][j] + f[i+1][j-1];//要么pop，要么push.

#include<bits/stdc++.h>
using namespace std;
int f[6][6];
int main(){
for(inti = 0;i <= 5;i ++ ) f[i][0]=1;
for(int j = 1;j <= 5;j ++ )
   for(int i = 0;i <= 5 - j;i ++ )
      if(i)
        f[i][j] = f[i-1][j] + f[i+1][j-1];
      else
        f[i][j] = f[1][j-1];
   cout<<f[0][5]<<endl;
   return 0;
}

法三：（陈） 


如果要输出所有可能的序列，需要用dfs以的复杂度实现；如果仅考虑方
法数，可以通过递推和动态规划以复杂度实现。更进一步说，求出入栈顺
序的方法数是卡塔兰数的一个应用。


dfs搜索


思路
用搜索求解出栈顺序问题，面对任何一个状态我们有两种选择：
1.如果还有元素未入栈，将一个元素入栈。
2.如果栈不为空，将栈顶元素出栈。
对应上述两种选择，分别搜索即可，但尤其注意注释处需要恢复被子状态
修改的栈顶元素（否则就会盯着代码半小时看不出问题）。
另一个需要注意的问题，如果要以字典序输出可能序列的话，必须保证
dfs过程中优先递归第二种选择。

#include<bits/stdc++.h>
usingnamespacestd;
ints[21],cnt=20,n,o[21];
voiddfs(intindex,intin,intout){
if(!cnt)return;
if(out==n){
for(inti=0;i<n;++i)
cout<<o[i];
cout<<endl;
cnt--;
return;
}
if(in){
intx=s[in-1];
o[out]=s[in-1];
dfs(index,in-1,out+1);
s[in-1]=x;//恢复在调用过程中被修改的栈顶
}
if(index<=n){
s[in]=index;
dfs(index+1,in+1,out);
}
}
intmain(){
cin>>n;
dfs(1,0,0);
}
运行截图
​
递推
思路
能使用递推或dp解决的问题的特点是规模小的问题会先于规模大的问题
被解决，而规模大的问题的解决会用到规模小的问题。
其实引例(P73)中有一个问题：已知1，2，3个字符的出栈顺序数分别为
1，2，5，问4个字符的出栈顺序数。
对于该问题，因为我们只关顺序数，而不关心具体的字符顺序，换句话
说，对于序列ABC和BCD来说，出栈顺序数都是5。
因此，我们可以考虑将大规模问题分解为小规模问题：通过序列中第一个
字符，将序列分成两部分，而这两部分显然在解决该问题前已经被解决，
这就是递推的思想。
具体来说，解决该问题的步骤为：
1.第一个字符可以出现在最终序列中的任一位置。
2.把序列分成了两个子部分，前一部分个字符任意顺序出栈，后一部分个
字符任意顺序出栈。
3.记个字符的出栈数为，则有。
代码
#include<bits/stdc++.h>
usingnamespacestd;
constintM=100;//规模太大需要用高精度，在此不表
intf[M]={1};//f[0]为1
intmain(){
intn;
cin>>n;
for(inti=1;i<=n;++i)
for(intj=1;j<=i;++j)//表示第一个元素在第j个位置
f[i]+=f[j-1]*f[i-j];
cout<<f[n];
}
运行截图
​
动态规划
思路
动态规划的可行性要求与递推类似，大规模问题可由子状态转移得到。
在该问题中，因为对于任一时刻，已出栈的元素的顺序已经确定，故我们
定义为当前有个元素还未入栈，有个元素仍在栈内，个元素已经出栈时，
出栈顺序的方法数。
有状态转移方程：
该方程的解释为：对于一个状态，我们的操作要么是将一个数出栈，要么
将一个数入栈。而经过操作后方法数一定减少，也就是状态向两个子状态
转移了。
或者用逆向思维理解：状态记作，状态记作，状态记作。只能由和转移而
来，其中通过将栈顶元素放回未入栈序列得到，通过将刚才出栈的元素放
回栈顶而回到状态。
目标状态显然为：
但是在递推过程中需要注意边界问题，首先栈内元素与未入栈元素之和不
超过n；其次如果未入栈元素为0，显然不可能再让元素入栈；最后如果
栈内没有元素，也不可能让元素出栈。

#include<bits/stdc++.h>
usingnamespacestd;
constintM=100;
intdp[M][M]{1};
intmain(){
intn;
cin>>n;
for(inti=0;i<=n;++i)
for(intj=0;i+j<=n;++j)//栈内元素与未入栈元素之和不超过n
if(i||j)dp[i][j]=(i?dp[i-1][j+1]:0)+(j?dp[i][j-
1]:0);//元素不足以转移状态
cout<<dp[n][0];
}
卡塔兰数
思路
如果将出入栈操作抽象为1和0，那么出栈顺序问题可以等价为求给定n
个1和n个0，它们按照某种顺序排成长度为2n的序列，满足任意前缀
中0的个数都不少于1的个数的序列的数量。
而该等价问题就是卡塔兰（Catalan）数的模型。