計算二項式選擇（n，r）= n！/（r！（nr）！）使用記憶法

二項函數選擇（n，r）= n！/（r！（nr）！）如何寫程序計算10^8 = 1億個隨機二項式，其中N隨機選自1到52，R隨機選擇0到n。計算二項式選擇（n，r）= n！/（r！（nr）！）使用記憶法

需要使用備忘錄或類似的東西來計算O（1）時間的二項式。

我的代碼就是這樣。我知道在每次遞歸中，一個元素可能會計算兩次，我不知道如何通過使用memoization來提高效率。

public static int choose(int n, int k){ 
    if(k == 0) return 1; 

    return (n * choose(n - 1, k - 1))/k; 
}

來源

2017-02-01 Zhmm53

這似乎是一個功課問題。請嘗試編寫代碼以完成要求。然後問你是否有特定的問題。 – Bryce

當N和R很低時，您可能想使用Pascal三角公式，而不是您在問題文本中使用的公式。不過，值C（50,25）不適合'int'，所以需要'long'。 – Gassa

1430二項式（除非我的數學錯誤，但它應該至少接近）和100mio二項式？只需建立一張桌子。或者這是關於二項式本身的計算嗎？並使用'long'來避免溢出。 – Paul

首先，您可能會得到整數數據類型太大的數字...... Proof。

這個想法是，你一步一步...乘以股利隨後的數字，併除以除數隨後的數字。

public class Binom { 

    private long[][] mapped; 

    public Binom(){ 
     mapped = new long[52][52]; 
    } 

    public long binom(int n, int r) { 
     if (r == 0) 
      return 1; 
     if (r == 1) 
      return n; 

     if(r > n-r) 
      r = n-r; 
     long toReturn = 1; 
     for (int i = 1, m = n; i <= r; i++, m--){ 
      toReturn = toReturn*m/i; 
     } 
     return toReturn; 
    } 

    public long[][] getMapped() { 
     return mapped; 
    } 
}

我的風向標：

public class Benchmark { 

    public static void main(String[] args) { 
     long start = System.nanoTime(); 
     Random random = new Random(); 
     int count = 1; 
     Binom binom = new Binom(); 
     long[][] mapped = binom.getMapped(); 
     for (int i = 1; i <= 100_000_000; i++) { 
      int n = 1 + random.nextInt(52); 
      int r = 1 + random.nextInt(n); 
      long result = mapped[n-1][r-1]; 
      if (result != 0) { 
       System.out.println(count++ + ". Binomial for n: " + n + " and r: " + r + " equals " + result + "."); 
      } else { 
       result = binom.binom(n, r); 
       mapped[n-1][r-1] = result; 
       System.out.println(count++ + ". Binomial for n: " + n + " and r: " + r + " equals " + result + "."); 
      } 
     } 
     System.out.println("The whole lasted " + ((System.nanoTime() - start)/1_000_000_000) + " seconds."); 
    } 
}

輸出的結束：

99999995. Binomial for n: 3 and r: 3 equals 1. 
99999996. Binomial for n: 19 and r: 17 equals 171. 
99999997. Binomial for n: 26 and r: 20 equals 230230. 
99999998. Binomial for n: 32 and r: 13 equals 347373600. 
99999999. Binomial for n: 20 and r: 14 equals 38760. 
100000000. Binomial for n: 3 and r: 3 equals 1. 
The whole lasted 342 seconds.

但不打印，將會更快...你只需要計算二項式係數爲那些1378=(52*52/2)對。

來源

2017-02-02 01:02:36

@ruakh，不是微型的，但是[that]（https://dzone.com/articles/abstraction-slows-you-down）。 –

@ruakh，已更正。從'HashMap'切換到'long [] []'。'''int [] []'是不夠的。 –

-1

你可以使用記憶化在這種情況下，有效的將是把你的結果在一個static Map<myObject, int>，其中myObject是n和k值作爲重點和INT的對象的唯一方法是結果。因此，每次在計算或/和返回答案之前，您都必須存儲或查找結果。

來源

2017-02-01 23:55:42

這個答案不是很有幫助（因爲不清楚什麼是'myObject'，而且現在你不能在Java中使用原始類型'int'，而且使用'Map'確實是解決問題的非常低效的方法。 – Shersh

或者只是使用一個數組，因爲計算出的二項式的總數很低，以加速查找。「Map」往往會使事情減慢很多。 – Paul

而且這當然不是唯一的方法 – EJP

計算二項式選擇（n，r）= n！/（r！（nr）！）使用記憶法

回答

相關問題