Calculer la combinaison pour les grands nombres

Question

J'essaie de calculer si une entrée particulière dans la 100ème ligne du triangle de Pascal est divisible par 3 ou non. Je calcule cela en utilisant la formule nCr où n=100 et r sont les différentes entrées de la 100ème ligne.J'utilise le code ci-dessous pour calculer la combinaison

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

Mais pour des valeurs telles que 100C16, j'obtiens un grand nombre contenant des décimales et un e.J'ai cherché sur Internet et j'ai découvert qu'il y avait en réalité 12 nombres qui ne sont pas divisibles par 3, mais mon programme me donne 63 nombres qui ne sont pas divisibles par 3 sur la 100ème ligne, ce qui est faux. Quelqu'un peut-il me dire ce que je suis faire du mal.

Answer 1

Je suppose que « nCr » est un raccourci pour n-choisissez-r, ou choisissez r parmi N, n'est-ce pas ?

Pour voir si nCr est divisible par trois, vous n'avez pas besoin de calculer le résultat, il vous suffit de déterminer s'il est divisible par 3.Il faut voir combien de fois n!est divisible par 3, et puis combien de fois r !est divisible par 3 et combien de fois (n-r) !est.

C'est vraiment très simple - 1 !n'est pas divisible par 3, 2 !n'est-ce pas, 3 !est divisible une fois.4 !et 5 !sont également divisibles une fois.6 !est divisible deux fois, et 7 aussi !et 8 !.9 !est divisible par 4, et ainsi de suite.Allez jusqu'à n (ou élaborez la formule sans calculer par incréments, ce n'est pas si difficile) et vérifiez.

Clarification - mes études de mathématiques étaient en hébreu, donc "Combien de fois n !est divisible par 3" n'est peut-être pas la manière anglaise appropriée de le dire.Par "n!est divisible par 3 m fois" je veux dire que n!=3^m*k, où k n'est pas du tout divisible par 3.

MODIFIER:Un exemple.Voyons si 10c4 est divisible par 3.

Faisons un petit tableau disant combien de fois k !est divisible par 3 (le k!la colonne est juste à titre de démonstration, vous n'en avez pas réellement besoin pour calculer la colonne de 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 vaut 10 !/ (6!*4!) .

dix!est divisible par 4 (soit 10 != 3^4 * quelque chose qui n’est pas divisible par 3), 6!est divisible 2 fois 4!est divisible 1 fois

Donc 10 !(6!* 4 !) est divisible par 3.Il s'agit en fait de 3*70.

Answer 2

Tout d'abord, vous utilisez des doubles, je ne pense pas que ce soit une bonne idée.Les nombres à virgule flottante donneront des erreurs après un certain temps.

Si le nombre n’augmente pas autant, on peut utiliser la méthode suivante :

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

Mais dans ce cas, cela ne suffit pas.Dans ce cas, on peut utiliser le BigInteger structurer dans 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;
    }

On pourrait dire qu'avec un BigInteger, il n'est pas nécessaire d'entrelacer la division et la multiplication.Cependant, si BigInteger est assez volumineux, les opérations sur les données prendront un certain temps (car le nombre est représenté sous la forme d'un tableau de plusieurs octets).En le gardant petit, on peut éviter de longs temps de calcul.