进出栈算法分析(数学分析+代码)

《进出栈算法分析(数学分析+代码)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、问题转述：求一列共n辆的火车按顺序通过一个栈所产生的排列总数。 分析：这一类组合计数题目显然不能用搜索的方法把所有可能的移动方案都穷举出来再统计总数──这样做时间复杂度极大。所以这道题应当根据问题本身的性质，利用组合数学的原理，将原问题转化为递归形式，找到计算总数的递归方程，再进行计算。  摘要： 算法一算法二算法三算法递推递推Catalan数时间复杂度O(n2)O(n2)O(n)空间复杂度O(n)O(n2)O(1)算法一：我们不妨直接设n辆火车产生的排列总数为f(n)。看看能不能找到一些规律。 如图

2、,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）各只有一种移动方法。仔细观

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列火

4、车通过栈，且将位于原车列首位的车头经过移动后位于移动后的车列第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(

5、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#includeusingnamespacestd;longf[19];intn,i,j;intmain(){       while(cin>>n)    {        memset(f,0,sizeof(f));        f[0]=1

6、;        for(i=1;i<=n;i++)         for(j=0;j<=i-1;j++)          f[i]+=f[j]*f[i-j-1];        cout<

7、方，栈，轨道左方的火车数分别为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)                                                   

8、   出栈             (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)（a+b≤n）f(a,b)=     f(a-1,b+1)           (a>0,b=0)  (此时只能作进栈操作)f(a,b-1)              (a=0)