Ошибка подсчета при расчете большого числа (например, 50!) - PullRequest
Новая
       21

Ошибка подсчета при расчете большого числа (например, 50!)

1 голос
/ 14 апреля 2019

Мой код работает хорошо, когда я ввожу маленькие цифры, такие как 10, выбираю 2, но когда дело доходит до 50, выбираю 10, его результат неверен, вы можете сказать мне, что здесь не так? 

#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) должно быть 10272278170.

Ответы [ 3 ]

1 голос
/ 14 апреля 2019

50! - это очень большое число, для представления которого требуется почти 150 бит. Тип данных long long предоставляет только 64 бита.Итак, C не может делать вычисления так, как вы это делаете;он переполняется.

Для этой цели вы можете использовать библиотеку арифметических пакетов произвольной точности.Этот вид библиотеки представляет числа с переменным числом битов и предлагает операции, которые не переполняются.

gmp - библиотека Gnu MP Bignum , является примером такой библиотеки.Есть и другие.Вот как вы можете сделать это с помощью gmp.(не отлажено). 

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

Другая возможность: использовать тот факт, что (n!) / (n-m)! равно произведению целых чисел от (m + 1 до n).Например, 50!/ 47! - это 48 * 49 * 50.Это должно во многих случаях сохранять ваши целые числа представимыми в 64 битах.И даже лучше, когда вы выполняете такую ​​компьютерную арифметику, вам не нужно выполнять фактическую операцию деления, потому что она выпадает прямо из формул.

1 голос
/ 14 апреля 2019

вы переполняете емкость long long (и ваш код смешивает long long и int BTW)

вам нужно вычислить 50!что составляет ~ 3,10 ^ 64, что намного выше максимального значения int (~ 2 ^ 9) и максимального значения long long int, что составляет ~ 9,10 ^ 18.Вам нужно использовать специальную библиотеку больших целых чисел или переделать свой алгоритм, чтобы не вычислять переполненные значения (или не использовать большие значения ...)

Кажется, есть алгоритм, который может вычислять комбинацию, которая подходит для длинных длин без переполнения;см .: Расчет суммы комбинаций

0 голосов
/ 14 апреля 2019

Вычисление n выберите k для умеренно больших значений n с формулой по умолчанию, включающей промежуточные результаты, которые превышают диапазон типа long long. Есть 2 решения для решения этой проблемы:

  • используйте пакет bignum, который может работать с такими большими числами
  • Перечислите факторы и исключите делители, чтобы свести вычисления к серии умножений.

Вот модифицированная версия с последним подходом: 

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

Выход: 

50 choose 10 is 10272278170
...