Java编程二项分布的递归和非递归实现代码实例
|
本文研究的主要内容是Java编程二项分布的递归和非递归实现，具体如下。 问题来源： 算法第四版 第1.1节 习题27：return (1.0 - p) * binomial(N - 1,k,p) + p * binomial(N - 1,k - 1,p); 二项分布: 定义：n个独立的是/非试验中成功次数k的离散概率分布，每次实验成功的概率为p，记作B(n,p,k)。 概率公式：P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k) 其中C(n,k) = (n-k) !/(k! * (n-k)!)，记作ξ~B(n,p)，期望：Eξ=np，方差:Dξ=npq，其中q=1-p。 概率统计里有一条递归公式：
这个便是题目中递归式的来源。 该递推公式来自:C(n,k)=C(n-1,k)+C(n-1,k-1)。实际场景是从n个人选k个，有多少种组合？将着n个人按1~n的顺序排好，假设第k个人没被选中，则需要从剩下的n-1个人中选k个；第k个选中了，则需要从剩下的n-1个人中选k-1个。 书中二项分布的递归实现：
public static double binomial(int N,int k,double p) {
COUNT++; //记录递归调用次数
if (N == 0 && k == 0) {
return 1.0;
}
if (N < 0 || k < 0) {
return 0.0;
}
return (1.0 - p) * binomial(N - 1,p);
}
实验结果： n k p 调用次数 10 5 0.25 2467 20 10 0.25 2435538 30 15 0.25 2440764535 由结果可以看出来这个递归方法需要调用的次数呈几何灾难，n到50就算不下去了。 改进的二项分布递归实现：
private static long COUNT = 0;
private static double[][] M;
private static double binomial(int N,double p) {
COUNT++;
if (N == 0 && k == 0) {
return 1.0;
}
if (N < 0 || k < 0) {
return 0.0;
}
if (M[N][k] == -1) { //将计算结果存起来，已经计算过的直接拿过来用，无需再递归计算
M[N][k] = (1.0 - p) * binomial(N - 1,p);
}
return M[N][k];
}
public static double Binomial(int N,double p) {
M = new double[N + 1][k + 1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= k; j++) {
M[i][j] = -1;
}
}
return binomial(N,p);
}
实验结果： n k p 调用次数 10 5 0.25 101 20 10 0.25 452 30 15 0.25 1203 50 25 0.25 3204 100 50 0.25 5205 由实验结果可以看出调用次数大幅减小，算法可以使用。 二项分布的非递归实现： 事实上，不利用递归，直接计算组合数和阶乘，反而速度更快。
//计算组合数
public static double combination(double N,double k)
{
double min = k;
double max = N-k;
double t = 0;
double NN=1;
double kk=1;
if(min>max){
t=min;
min = max;
max=t;
}
while(N>max){//分母中较大的那部分阶乘约分不用计算
NN=NN*N;
N--;
}
while(min>0){//计算较小那部分的阶乘
kk=kk*min;
min--;
}
return NN/kk;
}
//计算二项分布值
public static double binomial(int N,double p)
{
double a=1;
double b=1;
double c =combination(N,k);
while((N-k)>0){ //计算(1-p)的(N-k)次方
a=a*(1-p);
N--;
}
while(k>0){ //计算p的k次方
b=b*p;
k--;
}
return c*a*b;
}
实验结果： n k p 二项分布值 10,5,0.25 0.058399200439453125 20,10,0.25 0.009922275279677706 50,25,0.25 8.44919466990397E-5 与前面的算法比对，计算结果是正确的，而且运行速度是非常之快的。 总结 以上就是本文关于Java编程二项分布的递归和非递归实现代码实例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！ 您可能感兴趣的文章:
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
