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, 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; }
实验结果:
n k p 二项分布值 10, 5, 0.25 0.058399200439453125 20, 10, 0.25 0.009922275279677706 50, 25, 0.25 8.44919466990397E-5
与前面的算法比对,计算结果是正确的,而且运行速度是非常之快的。
总结
以上就是本文关于Java编程二项分布的递归和非递归实现代码实例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
您可能感兴趣的文章:
- Java8使用lambda实现Java的尾递归
- Java编程获取文件列表及子文件目录的方法(非递归)
- java编程之递归算法总结
- Java基于递归解决全排列问题算法示例
- Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】
- Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例
- java递归算法实例分析
- Java递归算法遍历部门代码示例
赞 (0)