本文研究的主要內(nèi)容是Java編程二項(xiàng)分布的遞歸和非遞歸實(shí)現(xiàn)，具體如下。
問題來源：
算法第四版 第1.1節(jié) 習(xí)題27：return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
計(jì)算遞歸調(diào)用次數(shù)，這里的遞歸式是怎么來的？
二項(xiàng)分布:
定義：n個(gè)獨(dú)立的是/非試驗(yàn)中成功次數(shù)k的離散概率分布，每次實(shí)驗(yàn)成功的概率為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。
概率統(tǒng)計(jì)里有一條遞歸公式：
這個(gè)便是題目中遞歸式的來源。
該遞推公式來自:C(n,k)=C(n-1,k)+C(n-1,k-1)。實(shí)際場(chǎng)景是從n個(gè)人選k個(gè)，有多少種組合？將著n個(gè)人按1~n的順序排好，假設(shè)第k個(gè)人沒被選中，則需要從剩下的n-1個(gè)人中選k個(gè)；第k個(gè)選中了，則需要從剩下的n-1個(gè)人中選k-1個(gè)。
書中二項(xiàng)分布的遞歸實(shí)現(xiàn)：
java/210860.html">java;">public static double binomial(int N, int k, double p) { COUNT++; //記錄遞歸調(diào)用次數(shù) 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); } 實(shí)驗(yàn)結(jié)果：
n k p 調(diào)用次數(shù)10 5 0.25 246720 10 0.25 243553830 15 0.25 2440764535
由結(jié)果可以看出來這個(gè)遞歸方法需要調(diào)用的次數(shù)呈幾何災(zāi)難，n到50就算不下去了。
改進(jìn)的二項(xiàng)分布遞歸實(shí)現(xiàn)：
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) { //將計(jì)算結(jié)果存起來，已經(jīng)計(jì)算過的直接拿過來用，無需再遞歸計(jì)算 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); } 實(shí)驗(yàn)結(jié)果：
n k p 調(diào)用次數(shù)10 5 0.25 10120 10 0.25 45230 15 0.25 120350 25 0.25 3204100 50 0.25 5205
由實(shí)驗(yàn)結(jié)果可以看出調(diào)用次數(shù)大幅減小，算法可以使用。
二項(xiàng)分布的非遞歸實(shí)現(xiàn)：
事實(shí)上，不利用遞歸，直接計(jì)算組合數(shù)和階乘，反而速度更快。
//計(jì)算組合數(shù) 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){//分母中較大的那部分階乘約分不用計(jì)算 NN=NN*N; N--; } while(min>0){//計(jì)算較小那部分的階乘 kk=kk*min; min--; } return NN/kk; } //計(jì)算二項(xiàng)分布值 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){ //計(jì)算(1-p)的(N-k)次方 a=a*(1-p); N--; } while(k>0){ //計(jì)算p的k次方 b=b*p; k--; } return c*a*b; } 實(shí)驗(yàn)結(jié)果：
n k p 二項(xiàng)分布值10, 5, 0.25 0.05839920043945312520, 10, 0.25 0.00992227527967770650, 25, 0.25 8.44919466990397E-5
與前面的算法比對(duì)，計(jì)算結(jié)果是正確的，而且運(yùn)行速度是非常之快的。
總結(jié)
以上就是本文關(guān)于Java編程二項(xiàng)分布的遞歸和非遞歸實(shí)現(xiàn)代碼實(shí)例的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！
新聞熱點(diǎn)
疑難解答
圖片精選
