进出栈算法分析(数学分析 代码)_第1页
进出栈算法分析(数学分析 代码)_第2页
进出栈算法分析(数学分析 代码)_第3页
进出栈算法分析(数学分析 代码)_第4页
进出栈算法分析(数学分析 代码)_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

2、后,车头处在了第a+1位,车头前有a辆车,车头后有b辆车(a>=0,b>=0)。则n=a+b+1,b=n-a-1。  若要达到上述移动目的,步骤为:(1)    将车头进栈;(2)    将车头后a辆车依次通过栈,移至轨道另一端;(3)    将车头出栈,则车头恰好排在第a+1位;(4)    将轨道右端剩余b辆车依次通过栈,移至轨道另一端;不难证明,移动方案仅此一种。问题是每个步骤又有许多种不同的移动方

3、法。显然步骤(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) 

4、 (因为b=n-a-1)我们目前已求得将n列火车通过栈,且将位于原车列首位的车头经过移动后位于移动后的车列第a+1位的方法总数, 即f(a)*f(n-a-1)。但是原火车头经过移动后可能处在移动后车列的任意一个位置,即a的取值是任意的。由于共有n辆车,因此移动后原火车头前面的车数可能有0n-1辆,即0an-1。要完成某个特定的移动方法,a只能取某个特定的值。根据加法原理,将n辆火车依次通过栈的移动总数为:总的方法数 f(n) = 取a=0的方法数 + 取a=1的方法数 + . + 取a=n-1的方法数&#

5、160;               = 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;l

6、ong f19;int n,i,j;int main()        while(cin>>n)              memset(f,0,sizeof(f);         f0=1;         for(i=1;i<

7、;=n;i+)          for(j=0;j<=i-1;j+)           fi+=fj*fi-j-1;         cout<<fn<<endl;            

8、;   算法二:前面所说的搜索法虽行不通,但它也许能给我们一些提示。如果用深度优先搜索(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)。又由上面的两种移动方法。我们可类似的得到两种状态转移方式:

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

10、0;                                       出栈          &#

11、160;  (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+bn)f(a,b) =     f(a-1,b+1)          

12、; (a>0,b=0)  (此时只能作进栈操作)f(a,b-1)              (a=0)       (此时只能作出栈操作)边界值:f(0,0)=1。a+b<=n;按a的值从0n划分阶段,亦可通过递推求得f(n,0)的值,即为所求。如果只保存两个阶段进行递推,还可将空间复杂度降为O(n)。这个算法虽然不如算法一简洁,但对于本题来说已

13、经很不错了。而且它在思维难度上要比算法一容易一些。算法二的例程如下:保存两个阶段进行递推,空间复杂度降为O(n)。#include<iostream>#include<cstring>using namespace std;long f19;int n,a,b;int main()       while(cin>>n)              memset(f,0,sizeof

14、(f);         f0=1;        for(b=1;b<=n;b+)         fb=fb-1;        for(a=1;a<=n;a+)         for(b=0;b<

15、;=n-a;b+)                          fb=fb+1;               if(b>0)       

16、        fb+=fb-1;                      cout<<f0<<endl;                 &#

17、160;算法三:是不是动态规划就是这道题的最优算法呢?其实,本题还隐藏着更为精妙的数学思想:可以设入栈为1,出栈为0。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1.n的顺序排列,入栈的操作数大于等于出栈的操作数,因此输出序列的总数目等于由左而右扫描n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数方案种数。即为n的Catalan数。设P2n为这样所得的数的个数。在2n位上填入n个1的方案数为:不填1的其余n位自动填以数0。从   中减去不符合要求的方案数即为所求。不合要求的数指的是从左而右扫描,出现0的累计数超过1

18、的累计数的数。     不合要求的数的特征是从左而右扫描时,必然在某一奇数2m+1位上首先出现m+1个0的累计数,和m个1的累计数。     此后的2(nm)1位上有nm个1,nm1个0。如若把后面这部分2(nm)1位,0与1交换,使之成为nm个0,nm1个1,结果得1个由n1个0和n1个1组成的2n位数,即一个不合要求的数对应于一个由n1个0和n1个1组成的一个排列。     反过来,任何一个由n1个0,n1个1组成的2n位数,由于0的个数多2

19、个,2n是偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面的部分,令0和1互换,使之成为由n个0和n个1组成的2n位数。即n1个0和n1个1组成的2n位数,必对应于一个不合要求的数。     用上述方法建立了由n1个0和n1个1组成的2n位数,与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。 其实,许多看似不相关的问题都和Catalan数有密切关系。例如所有节点数为n的二叉树的个数就恰为上式中的P2n,另外设圆周上2n个点,用n条彼此在圆内部无公共交点的弦连接这些点,共有P2n

20、种连接方式。在n×n的矩阵中,从(0,0)点走到(n,n)点,规定只能向下或向右走,且不能穿过左上到右下的对角线,共有P2n种走的方式。因此,Catalan数的应用范围很广。/高精度计算Catalan数#include<iostream>#include<cstring>using namespace std;const int Max=50;int aMax;void Catalan(int n,int m)      int i,j,f=0,d=2,x;     fo

21、r(i=n-m+1;i<=n;i+)                for(f=0,j=0;j<=d;j+)                          x=aj*i+f;  

22、60;            f=x/10;               aj=x%10;                       wh

23、ile(aj=0)j-;           d=j+5;               for(i=m;i>=2;i-)                for(f=0,j=d;j>=0;j-)  &

24、#160;                       x=f*10+aj;               aj=x/i;           

25、;    f=x%i;                       j=d;while(aj=0) j-;          d=j+1;            

26、;     j=d;        while(aj=0)j-;     /*以下是计算Catalan数*/     d=j+1;     i=m+1;     for(f=0,j=d;j>=0;j-)                          x=f*10+aj;               aj=x/i; &

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论