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

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

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

2、列火车通过栈，起始车头在车列最前端。经过移动后,车头处在了第a+1位，车头前有a辆车，车头后有b辆车(a>=0,b>=0)。则n=a+b+l,b=n-a-l0车身S1车头车身S2车身S1车头车身S2若要达到上述移动A的，步骤为:(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)的方法数=f(a)*f(b)=f(a)*f(n-a-l)(因为b=n-a-l)我们0前已求得将n列火车通过栈，且将位于原车列首位的车头经

4、过移动后位于移动后的车列第a+1位的方法总数，即f(a)*f(n・a・l)。但是原火车头经过移动后可能处在移动后车列的任意一个位置，即a的取值是任意的。由于共冇n辆车，因此移动后原火车头前面的车数可能有0〜n・l辆，即0WaWn・l。要完成某个特定的移动方法，a只能取某个特定的值。根据加法原理，将n辆火车依次通过栈的移动总数为：总的方法数f(n)=取沪0的方法数+取a=l的方法数+…・+取沪n_l的方法数=f(0)*f(n-0-l)+f(l)*f(n-l-l)+f(2)*f(n・2・l)+...

5、+f(n-l)*f(n-(n-l)-l)f(0)=l;有了以上递归公式，不难用递推的方法写出程序。算法一例程如下：#include#includeusingnamespacestd;longf[19];intmain(){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<

6、前而所说的搜索法虽行不通，但它也许能给我们一些捉示。如果用深度优先搜索(DFS),穷举所有可能的移动方法来做的话，当搜索到某个状态下，所能做的移动方法无非有两种：(1)将轨道右方的第一列火车进栈；(2)将栈顶的火车出栈，进入左边的轨道。设此时轨道右方，栈，轨道左方的火车数分别为a,b,Co我们就能用(a,b,c)表示出当前的状态。显然n=a+b+c,则c=n-a-bo即已知a和b,c就被确定,所以我们可以用(a,b)来作为状态的表示方法。则起始状态为(n,0),目标状态为(0,0)。乂由上面的两

7、种移动方法。我们可类似的得到两种状态转移方式：进栈(a・l,b+l)(a>0)(a,b)出栈(a,b-l)(b>0)再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动态规划的状态转移方程，我们可写出以下递归式：f(a-1,b+1)+f(a,b・1)(a>0,b>0)(a+bWn)f(a,b)=f(a-l,b+l)(a>0,b=0)(此时只能作进栈操作)f(a,b・l)(a=0)(此时只能作出栈操作)边界值：f(0,0)=loa+b<=n;azT按a的值从0

8、〜n划分阶段，亦可通过递推求得f(n,O)的值，即为所求。如果只保存两个阶段进行递推，还可将空间复杂度降为。何。这个算法虽然不如算法一简洁，但对于本题來说已经很不错了。而且它在思维难度上要比算法一容易一些。算法二的例程如下：保存两个阶段进行递推，空间复杂度降为。创。#include#includeusingnamespacestd;longf[19];intn,a,b;intmain(){while(cin>>n){mcmset(f,0,sizeof(f))