首页 > 代码库 > UVa 10223 - How many nodes ?

UVa 10223 - How many nodes ?

题目:气你一个整数n,问多少个节点可以生成n个不同的二叉树。

分析:数论,卡特兰数。根据定义即可。

说明:参照http://blog.csdn.net/mobius_strip/article/details/39229895

#include <iostream>
#include <cstdlib>

using namespace std;

long long Cat[100];

int main()
{
	Cat[0] = 1LL;
	for (int i = 1 ; i < 20 ; ++ i)
		Cat[i] = Cat[i-1]*(2*i+1)*2/(i+2);
	
	int n;
	while (cin >> n)
	for (int i = 0 ; i < 20 ; ++ i)
		if (Cat[i] == n) {
			cout << i+1 << endl;
			break;
		}
	return 0;
}


UVa 10223 - How many nodes ?