本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下。
算法第四版第1.1节习题27日:返回(1.0 - p) *二项(N - 1 k, p) + p *二项(N - 1), k - 1, p);
计算递归调用次数,这里的递归式是怎么来的?
定义:n个独立的是/非试验中成功次数k的离散概率分布,每次实验成功的概率为p,记作B(氮、磷、钾)。
概率公式:p(ξ=K)=C (n, K) * p ^ K * (1 - p) ^ (n - K)
其中C (n, k)=(n - k) !/(k !* (n - k) !),记作ξ~ B(氮、磷),期望:Eξ=np,方差:Dξ=npq,其中q=1 - p。
概率统计里有一条递归公式:
这个便是题目中递归式的来源。
该递推公式来自:C (n, k)=C (n, k) + C (n, k - 1)。实际场景是从n个人选k个,有多少种组合?将着n个人按1 ~ n的顺序排好,假设第k个人没被选中,则需要从剩下的n - 1个人中选k个;第k个选中了,则需要从剩下的n - 1个人中选k - 1个。
公共静态双二项(int, int k、双p) {
数+ +;//记录递归调用次数
如果(N==0,,k==0) {
返回1.0;
}
如果(N & lt;0 | | k & lt;0) {
返回0.0;
}
返回(1.0 - p) *二项(N - 1), k, p) + p *二项(N - 1), k - 1, p);
}
实验结果:
n k p调用次数
10 2467 0.25
20 10 0.25 2435538
30 15 0.25 2440764535
由结果可以看出来这个递归方法需要调用的次数呈几何灾难,n到50就算不下去了。
私有静态长计数=0;
私有静态双[][]米;
私有静态双二项(int, int k,双p) {
数+ +;
如果(N==0,,k==0) {
返回1.0;
}
如果(N & lt;0 | | k & lt;0) {
返回0.0;
}
如果(M [N] [k]==1){//将计算结果存起来,已经计算过的直接拿过来用,无需再递归计算
M [N] [k]=(1.0 - p) *二项(N - 1 k, p) + p *二项(N - 1), k - 1, p);
}
返回M [N] [k];
}
公共静态双二项(int, int k、双p) {
M=新双(N + 1) (k + 1);
for (int i=0;我& lt;=N;我+ +){
for (int j=0;j & lt;=k;j + +) {
M[我][j]=1;
}
}
返回二项(N, k, p);
}
实验结果:
n k p调用次数
10 101 0.25
20 452 0.25
1203年30 15日0.25
50 25 0.25 3204
100 50 5205 - 0.25
由实验结果可以看出调用次数大幅减小,算法可以使用。
事实上,不利用递归,直接计算组合数和阶乘,反而速度更快。
//计算组合数
公共静态双重组合(双N,双k)
{
两分钟=k;
双max=n - k;
双t=0;
双NN=1;
双乐=1;
如果(min> max) {
t=最小;
min=max;
max=t;
}
而(N> max){//分母中较大的那部分阶乘约分不用计算
NN=NN * N;
N——;
}
而(min> 0){//计算较小那部分的阶乘
kk=kk *分钟;
min -;
}
回归神经网络/乐;
}//计算二项分布值
公共静态双二项(int, int k、双p)
{
双=1;
双b=1;
双c=组合(N, k);
在((n - k)在0){//计算(1 - p)的(n - k)次方=* (1 - p);
N——;
}
而(k> 0){//计算p的k次方
b=b * p;
k,;
}
返回c * a * b;
}
实验结果:
n k p二项分布值
10、5、0.25 - 0.058399200439453125
20、10、0.25 - 0.009922275279677706
25岁的50 0.25 - 8.44919466990397 e-5
与前面的算法比对,计算结果是正确的,而且运行速度是非常之快的。
以上就是本文关于Java编程二项分布的递归和非递归实现代码实例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
