calcolo della combinazione per grandi numeri

Question

Sto cercando di calcolare se una particolare voce nella centesima riga del triangolo di Pascal è divisibile per 3 o meno. Lo sto calcolando utilizzando la formula nCr dove n=100 e r sono le diverse voci nella centesima riga.Sto usando il codice seguente per calcolare la combinazione

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

Ma per valori come 100C16 ottengo un numero elevato contenente decimali ed e.Ho effettuato una ricerca su Internet e ho scoperto che in realtà ci sono 12 numeri che non sono divisibili per 3, ma il mio programma mi fornisce 63 numeri che non sono divisibili per 3 nella centesima riga, il che è sbagliato. Qualcuno può dirmi cos'è che sto? facendo male.

Answer 1

Presumo che "nCr" sia una scorciatoia per n-scegli-r, o scegli r da N, giusto?

Per vedere se nCr è divisibile per tre, non è necessario calcolare il risultato, devi solo capire se è divisibile per 3.Devi vedere quante volte n!è divisibile per 3, e poi quante volte r!è divisibile per 3 e quante volte (n-r)!È.

È davvero abbastanza semplice: 1!non è divisibile per 3, 2!non lo è, 3!è divisibile una volta.4!e 5!sono anche divisibili una volta.6!è divisibile due volte, e lo sono anche 7!e 8!.9!è divisibile 4 volte e così via.Vai fino a n (o elabora la formula senza calcolare in modo incrementale, non è poi così difficile) e controlla.

Chiarimento: i miei studi di matematica erano in ebraico, quindi "Quante volte n!è divisibile per 3" potrebbe non essere il modo corretto di dirlo in inglese.Con "n!è divisibile per 3 m volte" intendo proprio questo n!=3^m*k, dove k non è affatto divisibile per 3.

MODIFICARE:Un esempio.Vediamo se 10c4 è divisibile per 3.

Facciamo una piccola tabella dicendo quante volte k!è divisibile per 3 (il k!è solo a scopo dimostrativo, in realtà non ti serve per calcolare la colonna di divisibilità):

  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 è 10!/ (6!*4!) .

10!è divisibile 4 volte (ovvero 10!= 3^4 * qualcosa di non divisibile per 3), 6!è divisibile 2 volte 4!è divisibile 1 volta

Quindi 10!(6!*4!) è divisibile per 3.In effetti è 3 * 70.

Answer 2

Prima di tutto stai usando doppi, non penso che sia una buona idea.I numeri del punto flottanti forniranno errori dopo un po '.

Se il numero non cresce che enorme è possibile utilizzare il seguente metodo:

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 questo caso, tuttavia questo non è ancora abbastanza.In tal caso si può utilizzare la struttura BigInteger in 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;
    }

.

Potresti discutere che con un biginteger non è necessario interbleave la devozione e la moltiplicazione.Tuttavia, se Biginteger è piuttosto grande, le operazioni sui dati richiederanno un po 'di tempo (perché il numero è rappresentato come una serie di un numero di byte).Mantenendolo piccolo può evitare lunghi tempi di calcolo.