《栈的计数》问题的算法分析

问题转述：

求一列共n辆的火车按顺序通过一个栈所产生的排列总数。

分析：

这一类组合计数题目显然不能用搜索的方法把所有可能的移动方案都穷举出来再统计总数──这样做时间复杂度极大。这道题与经典的HANOI问题很相似，所以应当根据问题本身的性质，利用组合数学的原理，将原问题转化为递归形式，找到计算总数的递归方程，再进行计算。

摘要：

算法一：

我们不妨直接设n辆火车产生的排列总数为f(n)。看看能不能找到一些规律。 如图,n列火车通过栈,起始车头在车列最前端。经过移动后,车头处在了第a+1位,车头前有a辆车,车头后有b辆车(a>=0,b>=0)。则n=a+b+1,b=n-a-1。

若要达到上述移动目的,步骤为:

(1)    将车头进栈;

(2)    将车头后a辆车依次通过栈，移至轨道另一端；

(3)    将车头出栈，则车头恰好排在第a+1位；

(4)    将轨道右端剩余b辆车依次通过栈，移至轨道另一端；

不难证明，移动方案仅此一种。问题是每个步骤又有许多种不同的移动方法。显然步骤（1）（3）各只有一种移动方法。仔细观察步骤（2）（4）。我们前面定义了“n辆火车依次通过栈产生的排列总数为f(n)”，而步骤（2）恰恰是这个问题的子问题。即步骤二可写为“将a辆火车依次通过栈”，根据前面定义，其移动方案总数为f(a)。同理，步骤(4)的移动方法总数为f(b)。

根据乘法原理，要完成上述工作：

总的方法数tot=步骤(1)的方法数*步骤(2)的方法数*步骤(3)的方法数*步骤(4)的方法数

=1* f(a) * 1* f(b)

=f(a) * f(b)

=f(a) * f(n-a-1)  (因为b=n-a-1)

我们目前已求得将n列火车通过栈，且将位于原车列首位的车头经过移动后位于移动后的车列第a+1位的方法总数, 即f(a)*f(n-a-1)。但是原火车头经过移动后可能处在移动后车列的任意一个位置，即a的取值是任意的。由于共有n辆车，因此移动后原火车头前面的车数可能有0~n-1辆，即0≤a≤n-1。

要完成某个特定的移动方法，a只能取某个特定的值。根据加法原理，将n辆火车依次通过栈的移动总数为：

总的方法数 f(n) = 取a=0的方法数 + 取a=1的方法数 + ... + 取a=n-1的方法数

                = f(0)*f(n-0-1) + f(1)*f(n-1-1) + f(2)*f(n-2-1) + … + f(n-1)*f(n-(n-1)-1)

f(0)=1;

    有了以上递归公式，不难用递推的方法写出程序。

算法一例程如下：

#include<iostream>
#include<cstring>
using namespace std;
long f[19];
int n,i,j;
int main()
{        while(cin>>n)
     {
         memset(f,0,sizeof(f));
         f[0]=1;
         for(i=1;i<=n;i++)
          for(j=0;j<=i-1;j++)
           f[i]+=f[j]*f[i-j-1];
         cout<<f[n]<<endl; 
     }   
}   

算法二：

前面所说的搜索法虽行不通，但它也许能给我们一些提示。如果用深度优先搜索(DFS)，穷举所有可能的移动方法来做的话，当搜索到某个状态下，所能做的移动方法无非有两种：（1）将轨道右方的第一列火车进栈；（2）将栈顶的火车出栈，进入左边的轨道。

设此时轨道右方，栈，轨道左方的火车数分别为a,b,c。我们就能用(a,b,c)表示出当前的状态。显然n=a+b+c,则c=n-a-b。即已知a和b，c就被确定，所以我们可以用(a,b)来作为状态的表示方法。则起始状态为(n,0)，目标状态为(0,0)。又由上面的两种移动方法。我们可类似的得到两种状态转移方式：

             进栈               (a-1,b+1)    (a>0)

(a,b)                                         

             出栈             (a,b-1)      (b>0)

再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动态规划的状态转移方程，我们可写出以下递归式：

f(a-1,b+1) + f(a,b-1)   (a>0,b>0)

f(a,b-1)              (a=0)       (此时只能作出栈操作)

边界值：f(0,0)=1。a+b<=n;

按a的值从0~n划分阶段，亦可通过递推求得f(n,0)的值，即为所求。如果只保存两个阶段进行递推，还可将空间复杂度降为O(n)。这个算法虽然不如算法一简洁，但对于本题来说已经很不错了。而且它在思维难度上要比算法一容易一些。

算法二的例程如下：保存两个阶段进行递推，空间复杂度降为O(n)。

#include<iostream>
#include<cstring>
using namespace std;
long f[19];
int n,a,b;
int main()
{       while(cin>>n)
     {
         memset(f,0,sizeof(f));
         f[0]=1;
        for(b=1;b<=n;b++)
         f[b]=f[b-1];
        for(a=1;a<=n;a++)
         for(b=0;b<=n-a;b++)
           {
               f[b]=f[b+1];
               if(b>0)
               f[b]+=f[b-1];
           } 
         cout<<f[0]<<endl;    
     }   
}   

算法三：

是不是动态规划就是这道题的最优算法呢？其实，本题还隐藏着更为精妙的数学思想：可以设入栈为1，出栈为0。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1…….n的顺序排列，入栈的操作数大于等于出栈的操作数，因此输出序列的总数目等于由左而右扫描n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数方案种数。即为n的Catalan数。

设P_2n为这样所得的数的个数。在2n位上填入n个1的方案数为：

不填1的其余n位自动填以数0。从  

中减去不符合要求的方案数即为所求。不合要求的数指的是从左而右扫描，出现0的累计数超过1的累计数的数。 

    不合要求的数的特征是从左而右扫描时，必然在某一奇数2m+1位上首先出现m+1个0的累计数，和m个1的累计数。 

    此后的2（n－m）－1位上有n－m个1，n－m－1个0。如若把后面这部分2（n－m）－1位，0与1交换，使之成为n－m个0，n－m－1个1，结果得1个由n＋1个0和n－1个1组成的2n位数，即一个不合要求的数对应于一个由n－1个0和n＋1个1组成的一个排列。 

    反过来，任何一个由n＋1个0，n－1个1组成的2n位数，由于0的个数多2个，2n是偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面的部分，令0和1互换，使之成为由n个0和n个1组成的2n位数。即n＋1个0和n－1个1组成的2n位数，必对应于一个不合要求的数。 

    用上述方法建立了由n＋1个0和n－1个1组成的2n位数，与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。

其实，许多看似不相关的问题都和Catalan数有密切关系。例如所有节点数为n的二叉树的个数就恰为上式中的P2n,另外设圆周上2n个点，用n条彼此在圆内部无公共交点的弦连接这些点，共有P2n种连接方式。
在n×n的矩阵中，从(0,0)点走到(n,n)点，规定只能向下或向右走，且不能穿过左上到右下的对角线，共有P2n种走的方式。因此，Catalan数的应用范围很广。

//高精度计算Catalan数
#include<iostream>
#include<cstring>
using namespace std;
const int Max=50;
int a[Max];
void Catalan(int n,int m)
 {
     int i,j,f=0,d=2,x;
     for(i=n-m+1;i<=n;i++)
      {
          for(f=0,j=0;j<=d;j++)
           {
               x=a[j]*i+f;
               f=x/10;
               a[j]=x%10;
           }
           while(a[j]==0)j--;
           d=j+5;  
      }
     for(i=m;i>=2;i--)
      {
          for(f=0,j=d;j>=0;j--)
           {
               x=f*10+a[j];
               a[j]=x/i;
               f=x%i;
           } 
          j=d;while(a[j]==0) j--;
          d=j+1;  
      }  
     j=d;  
     while(a[j]==0)j--;
     /*以下是计算Catalan数*/
     d=j+1;
     i=m+1;
     for(f=0,j=d;j>=0;j--)
           {
               x=f*10+a[j];
               a[j]=x/i;
               f=x%i;
           }
     j=d;  
     while(a[j]==0)j--;     
     for(;j>=0;j--)
      cout<<a[j];
      cout<<endl;      
 }   
int main()
 {  int n0;
     while(cin>>n0)
     {
         memset(a,0,sizeof(a));
         a[0]=1;
         Catalan(2*n0,n0);
     }   
     return 0;
 }