随笔-20  评论-16  文章-36  trackbacks-0
2084 Game of Connections

贴这个题目的程序就是因为写了个高精度，题目就是求Catalan数即Cn2n/(n+1)。

#include <iostream>
using namespace std;

int res[500];
int len;
void Plus( int x ){
    int i;
    for( i= 0; i< len; i++ )
        res[i]*= x;
    for( i= 0; i< len; i++ ){
        res[i+1]+= res[i]/10;
        res[i]%= 10;
    }
    for( ; res[len]; len++ ){
        res[len+1]= res[len]/10;
        res[len]%= 10;
    }
}
void Divide( int x ){
    int i, c;
    for( i= len-1, c= res[i]; i> 0; i-- ){
        if( c< x ){
            res[i]= 0;
            c= c*10+ res[i-1];
        }
        else{
            res[i]= c/x;
            c= (c%x)*10+ res[i-1];
        }
    }
    if( c )    res[0]= c/x;
    while( !res[--len] );
    len++;
}
int main(){
    int i, n;
    double rs;
    while( scanf("%d",&n) && n!=-1 ){
        if( n<= 25 ){
            rs= 1;
            for( i= n; i>= 1; i-- )
                rs= rs*(i+n)/i;
            rs/= (n+1);
            printf("%.0lf\n",rs);
            continue;
        }
        memset(res,0,sizeof(res));
        res[0]= 1;
        len= 1;
        for( i= n+2; i<= 2*n-1; i++ )
            Plus( i );
        for( i= 3; i<= n-1; i++ )
            Divide( i );
        while( len-- )    putchar(res[len]+'0');
        putchar('\n');
    }
    return 0;
}
posted on 2009-04-10 18:32 古月残辉 阅读(335) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 古月残辉