杭电OJ 1100（C++）

#include <iostream>
using namespace std;

//前19项Catalan数（此处直接打表，也可以根据递推公式 h(n)=h(n-1)*(4*n-2)/(n+1) 计算）
int catalan[19] = { 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,
					208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700 };
//前19项Catalan数的和
int catalan_sum[19] = { 1, 2, 4, 9, 23, 65, 197, 626, 2056, 6918,23714, 82500,
						290512, 1033412, 3707852, 13402697, 48760367, 178405157, 656043857 };

//深度优先搜索，k是所求树中的结点数，n为所求树在k个结点的树中排列的序号（从1开始）
void dfs(int k, int n)
{
	if (k <= 0)
		return;
	if (k == 1)
	{
		cout << "X";
		return;
	}
	int i;
	//Catalan数递推公式 h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0)
	//计算左右子树各有多少个结点
	for (i = 0; i <= k - 1; i++)
	{
		if (n <= catalan[i] * catalan[k - 1 - i])
			break;
		n -= catalan[i] * catalan[k - 1 - i];
	}
	int left = i, right = k - 1 - i; //左右子树的结点数
	n--;
	if (left > 0)
	{
		cout << "(";
		dfs(left, n / catalan[right] + 1);
		cout << ")";
	}
	cout << "X";
	if (right > 0)
	{
		cout << "(";
		dfs(right, n % catalan[right] + 1);
		cout << ")";
	}
}

int main()
{
	int n, num;
	while (cin >> n)
	{
		if (n == 0)
			break;
		n++; //由于Catalan[0]为1，所以需要将序数加1
		num = 0;
		while (n > catalan_sum[num])
			num++;
		if (num > 0)
			dfs(num, n - catalan_sum[num - 1]);
		cout << endl;
	}
	return 0;
}