历届试题_出栈次序

X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。
路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。
X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？
为了方便起见，假设检查站可容纳任意数量的汽车。
显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。现在足足有16辆车啊，亲！需要你计算出可能次序的数目。

思路：这道题其实是一个进栈出栈的题，也就是问所有出栈顺序的可能数，如果之前了解过这方面的问题的同学，这道题其实就是送分题，可以直接利用卡特兰数的公式求解，不了解的话

可以看一下我之前写的一篇博客，也是关于进出栈次序的问题，有对卡特兰数详细的分析https://www.cnblogs.com/henuliulei/p/9867106.html，下面是几种网上的常见求解思路，做了一下总结

方法一：求出栈次序，无非就是问一共有多少种满足要求的排列，满足条件在本题中就是指，只有站中有“车”，才能够出来。假设1，代表进站，0代表出站，r代表进栈的个数，L代表出栈的个数，易知

只有进栈的个数r大于等于出栈的个数L才可以出栈或进栈，否则只能进栈,因此可以进行回溯求出所有可能的方案。

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int num=0;
 6 
 7  
 8 
 9 void dfs(int n,int r,int l){
10 
11     if(n==32){
12 
13         num++;
14 
15         return;
16 
17     }
18 
19  
20 
21         if(r>l){
22 
23             if(r<16)
24 
25             dfs(n+1,r+1,l);
26 
27             if(l<16)
28 
29             dfs(n+1,r,l+1);
30 
31         }else{
32 
33             if(r==l)
34 
35             if(r<16)
36 
37             dfs(n+1,r+1,l);
38 
39         }
40 
41  
42 
43     return;
44 
45 }
46 
47  
48 
49 int main(){
50 
51     
52 
53     dfs(0,0,0);
54 
55     cout<<num<<endl;
56 
57     return 0;
58 
59 }

方法二：利用卡特兰数的公式f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... +f(n-1)*f(0)

 1 #include <stdio.h>
 2 
 3 int main()
 4 
 5 {
 6 
 7     int f[20];
 8 
 9     int i,j;
10 
11     f[0]=1;
12 
13     f[1]=1;
14 
15     f[2]=2;
16 
17     f[3]=5;
18 
19     for(i=4;i<=16;i++)
20 
21         f[i]=0;//注意必须给其他数组置0
22 
23     for(i=4; i<=16; i++) //求16个元素
24 
25     {
26 
27         for(j=0; j<=i-1; j++)
28 
29             f[i]+=f[j]*f[i-1-j];
30 
31     }
32 
33     printf("%d",f[16]);
34 
35     return 0;
36 
37 }

方法三：卡特兰数的另一种递推公式h(n)=h(n-1)*(4*n-2)/(n+1)

 1 #include <stdio.h>
 2 
 3 int main()
 4 
 5 {
 6 
 7     int n,h[20];
 8 
 9     h[0]=1;
10 
11     h[1]=1;
12 
13     for(n=2;n<=16;n++)
14 
15         h[n]=h[n-1]*(4*n-2)/(n+1);
16 
17     printf("%d
",h[16]);
18 
19     return 0;
20 
21 }

方法四：卡特兰数递推公式的解：h(n)=C(n,2n)*(2n-1) (n=0,1,2,...)

该种方法有一定的局限性，因为n>14时数据会超出unsigned long long int 的范围（0~2^64-1），不过可以考虑先求n=14的解，再用计算器推出n=16的解。

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 int m;
 5 unsigned long long int f(int n)
 6 {
 7    unsigned    long long int m1=1;
 8     unsigned    long long int m2=1;
 9     for(int i=1;i<=n;i++){
10         m1*=i;
11     }
12     for(int i=2*n;i>n;i--){
13         m2*=i;
14     }
15    // cout << m2 << "--" << m1 << endl;
16     m=m2/m1;
17     return m;
18 }
19 int main()
20 {
21 
22    int n;
23   // while(true){
24        cin >> n;
25    cout << f(n)/(n+1);
26   // }
27     return 0;
28 }

总之熟记卡特兰数即可。