Q10223: How many nodes ?

/*
    Catalan Number:
    1. C(n) = C(n-1)*(4n-2) / (n+1)
    2. C(n) = (2n)! / ( n!(n+1)! )
    3. C(n) = C(0)C(n-1) + C(1)C(n-2) +....+ C(n-1)C(0)

    Run time: 0.000
*/
#include <stdio.h>

int main()
{
    double arr[19];
    unsigned int n;
    int i;

    double prod;


    //  利用第二式寫的
/*
    int twice_n;
    for ( i = 0; i < 19; i++)
    {
        prod = 1;
        twice_n = (i+1)*2;
        for ( j = 0; j < i; )
            prod *= (double)twice_n--/++j;
        prod /= ++j;
        arr[i] = prod;

    }
*/
    //  利用第一式寫的
    arr[0] = 1;
    for ( i = 2; i <= 19; i++)
        arr[i-1] = arr[i-2]*(4*i-2)/(i+1);


    while (scanf("%u", &n) != EOF)
    {
        for ( i = 0; i < 19; i++)
            if (arr[i] == n)
               {printf("%d\n", i+1);  continue;}
    }

    return 0;
}