HDU 1131 Count the Trees 大數計算，hdu1131

HDU 1131 Count the Trees 大數計算，hdu1131

    題目是說給出一個數字，然後以1到這個數為序號當做二叉樹的結點，問總共有幾種組成二叉樹的方式。這個題就是用卡特蘭數算出個數，然後因為有編號，不同的編號對應不同的方式，所以結果是卡特蘭數乘這個數的階乘種方案。因為數字比較大，所以要用高精度的方法也就是用字符數組來做，我分別寫了三個函數，一個算加法，一個算乘法，最後一個打表，等打出表來最後只要判斷一下輸入的數是第幾個，直接輸出就行了，下面是我的代碼，第一次寫高精度的這種大數處理，可能看上去比較繁瑣= =

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char ans[105][1005];
char ads[1005],mus[1005];
char jc[105][1005];
char res[105][1005];

int multiply(char* a1,char* b1)
{
    memset(mus,0,sizeof(mus));
    int i,j,k;
    int len,len1,len2;
    len1=strlen(a1);
    len2=strlen(b1);
    int mut=0,t;
    bool va[1005];
    int s[1005],adt[1005];
    char a[1005],b[1005];
    memset(s,0,sizeof(s));
    memset(adt,0,sizeof(adt));
    memset(va,0,sizeof(va));
    for(i=len1-1,j=0;i>=0;i--)
    {
        a[i]=a1[j];
        j++;
    }
    for(i=len2-1,j=0;i>=0;i--)
    {
        b[i]=b1[j];
        j++;
    }
    for(i=0;i<len1;i++)
    {
        mut=0;
        for(j=0;j<len2;j++)
        {
            t=(a[i]-'0')*(b[j]-'0')+mut;
            mut=0;
            if(t>=10)
            {
                mut=t/10;
                t=t%10;
            }
            s[i+j]=t+s[i+j]+adt[i+j];
            va[i+j]=1;
            adt[i+j]=0;
            if(s[i+j]>=10)
            {
                if(!va[i+j+1])
                    adt[i+j+1]=s[i+j]/10+adt[i+j+1];
                else
                    adt[i+j+1]=s[i+j]/10;
                s[i+j]=s[i+j]%10;
            }
        }
        s[i+j]=mut;
    }
    s[i+j-1]=mut+adt[i+j-1];
    if(s[i+j-1]!=0)
        k=i+j-1;
    else
        k=i+j-2;
    for(i=k,j=0;i>=0;i--)
    {
        mus[i]=(s[j]+'0');
        j++;
    }
    return 0;
}

int additive(char* a,char* b)
{
    memset(ads,0,sizeof(ads));
    int len,len1,len2;
    int i;
    int ad[1005];
    len1=strlen(a);
    len2=strlen(b);
    if(len1==len2)
    {
        len=len1;
    }
    else if(len1>len2)
    {
        len=len1;
        for(i=len;i>=len-len2;i--)
        {
            b[i]=b[i-len+len2];
        }
        for(i=len-len2-1;i>=0;i--)
        {
            b[i]='0';
        }
    }
    else if(len1<len2)
    {
        len=len2;
        for(i=len;i>=len-len1;i--)
        {
            a[i]=a[i-len+len1];
        }
        for(i=len-len1-1;i>=0;i--)
        {
            a[i]='0';
        }
    }
    int t=0;
    for(i=len-1;i>=0;i--)
    {
        ad[i]=(a[i]-'0')+(b[i]-'0')+t;
        t=0;
        if(ad[i]>=10)
        {
            t++;
            ad[i]=ad[i]-10;
            ads[i]=ad[i]+'0';
        }
        else
        {
            ads[i]=ad[i]+'0';
        }
    }
    if(t==1)
    {
        for(i=len;i>=0;i--)
        {
            ads[i]=ads[i-1];
        }
        ads[0]='1';
    }
    return 0;
}

int excel()
{
    ans[0][0]='1';
    ans[1][0]='1';
    char sum[105];
    int n;
    int i,j;
    char t[5];
    memset(sum,0,sizeof(sum));
    for(i=2;i<=100;i++)
    {
        for(j=i;j>0;j--)
        {
            multiply(ans[i-j],ans[j-1]);
            additive(mus,sum);
            strcpy(sum,ads);
        }
        strcpy(ans[i],sum);
        memset(sum,0,sizeof(sum));
    }
    jc[1][0]='1';
    for(i=2;i<100;i++)
    {
        memset(t,0,sizeof(t));
        if(i>=10)
        {
            t[0]=i/10+'0';
            t[1]=i%10+'0';
        }
        else
        {
            t[0]=i+'0';
        }
        multiply(jc[i-1],t);
        strcpy(jc[i],mus);
    }
    multiply(jc[99],"100");
    strcpy(jc[100],mus);
    for(i=1;i<=100;i++)
    {
        multiply(ans[i],jc[i]);
        strcpy(res[i],mus);
        //cout<<"res["<<i<<"]="<<res[i]<<endl;
    }
    return 0;
}

int main()
{
    int n;
    excel();
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        cout<<res[n]<<endl;
    }
    return 0;
}