link:http://poj.org/problem?id=2084

题意:已知1-2n个数围成一个圈,问用线段分别连接两点,且没有交点,问有多少种。

思路:这题以前老师说过,标准的catalan数,只不过n的范围有点大,所以得用上大数,

自己写了个很烦的,网上有简单版本。

下面是我的代码,仅供参考

code:

#include <stdio.h>
#include <string.h>
char p[110][200];
void add(char a[],char b[],char c[])/*大数相加*/
{
    int i,j,k=0,up=0,x,y,z,t;
    i=strlen(a)-1,j=strlen(b)-1;
    while(i>=0||j>=0)
    {
        if(i<0) x=0;else x=a[i]-'0';
        if(j<0) y=0;else y=b[j]-'0';
        z=x+y+up;
        if(z>9)
        {
            up=1;
            z-=10;
        }
        else
            up=0;
        c[k++]=z+'0';
        i--,j--;
    }
    if(up)
        c[k++]='1';
    c[k]='';
    for(i=0;i<k/2;i++)
    {
        t=c[i];
        c[i]=c[k-i-1];
        c[k-i-1]=t;
    }
}
void mult(char a1[],char b1[],char c[])/*大数相乘*/
{
    if(!strcmp(a1,"0")||!strcmp(b1,"0"))
    {
        c[0]='0';
        return ;
    }
    int i,j,k,lena,lenb;
    char a[1000]={0},b[1000]={0},d[1000]={0};
    lena=strlen(a1);
    lenb=strlen(b1);
    for(i=0;i<lena;i++)
        a[i]=a1[lena-i-1]-'0';
    for(i=0;i<lenb;i++)
        b[i]=b1[lenb-i-1]-'0';
    for(i=0;i<lena;i++)
        for(j=0;j<lenb;j++)
        {
            d[i+j]+=a[i]*b[j];
            d[i+j+1]+=d[i+j]/10;
            d[i+j]%=10;
        }
    k=lena+lenb;
    while(!d[k-1])
        k--;
    for(i=0;i<k;i++)
        c[i]=d[k-i-1]+'0';
    c[i]='';
}
void init()
{
    int i,j;
    char c[200],s[200];
    strcpy(p[0],"1");
    strcpy(p[1],"1");
    strcpy(p[2],"2");
    for(i=3;i<101;i++)
    {
        strcpy(p[i],"0");
        for(j=0;j<i;j++)
        {
            memset(c,0,sizeof(c));
            mult(p[j],p[i-1-j],c);
            add(p[i],c,s);
	    strcpy(p[i],s);
        }
    }
}
int main()
{
    init();
    int n;
    while(scanf("%d",&n)&&(n+1))
        printf("%s\n",p[n]);
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation