Welches ist der bessere Weg, um nCr zu berechnen

Ansatz 1:
C(n,r) = n!/(nr)!r!

Ansatz 2:
Im Buch Kombinatorische Algorithmen von wilfdas habe ich gefunden:
C(n,r) kann geschrieben werden als C(n-1,r) + C(n-1,r-1).

z.B

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

Wie Sie sehen können, benötigt die endgültige Lösung keine Multiplikation. In jeder Form C(n,r), entweder n==r oder r==1.

Hier ist der Beispielcode, den ich implementiert habe:

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

Sehen Ausgang hier.

In Ansatz 2 gibt es überlappende Teilprobleme, bei denen wir Rekursion aufrufen, um dieselben Teilprobleme erneut zu lösen. Wir können es vermeiden, indem wir verwenden Dynamische Programmierung.

Ich möchte wissen, wie C(n,r) besser berechnet werden kann.

Beide Ansätze sparen Zeit, aber der erste ist sehr anfällig Integer-Überlauf.

Ansatz 1:

Dieser Ansatz wird in kürzester Zeit (in höchstens n/2 Iterationen), und die Möglichkeit eines Überlaufs kann reduziert werden, indem die Multiplikationen sorgfältig durchgeführt werden:

long long C(int n, int r) {
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

Dieser Code beginnt mit der Multiplikation des Zählers vom kleineren Ende und als Produkt von Any k aufeinanderfolgende ganze Zahlen ist teilbar durch k!, gibt es kein Teilbarkeitsproblem. Aber die Möglichkeit des Überlaufens ist immer noch da, ein weiterer nützlicher Trick kann das Teilen sein n - r + i und i durch ihre ggT vor der Multiplikation und Division (und still Überlauf möglich).

Ansatz 2:

Bei diesem Ansatz bauen Sie tatsächlich die auf Pascals Dreieck. Der dynamische Ansatz ist viel schneller als der rekursive (der erste ist O(n^2) während der andere exponentiell ist). Sie müssen jedoch verwenden O(n^2) Erinnerung auch.

# define MAX 100 // assuming we need first 100 rows
long long triangle[MAX + 1][MAX + 1];

void makeTriangle() {
    int i, j;

    // initialize the first row
    triangle[0][0] = 1; // C(0, 0) = 1

    for(i = 1; i < MAX; i++) {
        triangle[i][0] = 1; // C(i, 0) = 1
        for(j = 1; j <= i; j++) {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
}

long long C(int n, int r) {
    return triangle[n][r];
}

Dann kannst du jede nachschlagen C(n, r) in O(1) Zeit.

Wenn Sie eine bestimmte benötigen C(n, r) (dh das volle Dreieck wird nicht benötigt), dann kann der Speicherverbrauch vorgenommen werden O(n) indem dieselbe Reihe des Dreiecks von oben nach unten überschrieben wird.

# define MAX 100
long long row[MAX + 1];

int C(int n, int r) {
    int i, j;

    // initialize by the first row
    row[0] = 1; // this is the value of C(0, 0)

    for(i = 1; i <= n; i++) {
        for(j = i; j > 0; j--) {
             // from the recurrence C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
             row[j] += row[j - 1];
        }
    }

    return row[r];
}

Die innere Schleife wird am Ende gestartet, um die Berechnungen zu vereinfachen. Wenn Sie es von Index 0 aus starten, benötigen Sie eine weitere Variable, um den zu überschreibenden Wert zu speichern.

Ich denke, Ihr rekursiver Ansatz sollte effizient funktionieren DP. Aber es wird anfangen, Probleme zu geben, sobald die Einschränkungen zunehmen. Sehen http://www.spoj.pl/problems/MARMORS/

Hier ist die Funktion, die ich in Online-Juroren und Codierungswettbewerben verwende. Es wirkt also recht schnell.

long combi(int n,int k)
{
    long ans=1;
    k=k>n-k?n-k:k;
    int j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}

Es ist eine effiziente Implementierung für Ihren Ansatz Nr. 1

Ihr rekursiver Ansatz ist in Ordnung, aber die Verwendung von DP mit Ihrem Ansatz wird den Aufwand für die Lösung von Teilproblemen wieder reduzieren. Jetzt, da wir bereits zwei Bedingungen haben –

nCr(n,r) = nCr(n-1,r-1) + nCr(n-1,r);

nCr(n,0)=nCr(n,n)=1;

Jetzt können wir ganz einfach eine DP-Lösung erstellen, indem wir unsere Teilergebnisse in einem 2-D-Array speichern.

int dp[max][max];
//Initialise array elements with zero
int nCr(int n, int r)
{
       if(n==r) return dp[n][r] = 1; //Base Case
       if(r==0) return dp[n][r] = 1; //Base Case
       if(r==1) return dp[n][r] = n;
       if(dp[n][r]) return dp[n][r]; // Using Subproblem Result
       return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

Wenn Sie nun weiter optimieren möchten, ist die Primfaktorisierung des Binomialkoeffizienten wahrscheinlich die effizienteste Methode, um ihn zu berechnen, insbesondere wenn die Multiplikation teuer ist.

Die schnellste Methode, die ich kenne, ist Vladimirs Methode. Man vermeidet die Teilung insgesamt, indem man nCr in Primfaktoren zerlegt. Wie Vladimir sagt, können Sie dies ziemlich effizient mit Eratosthenes-Sieb tun. Verwenden Sie auch Kleiner Satz von Fermat um nCr mod MOD zu berechnen (wobei MOD eine Primzahl ist).

Mit dynamischer Programmierung können Sie ganz einfach den nCr finden, hier ist die Lösung

package com.practice.competitive.maths;

import java.util.Scanner;

public class NCR1 {

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int testCase = scanner.nextInt();
            while (testCase-- > 0) {
                int n = scanner.nextInt();
                int r = scanner.nextInt();
                int[][] combination = combination();
                System.out.println(combination[n][r]%1000000007);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static int[][] combination() {
        int combination[][] = new int[1001][1001];
        for (int i = 0; i < 1001; i++)
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i)
                    combination[i][j] = 1;
                else
                    combination[i][j] = combination[i - 1][j - 1] % 1000000007 + combination[i - 1][j] % 1000000007;
            }
        return combination;
    }
}

unsigned long long ans = 1,a=1,b=1;
        int k = r,i=0;
        if (r > (n-r))
            k = n-r;
        for (i = n ; k >=1 ; k--,i--)
        {
            a *= i;
            b *= k;
            if (a%b == 0)
            {
                a = (a/b);
                b=1;
            }
        }
        ans = a/b;