问题 E: 【递归入门】出栈序列统计 时间限制: 1 Sec 内存限制: 128 MB 献花: 30 解决: 27 [献花][花圈][TK题库] 题目描述 栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两•种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。
输入 一个整数n（1<=n<=15） 输出 一个整数，即可能输出序列的总数目。 样例输入 3 样例输出 5 提示
先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。
用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。
方法一：利用出栈公式进行计算
#include <iostream> #include <cmath> using namespace std; typedef unsigned long long ULL; ULL Cnm(int n,int m) { ULL res = 1; for(int i=1;i<=m;++i) { res = res * (n-i + 1) / i; } return res; } int main() { #ifdef _Debug freopen("data.txt","r+",stdin); #endif // _Debug int n; while(cin >> n) { ULL res = Cnm(2 * n,n)/(n+1); cout << res<<endl; } return 0; } /************************************************************** Problem: 5977 User: Sharwen Language: C++ Result: 升仙 Time:6 ms Memory:1704 kb ****************************************************************/方法二：回溯法
#include <iostream> #include <cmath> using namespace std; int c = 0; void DFS(int in,int out) { if(out == 0) { ++c; } else if(in == 0)//如果已经入栈没有元素，则入栈元素，待入栈元素少一个 { DFS(in + 1,out -1); } else if(out)//如果入栈有元素且待入栈也有元素，则分两种情况，一种是继续入栈，一种是出栈 { DFS(in + 1,out - 1); DFS(in - 1,out); } } int main() { #ifdef _Debug freopen("data.txt","r+",stdin); #endif // _Debug int n; while(cin >> n) { c = 0; DFS(0,n); cout << c<<endl; } return 0; }