杭电ACM1130——How Many Tree？Catalan数

杭电ACM1130——How Many Tree？~~Catalan数

Catalan数的递推公式为：F（n）= F(n - 1) * （4*n - 2）/ （n + 1）；

由于n最大为100；所以需要用数组来存放每一个Catalan数。需要运用大数的运算。

下面的是AC 的代码：

# include <stdio.h>

struct catalan
{
	int length;
	int len[100];
};

struct catalan a[101];
int main()
{
	a[0].length = 1; a[0].len[0] = 1;              //前4个Catalan数
	a[1].length = 1; a[1].len[0] = 1;
	a[2].length = 1; a[2].len[0] = 2;
	a[3].length = 1; a[3].len[0] = 5;
	int i, j, k, num, n, yu, div;
	for(i = 4; i <= 100; i++)
	{
		num = 4 * i - 2; k = 0; yu = 0; div = 0;
		a[i].length = 0;
		for(j = 0; j < a[i - 1].length; j++)       //根据公式，先乘以4 * i - 2；采用一位一存的方法。
		{
			a[i].len[k] = (a[i - 1].len[j] * num + yu) % 10;
			yu = (a[i - 1].len[j] * num + yu) / 10;
			k++;
		}
		while(yu)                                  //余数不为0；继续补上
		{
			a[i].len[k] = yu % 10;
			yu = yu / 10;
			k++;
		}
		a[i].length = k;
		for(j = a[i].length - 1; j >= 0; j--)      //根据公式，除以i + 1，运用的是大数除以一个小数。
		{
			div = div * 10 + a[i].len[j];
			a[i].len[j] = div / (i + 1);
			div = div % (i + 1);
		}
		while(!a[i].len[a[i].length])              //去掉前置的0.
			a[i].length--;
		a[i].length++;
	}
	while(scanf("%d", &n) != EOF)
	{
		for(i = a[n].length - 1; i >= 0; i--)
			printf("%d", a[n].len[i]);
		printf("\n");
	}
	return 0;
}