Java编程二项分布的递归和非递归实现代码实例

网友投稿 281 2023-02-25


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个http://人选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, k, p) + p * binomial(N - 1, k - 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, int k, 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, k, p) + p * binomial(N - 1, k - 1, p);

}

return M[N][k];

}

public static double Binomial(int N, int k, 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, k, 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,int k,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;

}

实验结果:

ADbtRx

n k p 二项分布值

10, 5, 0.25 0.058399200439453125

20, 10, 0.25 0.00992227527967ADbtRx7706

50, 25, 0.25 8.44919466990397E-5

与前面的算法比对,计算结果是正确的,而且运行速度是非常之快的。

总结

以上就是本文关于Java编程二项分布的递归和非递归实现代码实例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:前端MVVM框架解析之双向绑定
下一篇:如何写api接口文档(怎么写api接口)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~