二项分布概率算法

二项分布是一种伯努利试验。即实验结果只有两个，且互为对立事件。

解决类似问题：做一件事N次，成功的概率为p,问成功K次的概率为多少?

使用分治思想，假设前N-1次已经知道实验结果，现在只要求出第N次实验的概率即可。
所以可以使用递归的算法

public static double binomial(int n,int k,double p){
        if(n==0 && k==0)
            return 1;
        if(n<0||k<0)
            return 0;
        return p*binomial(n-1,k-1,p) +(1-p)*binomial(n-1,k,p);
    }

然而这样速度太慢，有什么办法能代替递归呢？
看看递归在这里起了什么作用。递归存储了每一种情况的概率。现在用数组来代替递归实现。

用a[N][K]表示N次事件发生K次的概率

这里我决定逐层往上地求出a[N][K],
所需要的最低层的概率就是a[i][0]和a[0][j] (i∈[0,N]，j∈[0,K])
而根据实际情况，a[0][j]的概率必为0（事件总数为0，概率肯定为零）
故而只要初始化a[i][0]的的概率即可

for(int i=0;i<=n;++i){
            a[i][0]=Math.pow(1-p,i);
        }

完整代码为：

public static double binomialNonRecursion(int n,int k,double p){
        double[][] a=new double[n+1][k+1];
        for(int i=0;i<=n;++i){
            a[i][0]=Math.pow(1-p,i);
        }
        for(int i=1;i<=n;++i){
            for(int j=1;j<=k;++j){
                a[i][j]=p*a[i-1][j-1]+(1-p)*a[i-1][j];
            }
        }
        return a[n][k];
    }