hdu 1023 Train Problem II (catalan 대수) uva 10303 uva 991

hdu 1023：
전형 적 인 입 점 시 카 틀 랜 드 수 문제.
블 루 브리지 컵 결승전 에서 만 나 할 줄 모 르 고 직접 가 져 온 공식 을 계산기 로 눌 렀 다.
당시 에 사용 한 것 은 이 공식 이다.
오늘 사용 한 것 은 이 공식 이 고 대수 곱셈 과 나눗셈 의 표기 법 을 더 한 것 이다.
h（n） = （4 * n - 2 ）/ （n + 1 ）* h（n - 1）
그리고 카 틀 란 드 의 고전 총 결 을 동봉 합 니 다.http://www.cnblogs.com/wuyuegb2312/p/3016878.html
코드:

//h(n) = (4 * n - 2) / (n + 1) * h(n - 1)
#include <stdio.h>

int a[105][105];

void catalan()
{
    a[1][0] = 1;
    a[1][1] = 1;
    a[2][0] = 1;
    a[2][1] = 2;

    int len = 1;

    for (int i = 3; i < 105; i++)
    {
        //  
        int yu = 0;
        for (int j = 1; j <= len; j++)
        {
            int t = a[i - 1][j] * (4 * i - 2) + yu;
            a[i][j] = t % 10;
            yu = t / 10;
        }
        while (yu)
        {
            a[i][++len] = yu % 10;
            yu /= 10;
        }
        //  
        for (int j = len; j > 0; j--)
        {
            int t = a[i][j] + yu * 10;
            a[i][j] = t / (i + 1);
            yu = t % (i + 1);
        }
        //  
        while(!a[i][len])
            len--;
        a[i][0] = len;
    }
}

int main()
{
    int n;
    catalan();
    while (scanf("%d", &n) != EOF)
    {
        for (int i = a[n][0]; i > 0; i--)//a[n][0]        
            printf("%d", a[n][i]);
        printf("
");
    }
    return 0;
}

uva 10303：
제목:
n 개의 숫자 를 주면 몇 가지 이 진 트 리 로 구축 할 수 있 습 니까?
코드:

//h(n) = (4 * n - 2) / (n + 1) * h(n - 1)
#include <stdio.h>

int a[1005][1005];

void catalan()
{
    a[1][0] = 1;
    a[1][1] = 1;
    a[2][0] = 1;
    a[2][1] = 2;

    int len = 1;

    for (int i = 3; i < 1005; i++)
    {
        //  
        int yu = 0;
        for (int j = 1; j <= len; j++)
        {
            int t = a[i - 1][j] * (4 * i - 2) + yu;
            a[i][j] = t % 10;
            yu = t / 10;
        }
        while (yu)
        {
            a[i][++len] = yu % 10;
            yu /= 10;
        }
        //  
        for (int j = len; j > 0; j--)
        {
            int t = a[i][j] + yu * 10;
            a[i][j] = t / (i + 1);
            yu = t % (i + 1);
        }
        //  
        while(!a[i][len])
            len--;
        a[i][0] = len;
    }
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    #endif // LOCAL
    int n;
    catalan();
    while (scanf("%d", &n) != EOF)
    {
        for (int i = a[n][0]; i > 0; i--)//a[n][0]        
            printf("%d", a[n][i]);
        printf("
");
    }
    return 0;
}

991：
제목:
원 내 불 교 현의 개수.
코드:

//h(n) = (4 * n - 2) / (n + 1) * h(n - 1)
#include <stdio.h>

int a[105][105];

void catalan()
{
    a[1][0] = 1;
    a[1][1] = 1;
    a[2][0] = 1;
    a[2][1] = 2;

    int len = 1;

    for (int i = 3; i < 105; i++)
    {
        //  
        int yu = 0;
        for (int j = 1; j <= len; j++)
        {
            int t = a[i - 1][j] * (4 * i - 2) + yu;
            a[i][j] = t % 10;
            yu = t / 10;
        }
        while (yu)
        {
            a[i][++len] = yu % 10;
            yu /= 10;
        }
        //  
        for (int j = len; j > 0; j--)
        {
            int t = a[i][j] + yu * 10;
            a[i][j] = t / (i + 1);
            yu = t % (i + 1);
        }
        //  
        while(!a[i][len])
            len--;
        a[i][0] = len;
    }
}

int main()
{
    int n;
    catalan();
    int ca = 0;
    while (scanf("%d", &n) != EOF)
    {
        if (ca++)
            printf("
");
        for (int i = a[n][0]; i > 0; i--)//a[n][0]        
            printf("%d", a[n][i]);
        printf("
");
    }
    return 0;
}