1
votes

Erreur de comptage lors du calcul d'un grand nombre (par exemple 50!)

Mon code fonctionne bien lorsque je saisis de petits chiffres comme 10 choisissez 2 , mais quand il s'agit de 50 choisissez 10 , son résultat est faux, pouvez-vous me dire ce qui ne va pas ici?

#include <stdio.h>

long long int factorial(int n);
long long int combn(int n, int k);

int main(void) {
    int n = 0;
    int k = 0;
    printf("Enter n and k:\n");
    scanf("%d %d", &n, &k);
    combn(n, k);
}

long long int combn(int n, int k) {
    long long int C = 0;

    C = factorial(n) / (factorial(k) * factorial(n - k));
    printf("C %d choose %d = %ld\n", n, k, C);
}

long long int factorial(int n) {
    if (n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

combn (50, 10) devrait être 10272278170 code>.

c long-integer factorial

3 commentaires

Avez-vous essayé de déboguer votre code? Le résultat de factorial (n) est-il correct? Le résultat de factorial (k) est-il correct? Le résultat de la factorielle (n - k) est-il correct? Utilisez des variables temporaires pour chaque sous-expression (les appels factoriels et la multiplication) et imprimez-les.

Oh au fait, "% ld" est pour long int . Pour long long int , vous avez besoin de "% lld" . Un spécificateur de format et un argument incompatibles conduisent à un comportement indéfini .

vous n'avez même pas de retour dans votre combn

3 Réponses :

1
votes

vous dépassez la capacité long long (et votre code mélange long long et int BTW)

vous devez en calculer 50! qui est ~ 3.10 ^ 64, jusqu'ici au-dessus de max int (~ 2 ^ 9) et max long long int qui est ~ 9.10 ^ 18. Vous devez utiliser une bibliothèque spéciale de grands entiers ou retravailler votre algorithme pour ne pas calculer les valeurs débordées (ou ne pas utiliser de grandes valeurs ...)

Il semble qu'il existe un algorithme qui peut calculer une combinaison qui correspond à un long long sans déborder; voir: Calcul du nombre de combinaisons

0 commentaires

1
votes

50! est un très grand nombre, prenant près de 150 bits à représenter, le type de données long long ne fournit que 64 bits. Donc, C ne peut pas faire le calcul comme vous le faites;

Vous pouvez utiliser une bibliothèque de packages arithmétiques à précision arbitraire à cette fin. Ce type de bibliothèque représente des nombres avec des nombres variables de bits et propose des opérations qui ne débordent pas.

gmp - la bibliothèque Gnu MP Bignum , est un exemple d'une telle bibliothèque . Il y en a d'autres. Voici comment vous pouvez le faire avec gmp. (non débogué).

#include "gmp.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int main(int argc, char * argv[]){
  uint n;
  uint m;

  mpz_t nn;
  mpz_t mmn;
  mpz_t mmm;
  mpz_t denom;
  mpz_t result;
  char * str;

  if (argc <= 2){
    printf ("Usage: %s <number> <number> \n", argv[0]);
    return 1;
  }
  n = atoi(argv[1]);
  m = atoi(argv[2]);

  mpz_fac_ui (nn,n);          /* nn = n! */
  mpz_fac_ui (mmn,n-m);       /* mmn = (n-m)! */
  mpz_fac_ui (mmm,m);         /* mmm = m! */

  mpz_mul(denom, mmm, mmn);       /* denom = mmn * mmm */
  mpz_fdiv_q(result, nn, denom);  /* result = nn / denom */

  str =  mpz_get_str (null, 10, const mpz_t result);
  printf ("deal %d from %d: %s combinations\n", n,m, str);
  free (str);
  mpz_clear(nn);
  mpz_clear(mmm);
  mpz_clear(mmn);
  mpz_clear(denom);
  mpz_clear(result);

  return 0;
}

Autre possibilité: profitez du fait que (n!) / (nm)! est égal au produit des nombres entiers de (m + 1 à n). Par exemple, 50! / 47! est 48 * 49 * 50 . Cela devrait, dans de nombreux cas, garder vos entiers représentables en 64 bits. Et, encore mieux lorsque vous faites ce type d'arithmétique informatique, vous n'avez pas à effectuer une opération de division réelle car elle ne fait pas partie des formules.

0 commentaires

0
votes

Calculer n choisissez k pour des valeurs moyennement grandes de n avec la formule par défaut implique des résultats intermédiaires qui dépassent la plage de type long long . Il existe 2 solutions pour résoudre ce problème:

utiliser un package bignum capable de traiter un si grand nombre
énumérer les facteurs et éliminer les diviseurs pour réduire le calcul à des séries de multiplications.

Voici une version modifiée avec cette dernière approche:

50 choose 10 is 10272278170

Sortie:

#include <limits.h>
#include <stdio.h>

unsigned long long int combn(int n, int k) {
    if (k < 0 || n < 0 || k > n)
        return 0;

    // minimize computations
    if (k > n - k)
        k = n - k;

    int factors[k];
    // initialize factors of n! / (n - k)!
    for (int i = 0; i < k; i++)
        factors[i] = n - i;

    for (int i = k; i > 1; i--) {
        // find the multiple of i, divide it by i
        for (int j = 0; j < k; j++) {
            if (factors[j] % i == 0) {
                factors[j] /= i;
                break;
            }
        }
    }

    // compute result
    unsigned long long int C = 1;
    for (int i = 0; i < k; i++) {
        if (C > ULLONG_MAX / factors[i])
            return ULLONG_MAX;
        C = C * factors[i];
    }
    return C;
}

int main(void) {
    int n, k;
    printf("Enter n and k: ");
    if (scanf("%d %d", &n, &k) == 2) {
        unsigned long long C = combn(n, k);
        if (C == ULLONG_MAX)
            printf("overflow\n");
        else
            printf("%d choose %d is %llu\n", n, k, C);
    }
    return 0;
}

0 commentaires