Trees Made to Order--POJ 1095

时间：2010-09-29 来源：勇泽

1、题目类型：数论、卡特兰数。

2、解题思路：卡特兰数的经典应用；递归输出的灵活运用。

3、注意事项：注意递归函数中第二个参数的处理，刚开始有点难于理解。

4、参考博客：http://blog.csdn.net/scut_lyq00/archive/2009/07/30/4393598.aspx

4、实现方法:

#include <iostream>
using namespace std;
int catalan[19]={1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};
void fun(int n,int k)
{
    int i,sum=0;
    if(1==n)
    {
        putchar('X');
        return;
    }
    for(i=0;k>sum;i++)
        sum+=catalan[i]*catalan[n-i-1];
    i--;
    sum-=catalan[i]*catalan[n-i-1];
    k-=sum;
    if(i)
    {
        putchar('(');
        fun(i,(k-1)/catalan[n-i-1]+1);
        putchar(')');
    }
    putchar('X');
    if(n-i-1)
    {
        putchar('(');
        fun(n-i-1,(k-1)%catalan[n-i-1]+1);
        putchar(')');
    }  
}

int main()
{
    int n,i,sum;
    while(scanf("%d",&n) && n)
    {
        sum=0;
        for(i=1;n>sum;i++)
            sum+=catalan[i];
        i--;
        fun(i,n-sum+catalan[i]);
        putchar('\n');
    }    
    return 0;
}