Javaプログラミングの2つの分布の再帰的および非再帰的な実装コードの例

本研究の主な内容はJavaプログラミングの二項分布の再帰的および非再帰的実現であり、具体的には以下の通りである。
問題のソース:
アルゴリズム第4版第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  

前のアルゴリズムと比較して計算結果は正しく，動作速度は非常に速い。
締め括りをつける
以上が、Javaプログラミングの2つの分布の再帰的かつ非再帰的なコードインスタンスのすべてのコンテンツについてであり、皆さんの役に立つことを願っています。興味のある方は引き続き当駅の他のテーマを参照してください。友達のサポートに感謝します。