分享
 
 
 

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

王朝other·作者佚名  2006-07-13
窄屏简体版  字體: |||超大  

问题转述:

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

分析:

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

摘要:

算法一

算法二

算法三

算法

递推

递推

Catalan数

时间复杂度

O(n2)

O(n2)

O(n)

空间复杂度

O(n)

O(n2)

O(1)

算法一:

我们不妨直接设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)

(a+b≤n)

f(a,b) = f(a-1,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数。

设P2n为这样所得的数的个数。在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的二叉树的个数就恰为上式中的f(n)。因此,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;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有