Berechnen von Binomen Wählen Sie (n, r) = n!/(R! (Nr)!) Unter Verwendung von Memo

Question

Binomialfunktion Wählen Sie (n, r) = n!/(R! (Nr)!) So schreiben Sie a Programm zur Berechnung von 10^8 = 100 Millionen zufälligen Binomen mit N zufällig ausgewählt von 1 bis 52, und R zufällig ausgewählt 0 bis n.

Sie müssen das Binom in O (1) Zeit berechnen, indem Sie eine Memo-ierung oder etwas Ähnliches verwenden.

Mein Code ist so. Ich weiß, dass bei jeder Rekursion ein Element zweimal berechnen kann, ich weiß nicht, wie man es effizienter machen kann, wenn man Memoization verwendet.

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

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

Answer 1

Zuerst erhalten Sie möglicherweise zu große Zahlen für den ganzzahligen Datentyp ... Proof.

Die Idee ist, dass Sie Schritt für Schritt gehen ... Multiplikation mit nachfolgenden Zahlen von Dividende und Division durch nachfolgende Zahlen von Divisor.

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; 
    } 
} 

Meine Benchmark:

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."); 
    } 
} 

Ausgabe beenden:

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. 

Ohne Druck schneller sein würde ... Sie müssen nur Binomialkoeffizient für jene 1378=(52*52/2) Paare berechnen.

Answer 2

Die einzige Möglichkeit, memoization in diesem Fall effizient Ihre Ergebnisse in einem static Map<myObject, int> wäre nutzen könnten, um bei myObject ein Objekt mit n und k-Werte als Schlüssel und int ist das Ergebnis. Sie müssen also jedes Mal die Ergebnisse speichern oder finden, bevor Sie Ihre Antworten berechnen und/oder zurücksenden.