计算大数时的计数错误(例如 50!)

Question

当我输入像 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。

Answer 1

50! 是一个非常大的数字，需要将近 150 位来表示，long long 数据类型仅提供 64 位。因此，C 无法按照您的方式进行计算；它溢出了。

为此，您可以使用任意精度的算术包库。这种库表示具有可变位数的数字，并提供不会溢出的操作。

gmp -- the Gnu MP Bignum library , 是此类库的一个示例。还有其他人。以下是您可以如何使用 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 位表示。而且，更好的是，当你进行这种计算机运算时，你不必执行实际的除法运算，因为它不在公式中。