Cálculo de la combinación para grandes números.

Question

Estoy tratando de calcular si una entrada particular en la primera fila del triángulo de Pascal es divisible por 3 o no. Estoy calculando esto utilizando la fórmula NCR donde n= 100 y R son las diferentes entradas en la fila número 100. Estoy usando el siguiente código para calcular la combinación

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

Pero para valores como 100C16, estoy obteniendo un número grande que contiene decimal y E en él. Busqué en Internet encontré que en realidad hay 12 números que no son divisibles en 3, pero mi programa me da 63 números, que no son divisibles por 3 en 100ª fila, lo que está equivocado. Cualquiera de nosotros, dime, ¿qué es lo que soy?haciendo mal.

Answer 1

Supongo que "NCR" es taquigrafía para N-Cheal-R, o elija R desde N, ¿verdad?

Para ver si NCR es divisible por tres, no necesita calcular el resultado, solo necesita averiguar si es divisible por 3. ¡Tienes que ver cuántas veces n! es divisible por 3, y luego cuántas veces r! Es divisible por 3 y cuántas veces (N-R)! es.

¡Realmente es bastante simple - 1! No es divisible por 3, 2! no es, 3! Es divisible una vez. 4! y 5! También son divisibles una vez. 6! Es divisible dos veces, y también lo son 7! y 8!. 9! Es divisible 4 veces, y así sucesivamente. Vaya hasta N (o trabaje la fórmula sin calcular incrementalmente, no es tan difícil), y verifique.

Aclaración: Mis estudios de matemáticas donde en Hebreo, así que "¿Cuántas veces n! Es divisible por 3" puede no ser la forma de inglés adecuada de decirlo. Por "n! Es divisible por 3 m veces", quiero decir que n!=3^m*k, donde k no es divisible por 3 en absoluto.

Editar: Un ejemplo. Veamos si 10C4 es divisible por 3.

Hagamos una mesa pequeña diciendo cuántas veces K! es divisible por 3 (¡la columna K! La columna es solo para demostrar, no lo necesita en realidad al calcular la columna Divisiblidad):

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

10! es divisible 4 veces (es decir, 10!= 3 ^ 4 * algo no divisible por 3), 6! es divisible 2 veces 4! es divisible 1 tiempo

SO 10! (6! * 4!) Es divisible por 3. De hecho, es de 3 * 70.

Answer 2

En primer lugar, estás usando dobles, no creo que sea una buena idea.Los números de puntos flotantes darán errores después de un tiempo.

Si el número no crecerá ese enorme, podría usar el siguiente método:

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

en este caso, sin embargo, esto aún no es suficiente.En ese caso, uno puede usar la estructura de BigInteger en 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;
    }

Puede argumentar que con un Biginteger, no necesita intercalar la desviación y la multiplicación.Sin embargo, si Biginteger es bastante grande, las operaciones en los datos tomarán algún tiempo (porque el número se representa como una matriz de varios bytes).Al mantenerlo pequeño, uno puede evitar tiempos de cálculo largos.