首页 > 代码库 > UVa 10007 - Count the Trees

UVa 10007 - Count the Trees

题目:统计n个节点的二叉树的个数。

分析:组合,计数,卡特兰数,大整数。

            n个节点的二叉树的形状有Cn个,求不同的树的个数,用卡特兰数乘以全排列n!

说明:打表计算,查询输出,提高效率。

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int C[305][2005] = {0};

int main()
{
	C[1][0] = 1;
	for (int i = 2 ; i < 301 ; ++ i) {
		for (int j = 0 ; j < 2000 ; ++ j)
			C[i][j] += C[i-1][j]*(4*i-2);
		for (int j = 0 ; j < 2000 ; ++ j) {
			C[i][j+1] += C[i][j]/10;
			C[i][j] %= 10;
		}
		for (int j = 1999 ; j >= 0 ; -- j) {
			C[i][j-1] += C[i][j]%(i+1)*10;
			C[i][j] /= (i+1);
		}
		
		for (int j = 0 ; j < 2000 ; ++ j)
			C[i][j] *= i;
		for (int j = 0 ; j < 2000 ; ++ j) {
			C[i][j+1] += C[i][j]/10;
			C[i][j] %= 10;
		}
	}
		
	int n;
	while (cin >> n && n) {
		int end = 1999;
		while (!C[n][end]) -- end;
		while (end >= 0) printf("%d",C[n][end --]);
		printf("\n");
	}
	return 0;
}

UVa 10007 - Count the Trees