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

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

来源：http://blog.csdn.net/u014485485/article/details/77506844