TIOJ 1107 繁複的二元樹

poao899    15672K    203MS    G++     0.62K     2009-11-13 14:42:42                                     .




唔卡特蘭數

不過不知道這個遞迴式怎麼證明

本來想寫矩陣乘法


是說重載運算子真的這麼慢嗎@@


//*****************************

//1107 Catalan Number

#include<stdio.h>
struct num{
    double real;
    int exp;
    num operator*(int x){
        num t=*this;
        t.real*=x;
        while(t.real>10){
            t.real/=10;
            t.exp++;
        }
        return t;
    }
    num operator/(int x){
        num t=*this;
        t.real/=x;
        while(t.real<1){
            t.real*=10;
            t.exp--;
        }
        return t;
    }
    void set(int x){
        real=x;
        while(real>10){
            real/=10;
            exp++;
        }
    }
}Cat[1000010];
int n;
main(){
    num *cat=Cat;
    cat[0].set(1);
    for(int i=1;i<1000010;i++){
        cat[i]=(cat[i-1]*(4*i-2))/(i+1);
    }
    while(scanf("%d",&n),n){
        printf("%.3lfE+%d\n",cat[n].real,cat[n].exp);
    }
}