本文共 1747 字，大约阅读时间需要 5 分钟。

情况1：如果每次入栈之前只能出栈一次：

核心代码：

// v作为栈存放数据，res作为缓存，存放出栈的元素，打印的时候res从0到n，v从n到0void DFS(vector
   
    v,vector
    
     res,int circle){  if(circle==length){    printres(res);    cout<<"*";    printstack(v);    cout<
    
   

完整版的代码:

#include 
   
    #include 
    
     #include 
     
      using namespace std;int length=0;vector
      
       input;void printres(vector
       
        v){  int i;  for(i=0;i
        
         v){ while(!v.empty()){ cout<
         
          <<" "; v.pop_back(); } cout<
          
           v,vector
           
            res,int circle){ if(circle==length){ printres(res); cout<<"*"; printstack(v); cout<
            
             v; int i; scanf("%d",&length); char c; for(i=0;i
             
              >c; input.push_back(c); } vector
              
               res; DFS(v,res,0); return 0;}/*3a b c*/
              
             
            
           
          
         
        
       
      
     
    
   

情况2：如果出栈次数不受限

如何计算有多少种组合？

1. 因为最后栈为空，所以0（出栈）与1（入栈）的个数应该相同。
2. 在该0-1串中若出现0大于1的情况，则必有一点满足该点及之前点中0的和==1的和-1

    

   image.png

3. 若将该点之后的0变成1,1变成0，则有m+n个1，m+n+2个0，所以如果总个数为2N，出现溢出的可能就有C(N+1,2N)种。
4. 所以答案就是N个元素有C(N,2N)-C(N+1,2N)种组合。

如果N个元素可以打乱进栈顺序的话，会有N!*(C(N,2N)-C(N+1,2N))

如何编码实现？

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int length=0;void print(vector
       
        v){  int i;  for(i=0;i
        
         v,vector
         
          res,queue
          
           q){ if(q.empty()){ // 当 q.empty()时打印res然后再打印v print(res); // 输出栈中元素 reverse(v.begin(),v.end()); // 栈要逆向输出 print(v); cout<
           
            res; queue
            
             q; vector
             
              v; int i; scanf("%d",&length); char c; for(i=0;i
              
               >c; q.push(c); } DFS(v,res,q); return 0;}/*3a b c*/
              
             
            
           
          
         
        
       
      
     
    
   

拓展阅读：

卡特兰数的问题应用：

• 圆周上有标号为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

转载地址：http://wuxen.baihongyu.com/