Berechnung der Kombination für große Zahlen

Question

Ich versuche zu berechnen, ob ein bestimmter Eintrag in der 100. Zeile des Pascalschen Dreiecks durch 3 teilbar ist oder nicht. Ich berechne dies mithilfe der Formel nCr, wobei n=100 und r die verschiedenen Einträge in der 100. Zeile sind.Ich verwende den folgenden Code, um die Kombination zu berechnen

 public static double Combination(int n, int m, double comb)
    {
        for (int r = -1; ++r < m; )
            comb = comb * (n - r) / (r + 1);
        return comb;
    }

Aber für Werte wie 100C16 erhalte ich eine große Zahl, die Dezimalzahl und e enthält.Ich habe im Internet gesucht und festgestellt, dass es tatsächlich 12 Zahlen gibt, die nicht durch 3 teilbar sind, aber mein Programm gibt mir in der 100. Reihe 63 Zahlen aus, die nicht durch 3 teilbar sind, was falsch ist. Kann mir jemand sagen, was ich bin? falsch machen.

Answer 1

Ich gehe davon aus, dass „nCr“ eine Abkürzung für n-choose-r ist, oder „wähle r aus N“, oder?

Um zu sehen, ob nCr durch drei teilbar ist, müssen Sie das Ergebnis nicht berechnen, sondern nur herausfinden, ob es durch 3 teilbar ist.Man muss sehen, wie oft n!ist durch 3 teilbar, und wie oft ist dann r!ist durch 3 teilbar und wie oft (n-r)!Ist.

Es ist wirklich ganz einfach – 1!ist nicht durch 3, 2 teilbar!ist nicht, 3!ist einmal teilbar.4!und 5!sind auch einmal teilbar.6!ist zweimal teilbar, und 7 auch!und 8!.9!ist viermal teilbar und so weiter.Gehen Sie ganz bis n (oder erarbeiten Sie die Formel, ohne inkrementell zu rechnen, das ist gar nicht so schwer) und überprüfen Sie.

Klarstellung: Mein Mathematikstudium war auf Hebräisch, also „Wie oft n!“ist durch 3 teilbar“ ist möglicherweise nicht die richtige englische Art, es auszudrücken.Von "n!ist durch 3 m teilbar“ Das meine ich so n!=3^m*k, wobei k überhaupt nicht durch 3 teilbar ist.

BEARBEITEN:Ein Beispiel.Mal sehen, ob 10c4 durch 3 teilbar ist.

Lassen Sie uns eine kleine Tabelle erstellen, in der steht, wie oft k!ist durch 3 teilbar (das k!Spalte dient nur zur Veranschaulichung, Sie benötigen sie eigentlich nicht, wenn Sie die Teilbarkeitsspalte berechnen):

  k      k!     Divisibility
  1       1     0
  2       2     0
  3       6     1
  4      24     1
  5     120     1
  6     720     2
  7    5040     2
  8   40320     2
  9  362880     4
 10 3628800     4

10c4 ist 10!/ (6!* 4!) .

10!ist 4-mal teilbar (also 10!= 3^4 * Etwas nicht teilbar von 3), 6!ist teilbar 2 mal 4!ist 1-mal teilbar

Also 10!(6!* 4!) ist durch 3 teilbar.Es ist tatsächlich 3 * 70.

Answer 2

Erstens verwenden Sie Doubles, das halte ich nicht für eine gute Idee.Gleitkommazahlen führen nach einer Weile zu Fehlern.

Wenn die Zahl nicht so groß wird, könnte man die folgende Methode verwenden:

public static long nCr (int m, int n) {
    long tmp = 1;
    int j = 2;
    int k = m-n;
    for(int i = m; i > k; i--) {
        tmp *= i;
        while(j <= n && tmp%j == 0) {
            tmp /= j++;
        }
    }
    while(j <= n) {
        tmp /= j++;
    }
    return tmp;
}

In diesem Fall reicht dies jedoch noch nicht aus.In diesem Fall kann man das verwenden BigInteger strukturieren System.Numerics

public static BigInteger nCr (int m, int n) {
        BigInteger tmp = 1;
        int j = 2;
        int k = m-n;
        for(int i = m; i > k; i--) {
            tmp *= i;
            while(j <= n && tmp%j == 0) {
                tmp /= j++;
            }
        }
        while(j <= n) {
            tmp /= j++;
        }
        return tmp;
    }

Man könnte argumentieren, dass man bei einem BigInteger keine Division und Multiplikation verschachteln muss.Wenn BigInteger jedoch ziemlich groß ist, dauern die Operationen an den Daten einige Zeit (da die Zahl als Array aus einer Anzahl von Bytes dargestellt wird).Indem man es klein hält, kann man lange Berechnungszeiten vermeiden.