问题 E: 【递归入门】出栈序列统计

问题 E: 【递归入门】出栈序列统计
[命题人 : 外部导入]
时间限制 : 1.000 sec 内存限制 : 128 MB

题目描述
栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两•种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。

输入
一个整数n（1<=n<=15）

输出
一个整数，即可能输出序列的总数目。

样例输入 Copy
3
样例输出 Copy
5
提示
先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。
用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。

第一种办法用递归本身是栈模拟
第二种办法直接把全排列列出来，比较容易理解，然后根据性质筛选掉，数列中不符合的数列。
这里只提供第一种方法

#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
int N;
int cnt;
void
dfs(int outl,int in,int outr) {
if(outr==N) {
cnt++;
return ;
}
if(outl>0&&in<N)
dfs(outl-1,in+1,outr);
if(in>0&&outr<N)
dfs(outl,in-1,outr+1);
}
int main() {
cnt = 0;
scanf("%d",&N);
dfs(N,0,0);
cout<<cnt<<endl;
return 0;
}

最后

以上就是微笑灰狼为你收集整理的问题 E: 【递归入门】出栈序列统计的全部内容，希望文章能够帮你解决问题 E: 【递归入门】出栈序列统计所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。