HDU ACM Steps：Train Problem II（高精度乘除法+卡特兰数）

程序员文章站 2024-01-15 17:52:04

...

HDU ACM Steps：Train Problem II

题目描述

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.

输入

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.

输出

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

输入样例

1
2
3
10

输出样例

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

思路

递归

对于n个火车(1~n)，它的出栈排列数设为 $f(n)$ 。那么对于n个火车中第k个火车而言，前k-1个火车的出栈排列数： $f(k-1)$ ；后n-k个火车的出栈排列数： $f(n-k)$ .
因此对于确定的k,我们有 $f(k-1)\times f(n-k)\times1$ 种出栈顺序
又因为k是1~n中的一个，即取值范围是1~n
所以 $f(n)= \sum_1^n{f(k-1)\times f(n-k)\times1}$
也就是卡特兰数。

卡特兰数

   卡特兰数是一种经典的组合数，经常出现在各种计算中，其前几项为 : 
   1, 2, 5, 14, 42, 
   132, 429, 1430, 4862, 16796, 
   58786, 208012, 742900, 2674440, 9694845, 
   35357670, 129644790, 477638700, 1767263190, 
   6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 
   4861946401452, ...
   通项公式：f(n)=f(n-1)*(4*n-2)/(n+1);

关于卡特兰数的具体介绍：https://blog.csdn.net/weixin_45718149/article/details/104783194

高精度运算

我们要注意到输出样例中给出的提示：
The result will be very large, so you may not process it by 32-bit integers.
意思是说：数很大，用整数型储存不了。
因此我们就需要用到高精度运算（用字符串表示数字）。在这里只需要用到比较简单的高精度乘除法

高精度的概念

在变量运算对象的数值范围为任何数据类型所无法容纳的情况下，采用整数数组（每一个元素对应一位十进制数，由其下标顺序指明位序号）。
1、采用数串形式输入，并将其转化为整数数组。
2、用一个整数变量记录数据的实际长度（即数组的元素个数）
3、该数组的运算规则如同算术运算。

高精度乘除法

乘法运算
对于任意位置i。进行乘法运算a[i]*k,再加上低位来的进位d，得到的结果除10向高位进位。模10保留在a[i]；（如果不是很理解，可以结合手算）
除法运算则需要注意借位

之后会更新完整的高精度运算

代码

#include<stdio.h>
int n;
int ar[110][110];
void ktl()//  f(n)=f(n-1)*(4*n-2)/(n+1);
{
	/*卡特兰数的前两项*/
	ar[1][0]=1;
    ar[2][0]=1;
    ar[1][1]=1;
    ar[2][1]=2;

	int d,len=1;//d是乘法中的进位、除法中的借位;len是数字的长度
	int i,j;
	for(i=3;i<=100;i++) 
	{
	     d=0;//初始化 
	     
		/*乘法*/
		for(j=1;j<=len;j++)
		{
			d=ar[i-1][j]*(4*i-2)+d;	
			ar[i][j]=d%10;
			d/=10;
		 } 
		 while(d)
		 {
		 	ar[i][++len]=d%10;
		 	d/=10;
		 }
		 
		 /*除法*/
		for(j=len;j>=1;j--)
		{
			d=10*d+ar[i][j];
			ar[i][j]=d/(i+1);
			d=d%(i+1);
		}
		while (!ar[i][len])
		{
			len--;
		}
		ar[i][0]=len;
	}
 } 

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