随笔-20  评论-16  文章-36  trackbacks-0

贴这个题目的程序就是因为写了个高精度,题目就是求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 古月残辉 阅读(359) 评论(0)  编辑 收藏 引用 所属分类: POJ

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