HDU1134_catalan_大数运算

题目大意： 给你2n个点要你在一个圈中连接任意两个点，而且直线不可相交。求直线数。1<=n<=100; 解题思路： 典型的catalan大数，输出h（n）即可，但是要做大数处理。 h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1 代码：

#include
using namespace std;
const int MAX_LEN = 10005;

int catalan[101][MAX_LEN];

void multip(int *ans, int b, int &len)
{
    int carry = 0;
    for(int j = 0; j < len; j++)
    {
        int temp = ans[j] * b + carry;
        ans[j] = temp % 10;
        carry = temp / 10;
    }
    while(carry)
    {
        len++;
        ans[len-1] = carry % 10;
        carry /= 10;
    }
}

void division(int *ans, int b, int &len)
{
    int r = 0;
    for(int i = len - 1; i >= 0; i--)
    {
        int temp = ans[i] + r * 10;
        ans[i] = temp / b;
        r = temp % b;
    }
    while(!ans[len-1])
    {
        len--;
    }
    return ;
}

int main(void)
{
    int len[101];
    memset(len, 0, sizeof(len));
    memset(catalan, 0, sizeof(catalan));
    catalan[0][0] = 1;//由catalan的0值开始产生
    len[0] = 1;
    for(int i = 1; i < 101; i++)
    {
        memcpy(catalan[i], catalan[i-1], MAX_LEN * sizeof(int));
        len[i] = len[i-1];//copy前面的

        multip(catalan[i], 4 * i - 2, len[i]);
        division(catalan[i], i + 1, len[i]);
    }
    /*for(int i = 0; i < 20; i++)
    {
    	for(int j = len[i]-1; j >= 0; j--)
    		printf("%d", catalan[i][j]);
    	printf("\n");
    }*/
    int n;
    while(scanf("%d", &n), n >= 0)
    {
        for(int i = len[n] - 1; i >= 0; i--)
        {
            printf("%d", catalan[n][i]);
        }
        printf("\n");
    }
    return 0;
}