情况1：如果每次入栈之前只能出栈一次：
核心代码：
// v作为栈存放数据，res作为缓存，存放出栈的元素，打印的时候res从0到n，v从n到0
void DFS(vector<char>v,vector<char>res,int circle){
if(circle==length){
printres(res);
cout<<"*";
printstack(v);
cout<<endl;
return;
}
// 不把该输入pop
v.push_back(input[circle]);
DFS(v,res,circle+1);
// pop该输入
v.pop_back();
res.push_back(input[circle]);
DFS(v,res,circle+1);
}
完整版的代码:
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int length=0;
vector<char>input;
void printres(vector<char>v){
int i;
for(i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
}
void printstack(vector<char>v){
while(!v.empty()){
cout<<v.back()<<" ";
v.pop_back();
}
cout<<endl;
}
void DFS(vector<char>v,vector<char>res,int circle){
if(circle==length){
printres(res);
cout<<"*";
printstack(v);
cout<<endl;
return;
}
// 不把该输入pop
v.push_back(input[circle]);
DFS(v,res,circle+1);
// pop该输入
v.pop_back();
res.push_back(input[circle]);
DFS(v,res,circle+1);
}
int main() {
// freopen("test.txt","r+",stdin);
vector<char>v;
int i;
scanf("%d",&length);
char c;
for(i=0;i<length;i++){
cin>>c;
input.push_back(c);
}
vector<char>res;
DFS(v,res,0);
return 0;
}
/*
3
a b c
*/
情况2：如果出栈次数不受限
如何计算有多少种组合？
- 因为最后栈为空，所以0（出栈）与1（入栈）的个数应该相同。
- 在该0-1串中若出现0大于1的情况，则必有一点满足该点及之前点中
0的和==1的和-1
image.png - 若将该点之后的0变成1,1变成0，则有m+n个1，m+n+2个0，所以如果总个数为2N，出现溢出的可能就有C(N+1,2N)种。
- 所以答案就是N个元素有C(N,2N)-C(N+1,2N)种组合。
如果N个元素可以打乱进栈顺序的话，会有N!*(C(N,2N)-C(N+1,2N))
如何编码实现？
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int length=0;
void print(vector<char>v){
int i;
for(i=0;i<v.size();i++){
cout<<v[i]<<" ";
}
}
// queue用来存放键盘输入，res用来存放pop时打印的输出序列，v用来作为栈使用(最后一次性打印)
void DFS(vector<char>v,vector<char>res,queue<char>q){
if(q.empty()){
// 当 q.empty()时打印res然后再打印v
print(res);
// 输出栈中元素
reverse(v.begin(),v.end());
// 栈要逆向输出
print(v);
cout<<endl;
return;
}
// pop栈v中元素然后放入res中，不需要消耗q
if(!v.empty()){
res.push_back(v.back());
v.pop_back();
// 继续递归
DFS(v,res,q);
// 恢复v和res的初始状态
v.push_back(res.back());
res.pop_back();
}
// 不把该输入pop,存放入栈中
if(!q.empty()){
v.push_back(q.front());
q.pop();
DFS(v,res,q);
}
}
int main() {
freopen("test.txt","r+",stdin);
vector<char>res;
queue<char>q;
vector<char>v;
int i;
scanf("%d",&length);
char c;
for(i=0;i<length;i++){
cin>>c;
q.push(c);
}
DFS(v,res,q);
return 0;
}
/*
3
a b c
*/
只求数，不保留过程序列：(非递归版)
public static int catalanNumber(int n){
int[] arr=new int[n+1];
arr[1]=1;
for(int i=2;i<n+1;i++){
arr[i]=0;
for(int j=1;j<i;j++)
arr[i]+=arr[j]*arr[i-j];
}
return arr[n];
}
拓展阅读：
卡特兰数的问题应用：
-
圆周上有标号为1，2，3，4，……，2n的共计2n个点，这2n个点配对可连成n条弦，且这些弦两两不相交的方式数为卡特兰数。
image.png 游乐园门票1元一张，每人限购一张。现在有10个小朋友排队购票，其中5个小朋友每人只有1元的钞票一张，另5个小朋友每人只有2元的钞票一张，售票员没有准备零钱。问：有多少种排队方法，使售票员总能找的开零钱？
甲乙两人比赛乒乓球，最后结果为20∶20，问比赛过程中甲始终领先乙的计分情形的种数。即甲在得到1分到19分的过程中始终领先乙，其种数是卡特兰数。
-
Cn=n*n的方格地图中，从一个角到另外一个角，不跨越对角线的路径数，例如， 4×4方格地图中的路径有：
image.png
