本文研究的主要內容是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個。
書中二項分布的遞歸實現：
|
1
2
3
4
5
6
7
8
9
10
|
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); } |
實驗結果：
|
1
2
3
4
|
n k p 調用次數10 5 0.25 246720 10 0.25 243553830 15 0.25 2440764535 |
由結果可以看出來這個遞歸方法需要調用的次數呈幾何災難，n到50就算不下去了。
改進的二項分布遞歸實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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); } |
實驗結果：
|
1
2
3
4
5
6
|
n k p 調用次數10 5 0.25 10120 10 0.25 45230 15 0.25 120350 25 0.25 3204100 50 0.25 5205 |
由實驗結果可以看出調用次數大幅減小，算法可以使用。
二項分布的非遞歸實現：
事實上，不利用遞歸，直接計算組合數和階乘，反而速度更快。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
//計算組合數 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; } |
實驗結果：
|
1
2
3
4
|
n k p 二項分布值10, 5, 0.25 0.05839920043945312520, 10, 0.25 0.00992227527967770650, 25, 0.25 8.44919466990397e-5 |
與前面的算法比對，計算結果是正確的，而且運行速度是非常之快的。
總結
以上就是本文關于java編程二項分布的遞歸和非遞歸實現代碼實例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/u014485485/article/details/77506844
