站长网 大数据 HDOJ 1023 Train Problem II(卡特兰数+大数乘除法)

HDOJ 1023 Train Problem II(卡特兰数+大数乘除法)

Train Problem II Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7690????Accepted Submission(s): 4140 Problem Description As we all know the Train Problem I,the boss of the Ignatiu

Train Problem II

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 7690????Accepted Submission(s): 4140

Problem Description

As we all know the Train Problem I,the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order,how many orders that all the trains can get out of the railway.

?

Input

The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.

?

Output

For each test case,you should output how many ways that all the trains can get out of the railway.

?

Sample Input

  
  
   
   1 2 3 10
  
  

?

Sample Output

  
  
   
   1 2 5 16796 
   
    
     
     Hint 
     
     The result will be very large,so you may not process it by 32-bit integers.  
   
   
    
  
  

?

题意:n辆火车编号为1~n,按照编号递增的顺序进入火车站(栈模型),出站的情况有多少种?

题解:我们可以把题目看成这样的模型:一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列? ??

  首先,我们设f(n)=序列个数为n的出栈序列种数。同时,我们假定第一个出栈的序数是k。
  第一个出栈的序数k将1~n的序列分成两个序列,其中一个是1~k-1,序列个数为k-1,另外一
个是k+1~n,序列个数是n-k。
  此时,我们若把k视为确定一个序数,那么根据乘法原理,f(n)的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n – k的出栈序列种数,即选择k这个序数的f(n)=f(k-1)×f(n-k)。

而k可以选1到n,所以再根据加法原理,将k取不同值的序列种数相加,得到的总序列种数为:
f(n)=

f(0)f(n-1)
+f(1)f(n-2)+……+f(n-1)f(0)。

那么这个式子到底有什么作用,怎么求和呢?

这个式子就是组合数学中的卡特兰数的递推式。卡特兰数的递推式形态一共有如下几种:

令h(0)=1,h(1)=1,catalan数满足递推式[1] :

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n>=2)

例如:h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

另类递推式[2] ?:

h(n)=h(n-1)*(4*n-2)/(n+1);

递推关系的解为:
h(n)=C(2n,n)/(n+1) (n=0,1,2,…)

递推关系的另类解为:
h(n)=c(2n,n)-c(2n,n-1)(n=0,…)

?

有关卡特兰数的几篇博文Y(^o^)Y:?博文1? ??博文2? ?博文3? ?

代码就用了kuangbin大牛的板子,很好懂,如下:

//h(n)=h(n-1)*(4*n-2)/(n+1);
#include<cstdio>
#include<cstring>
using namespace std;
int a[110][110];
//a[n][0]表示n的卡特兰数的长度,存储是反向的,a[n][1]表示个位数 

void ktl()//打表 
{
	int i,j,len;
	int c,s;
	a[1][0]=1;
	a[1][1]=1;
	a[2][0]=1;
	a[2][1]=2;
	len=1;
	for(i=3;i<101;++i)
	{
		c=0;
		for(j=1;j<=len;++j)
		{
			s=a[i-1][j]*(4*i-2)+c;
			c=s/10;
			a[i][j]=s%10;
		}
		while(c)
		{
			a[i][++len]=c%10;
			c/=10;
		}
		for(j=len;j>0;--j)
		{
			s=a[i][j]+c*10;
			a[i][j]=s/(i+1);
			c=s%(i+1);
		}
		while(!a[i][len])
			len--;
		a[i][0]=len;
	}
}

int main()
{
	ktl();
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=a[n][0];i>0;--i)
			printf("%d",a[n][i]);
		printf("\n");
	}
	return 0;
} 

本文来自网络,不代表站长网立场,转载请注明出处:https://www.zwzz.com.cn/html/shuju/2021/0527/6913.html

作者: dawei

【声明】:站长网内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。
联系我们

联系我们

0577-28828765

在线咨询: QQ交谈

邮箱: xwei067@foxmail.com

工作时间:周一至周五,9:00-17:30,节假日休息

返回顶部