cálculo da Combinação de um grande número

Question

Eu estou tentando calcular se uma entrada em particular o 100º linha do triângulo de Pascal é divisível por 3 ou não.Eu estou calcular esta usando a fórmula de nCr onde n=100 e r é a entradas diferentes no 100º linha.Eu estou usando o código abaixo, para calcular a combinação

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

Mas para valores como 100C16 eu estou ficando grande número, contendo decimal e e no-lo.Eu procurei na internet descobriu que, na verdade, há 12 números que não são divisíveis por 3, mas o meu programa me dá o número 63, que não são divisíveis por 3 100º linha que é errado.Pode dizer-me o que é que eu estou fazendo de errado.

Answer 1

Eu assumir "nCr" é uma abreviação para n-escolher-r, ou escolha a partir de r N, certo?

Para ver se a nCr é divisível por três, você não precisa calcular o resultado, você só precisa descobrir se é divisível por 3.Você tem que ver quantas vezes n!é divisível por 3 e, em seguida, quantas vezes r!é divisível por 3 e quantas vezes (n-r)!é.

É realmente muito simples - 1!não é divisível por 3, 2!não é, 3!é divisível uma vez.4!e 5!também são divisíveis uma vez.6!é divisível por duas vezes, e por isso são 7!e 8!.9!é divisível por 4 vezes, e assim por diante.Vá todo o caminho até n (ou exercitar-se a fórmula sem calcular de forma incremental, não é tão difícil), e de seleção.

Esclarecimentos - os meus estudos de matemática, onde, em hebraico, de modo que "quantas vezes n!é divisível por 3" pode não ser o inglês adequada forma de dizê-lo.Por "n!é divisível por 3 m vezes" eu quero dizer que n!=3^m*k, onde k não é divisível por 3 a todos.

EDITAR:Um exemplo.Vamos ver se 10c4 é divisível por 3.

Vamos fazer uma pequena mesa dizendo quantas vezes k!é divisível por 3 (k!a coluna é apenas para demonstração, você realmente não precisa disso quando o cálculo do divisiblity coluna):

  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!é divisível por 4 vezes (o que significa 10!= 3^4 * algo que não é divisível por 3), 6!é divisível por 2 vezes 4!é divisível por 1 hora

Então 10!(6!* 4!) é divisível por 3.Ele é, na verdade, 3 * 70.

Answer 2

Primeiro de tudo você estiver usando duplas, eu não acho que é uma boa idéia.Números em ponto flutuante vai dar erros depois de um tempo.

Se o número não vai crescer enorme, pode-se usar o seguinte 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;
}

Neste caso, no entanto, isso ainda não é suficiente.Nesse caso pode-se usar a BigInteger estrutura em 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;
    }

Você poderia argumentar que, com um BigInteger que não é preciso intercalar devision e multiplicação.No entanto, se BigInteger é muito grande, as operações sobre os dados, vai levar algum tempo (porque o número é representado como uma matriz de um número de bytes).Por mantê-la pequena, pode-se evitar o cálculo longo dos tempos.