二项分布记录

《算法》1.1.27原题： 

二项分布。估计用以下代码计算binomial（100,50,0.25）将会产生的递归调用次数。

public static double binomial(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) * binomial(N-1, k, p) + p * binomial(N-1, k-1, p);  

}  

二项分布简单的介绍就是计算 抽取n个样本，每个样本有a,b两种状态，出现a,b两种状态的概率独立，且出现a概率为p，二项分布就是计算n个样本中出现k次a状态的概率。

将原题描述转换成具体例子如下：某化验有阴性阳性两种状态，出现阴性的概率为0.25，100个人中，有50个人为阴性的概率是多少。

100个人中，50个人为阴性的概率  =  （一个人为阴性的概率）*（99个人中，49个为阴性的概率）+（一个人不为阴性的概率）*（99个人中，50个为阴性的概率）

提取下就是原题中的(1.0 - p) * binomial(N-1, k, p) + p * binomial(N-1, k-1, p);  

原题采用递归的算法进行计算，存在指数级的重复计算量，根据题目提示采用数组循环的方式来计算：

public static int index=0;

public static double[][] binomial(int n,int k,double p){

double[][] result =new double[n+1][k+1];

result[0][0]=1.0;

for(int i=1;i<=n;i++){

result[i][0]=(1-p)*result[i-1][0];

for(int j=1;(j<=k&&j<=i);j++){

index++;

result[i][j]=p*result[i-1][j-1]+(1-p)*result[i-1][j];

}

}

return result;

}

}

其中，二维数组result下标分别代表n,k，当k是0时，概率为(1-p)*result(n-1)(0),其余为p*result[n][k-1]+(1-p)*result[n-1][k];

index记录计算次数，为：3775

结果为：4.507310875086383E-8