《算法》1.1.27原題：?
二項分布太示。估計用以下代碼計算binomial（100,50,0.25）將會產(chǎn)生的遞歸調(diào)用次數(shù)捧请。
public?static?double?binomial(int?N,?int?k,?double?p){??
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個樣本，每個樣本有a,b兩種狀態(tài)，出現(xiàn)a,b兩種狀態(tài)的概率獨立，且出現(xiàn)a概率為p，二項分布就是計算n個樣本中出現(xiàn)k次a狀態(tài)的概率晨缴。
將原題描述轉(zhuǎn)換成具體例子如下：某化驗有陰性陽性兩種狀態(tài)，出現(xiàn)陰性的概率為0.25峡捡，100個人中击碗，有50個人為陰性的概率是多少。
100個人中棋返，50個人為陰性的概率? =? （一個人為陰性的概率）*（99個人中延都，49個為陰性的概率）+（一個人不為陰性的概率）*（99個人中，50個為陰性的概率）
提取下就是原題中的(1.0?-?p)?*?binomial(N-1,?k,?p)?+?p?*?binomial(N-1,?k-1,?p);??
原題采用遞歸的算法進(jìn)行計算睛竣，存在指數(shù)級的重復(fù)計算量晰房，根據(jù)題目提示采用數(shù)組循環(huán)的方式來計算：
public static int index=0;
public static double[][] binomial(int n,int k,double p){
double[][] result =new double[n+1][k+1];
result[0][0]=1.0;
for(int i=1;i<=n;i++){
result[i][0]=(1-p)*result[i-1][0];
for(int j=1;(j<=k&&j<=i);j++){
index++;
result[i][j]=p*result[i-1][j-1]+(1-p)*result[i-1][j];
}
}
return result;
}
}
其中，二維數(shù)組result下標(biāo)分別代表n,k射沟，當(dāng)k是0時殊者，概率為(1-p)*result(n-1)(0),其余為p*result[n][k-1]+(1-p)*result[n-1][k];
index記錄計算次數(shù)，為：3775
結(jié)果為：4.507310875086383E-8
