二項係数

二項係数を求めるプログラムを、再帰を使ったのと、公式を使ったの二通りで作ってみた。

long product_n2k(long n,long k){
    if (n == 0){
        return 1;
    } else if (n == k) {
        return n;
    }else {
        return n * product_n2k(n - 1, k);
    }
}

long bi_coefficient(long n, long k){
    if (k == 0)
        return 1;
    else
        return product_n2k(n, n - k + 1) / product_n2k(k, 1);
}

公式を使ったバージョン。product_n2kはnからkまでの数をかけた値を返す関数。ここで再帰つかってるじゃんという話もあります。k = 0のときどうすればいいのか分からなくなったので、場合分けしました。if文使わないでうまいこと書けないのかなあ。

long bi_coefficient_r(long n,long k){
    if (n == 0 || k == 0 || n == k){
        return 1;
    }else {
        return bi_coefficient_r(n-1,k-1) + bi_coefficient(n-1,k);
    }
}

パスカルの三角形的に再帰使って書いたバージョン。うーん、簡潔だ……。
(n k) = (n n-k)になることを使ったら計算量が減る気がする。

int main_b(){
    long i,j;
    long a,ar;
    for(i = 0; i < 20 ;i++) {
        for(j = 0; j <= i; j++) {
            cout << i << "," << j << ":";
            cout << (a = bi_coefficient(i, j)) << " ";
            cout << (ar = bi_coefficient_r(i, j)) << " ";

            if ( a == ar) {
                cout << ": OK\n";
            }else{
                cout << ": NG\n";
            }
        }
    }
}

でちゃんと同じ値になるかチェックしてみた。n=12までは良いんですが、n=13ぐらいから、答えがマイナスになったりして、合わなくなってくる。計算途中で大きすぎる値が出るのかなあ。
あとn=100やってみたら、途中でFloating Point Exceptionはいて終了。階乗の力すごい。