Java編程二項分布的遞歸和非遞歸實現(xiàn)代碼實例
本文研究的主要內(nèi)容是Java編程二項分布的遞歸和非遞歸實現(xiàn)，具體如下。
問題來源：
算法第四版 第1.1節(jié) 習(xí)題27：return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
計算遞歸調(diào)用次數(shù)，這里的遞歸式是怎么來的？
二項分布:
定義：n個獨立的是/非試驗中成功次數(shù)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。
概率統(tǒng)計里有一條遞歸公式：
這個便是題目中遞歸式的來源。
該遞推公式來自:C(n,k)=C(n-1,k)+C(n-1,k-1)。實際場景是從n個人選k個，有多少種組合？將著n個人按1~n的順序排好，假設(shè)第k個人沒被選中，則需要從剩下的n-1個人中選k個；第k個選中了，則需要從剩下的n-1個人中選k-1個。
書中二項分布的遞歸實現(xiàn)：
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);
}
實驗結(jié)果：
n k p 調(diào)用次數(shù) 10 5 0.25 2467 20 10 0.25 2435538 30 15 0.25 2440764535
由結(jié)果可以看出來這個遞歸方法需要調(diào)用的次數(shù)呈幾何災(zāi)難，n到50就算不下去了。
改進(jìn)的二項分布遞歸實現(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) { //將計算結(jié)果存起來，已經(jīng)計算過的直接拿過來用，無需再遞歸計算
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);
}
實驗結(jié)果：
n k p 調(diào)用次數(shù) 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
由實驗結(jié)果可以看出調(diào)用次數(shù)大幅減小，算法可以使用。
二項分布的非遞歸實現(xiàn)：
事實上，不利用遞歸，直接計算組合數(shù)和階乘，反而速度更快。
//計算組合數(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){//分母中較大的那部分階乘約分不用計算
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;
}
實驗結(jié)果：
n k p 二項分布值 10, 5, 0.25 0.058399200439453125 20, 10, 0.25 0.009922275279677706 50, 25, 0.25 8.44919466990397E-5
與前面的算法比對，計算結(jié)果是正確的，而且運行速度是非常之快的。
總結(jié)
以上就是本文關(guān)于Java編程二項分布的遞歸和非遞歸實現(xiàn)代碼實例的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
- Java實現(xiàn)的二叉樹常用操作【前序建樹，前中后遞歸非遞歸遍歷及層序遍歷】
- JAVA實現(xiàn)遍歷文件夾下的所有文件(遞歸調(diào)用和非遞歸調(diào)用)
- java遞歸與非遞歸實現(xiàn)掃描文件夾下所有文件
- JAVA遞歸與非遞歸實現(xiàn)斐波那契數(shù)列
- Java基于棧方式解決漢諾塔問題實例【遞歸與非遞歸算法】
- Java編程獲取文件列表及子文件目錄的方法（非遞歸）
- Java編程用棧來求解漢諾塔問題的代碼實例（非遞歸）
- java數(shù)學(xué)歸納法非遞歸求斐波那契數(shù)列的方法
- java 漢諾塔Hanoi遞歸、非遞歸(仿系統(tǒng)遞歸)和非遞歸規(guī)律 實現(xiàn)代碼
- Java語言實現(xiàn)非遞歸實現(xiàn)樹的前中后序遍歷總結(jié)
相關(guān)文章
Spring和SpringMVC父子容器關(guān)系初窺(小結(jié))
這篇文章主要介紹了Spring和SpringMVC父子容器關(guān)系初窺(小結(jié))，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-01-01
這篇文章主要介紹了java split()使用方法解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-02-02
在同一個類中調(diào)用帶有@Transactional注解的方法示例
這篇文章主要為大家介紹了在同一個類中調(diào)用帶有@Transactional注解的方法示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-04-04
出錯：Error:(3, 27) java: 程序包com.aliyun.odps.udf不存在，遇到這樣的錯誤問題如何解決呢，下面小編給大家?guī)砹薺ava編譯錯誤:程序包不存在的問題及解決方法，感興趣的朋友一起看看吧2023-05-05
這篇文章主要介紹了SpringBoot靜態(tài)資源配置原理(源碼分析)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
這篇文章主要介紹了Java添加Word文本水印和圖片水印，文章圖文講解的很清晰，有對于這方面不懂得同學(xué)可以學(xué)習(xí)下2021-02-02
Java實現(xiàn)世界上最快的排序算法Timsort的示例代碼
Timsort?是一個混合、穩(wěn)定的排序算法，簡單來說就是歸并排序和二分插入排序算法的混合體，號稱世界上最好的排序算法。本文將詳解Timsort算法是定義與實現(xiàn)，需要的可以參考一下2022-07-07
這篇文章主要介紹了JVM致命錯誤日志詳解,本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-06-06
Eclipse中改變默認(rèn)的workspace的方法及說明詳解
eclipse中改變默然的workspace的方法有哪幾種呢？接下來腳本之家小編給大家介紹Eclipse中改變默認(rèn)的workspace的方法及說明，對eclipse改變workspace相關(guān)知識感興趣的朋友一起學(xué)習(xí)吧2016-04-04
Java中轉(zhuǎn)義字符反斜杠\的代替方法及repalceAll內(nèi)涵解析
這篇文章主要介紹了Java中轉(zhuǎn)義字符反斜杠\的代替方法及repalceAll內(nèi)涵解析，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08