二項分布アルゴリズム(Java実装)

二項分布アルゴリズム(Java実装)
最近「アルゴリズム(第四版)」を見始めました.これは出会った最初のアルゴリズムです.題目で求められているのはアルゴリズムの再帰の数を推定するだけであるが、異なる二項分布を計算するアルゴリズムをさらに検討した.
二項分布の概要
ここはただ多く展開して、自分の言語で説明します.ある実験で事件が起こる確率は、相互干渉(独立)なしで繰り返し実験を行うと、k回のイベントが発生する確率です.上式はこのブログで検討した問題です.
二項式の公式を利用してV 1.0を実現します.
数学を学ぶ時によく知っている公式は

    public static double myBinomial(int N, int k, double p) {
        long c = N;
        for(int i = N-1; i >= N-k+1; --i)
            c*=i;
        for(int i = 2; i <= k; ++i)
            c/=i;
        double a1 = Math.pow(p, k);
        double a2 = Math.pow(1-p, N-k);
        return c*a1*a2;
    }

改良版V 1.1
バージョンフォーカスV 1.0の一つの問題を改善します.計算する時、二つの方法があります.

この二つの方式の演算量は違っています.具体的な演算の時に選択できます.

    public static double myBinomial2(int N, int k, double p) {
        long c = N;
        if(k < N-k) {
            for(int i = N-1; i >= N-k+1; --i)
                c*=i;
            for(int i = 2; i <= k; ++i)
                c/=i;
        }
        else {
            for(int i = N-1; i >= k+1; --i)
                c*=i;
            for(int i = 2; i <= N-k; ++i)
                c/=i;
        }
        double a1 = Math.pow(p, k);
        double a2 = Math.pow(1-p, N-k);
        return c*a1*a2;
    }

再帰的にV 2.0を実現する
これは例示的なコードで、公式サイトでその基本的な思想を確認することができます.大きな問題を逐次小さな問題に分割する再帰的な思想です.

    public static double binomial1(int N, int k, double p) {
        if (N == 0 && k == 0) return 1.0;
        if (N < 0 || k < 0) return 0.0;
        return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);
    }

再帰的を反復V 2.1に改善する
ここの方法はとても巧妙です.再帰的なステップを逆にすると、「格子を記入する」ということになります.再帰的にトップダウンします.この方法はボトムアップの反復法になります.

public static double binomial2(int N, int k, double p) {
        double[][] b = new double[N+1][k+1];

        // base cases
        for (int i = 0; i <= N; i++)
            b[i][0] = Math.pow(1.0 - p, i);
        b[0][0] = 1.0;

        // recursive formula
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= k; j++) {
                b[i][j] = p * b[i-1][j-1] + (1.0 - p) *b[i-1][j];
                StdOut.printf("%f\t", b[i][j]);
            }
            StdOut.println();
        }
        return b[N][k];
    }

この方法は巧妙であるが、実際の速度は公式法に勝るものではない(複雑さがあり、一部の計算は不要である(一部の「空」は書く必要がない).