我们专注攀枝花网站设计 攀枝花网站制作 攀枝花网站建设
成都网站建设公司服务热线:400-028-6601

网站建设知识

十年网站开发经验 + 多家企业客户 + 靠谱的建站团队

量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决

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

本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下。

大渡口网站制作公司哪家好,找创新互联!从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设等网站项目制作,到程序开发,运营维护。创新互联从2013年开始到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联

问题来源:

算法第四版 第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。

概率统计里有一条递归公式:

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

这个便是题目中递归式的来源。

该递推公式来自: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编程二项分布的递归和非递归实现代码实例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!


网站标题:Java编程二项分布的递归和非递归实现代码实例
标题来源:http://shouzuofang.com/article/iiejge.html

其他资讯