0

我正在尝试做一些与统计相关的功能，以便我可以执行一些相关的程序（即：概率的统计计算，为任意深度生成帕斯卡三角形等）。

我遇到了一个可能要处理溢出的问题。例如，如果我想计算 (n=30,p=1) 的 nPr，我知道我可以将其简化为：

30P1 = 30! / (30 - 1)!
     = 30! / (29)!
     = 30! / 29!
     = 30

但是，当使用下面的函数进行计算时，看起来我总是会因为整数溢出而得到无效值。是否有任何解决方法不需要使用库来支持任意大的数字？我在其他有关 gamma 函数的帖子中阅读了一些内容，但找不到具体的例子。

int factorial(int n) {
   return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}


int nCr(int n, int r) {
   return (nPr(n,r) / factorial(r));
   //return factorial(n) / factorial(r) / factorial(n-r));
}


int nPr(int n, int r) {
   return (factorial(n) / factorial(n-r));
}
4

5 回答 5

3

这是一种不使用伽马函数的计算方法。它依赖于 n_C_r = (n/r) * ((n-1) C (r-1)) 以及对于任何正值 n_C_0 = 1 的事实，因此我们可以使用它编写如下所示的递归函数

public long combination(long n, long r) {
    if(r==0)
        return 1;
    else {
        long num = n * combination(n - 1, r - 1);
        return num/r;
    }
}
于 2012-12-16T05:31:09.977 回答
2

我认为你有两个选择：

  1. 使用大整数库。这样您就不会失去精度（浮点数可能适用于某些情况，但它是一个糟糕的替代品）。

  2. 重组你的函数，这样它们就不会达到很高的中间值。例如是从到factorial(x)/factorial(y)的所有数字的乘积。所以只需编写一个循环并乘以。这样，如果最终结果溢出，您只会得到溢出。y+1x

于 2012-06-13T13:45:35.003 回答
1

如果您不必处理带符号的值（而且您似乎没有这样做），您可以尝试使用更大的整数类型，例如unsigned long long. 如果这还不够，您需要使用支持任意长整数的非标准库。请注意，使用该long long类型需要 C99 编译器支持（如果您使用 GCC，可能必须使用 编译-std=c99）。

编辑：您可能可以更适合 a long double，在某些系统上是 80 位。

于 2012-06-13T13:48:10.123 回答
1

我可能很密集，但在我看来，去doubles 和 gamma 函数在这里是多余的。

是否有任何解决方法不需要使用库来支持任意大的数字？

当然有。你总是清楚地知道你在处理什么——整数范围的乘积。整数范围是有限整数列表的特例。我不知道在 C 中表示列表的惯用方式是什么，所以我将坚持使用 C-ish 伪代码：

make_list(from, to)
    return a list containing from, from+1, ..., to

concatenate_lists(list1, list2)
    return a list with all the elements from list1 and list2

calculate_list_product(list)
    return list[0] * list[1] * ... * list[last]

calculate_list_quotient(numerator_list, denominator_list)
    /* 
    be a bit clever here: form the product of the elements of numerator_list, but
    any time the running product is divisible by an element of denominator_list,
    divide the running product by that element and remove it from consideration
    */

n_P_r(n, r)
   /* nPr is n! / (n-r)! 
      which simplifies to n * n-1 * ... * r+1
       so we can just: */
   return calculate_list_product(make_list(r+1, n)) 

n_C_r(n, r)
   /* nCr is n! / (r! (n-r)!) */
    return calculate_list_quotient(
        make_list(1, n), 
        concatenate_lists(make_list(1, r), make_list(1, n-r))
    )

请注意，我们从不实际计算阶乘！

于 2012-06-14T09:44:34.240 回答
0

你看起来是在正确的轨道上，所以你去：

#include <math.h>
#include <stdio.h>

int nCr(int n, int r) {
   if(r>n) {
      printf("FATAL ERROR"); return 0;
     }       
   if(n==0 || r==0 || n==r) {
      return 1;
   } else {
      return (int)lround( ((double)n/(double)(n-r)/(double)r) * exp(lgamma(n) - lgamma(n-r) - lgamma(r)));
   }
}


int nPr(int n, int r) {
   if(r>n) {printf("FATAL ERROR"; return 0;}
   if(n==0 || r==0) {
      return 1;
   } else {
      if (n==r) {
         r = n - 1;
      }
      return (int)lround( ((double)n/(double)(n-r)) * exp(lgamma(n) - lgamma(n-r)));
   }
}

要编译，请执行以下操作：gcc -lm myFile.c && ./a.out

请注意，结果的准确性受到double数据类型的位深度的限制。你应该能够得到很好的结果，但要注意：用 s 替换int上面的所有 slong long unsigned不一定能保证较大值的准确结果n,r。在某些时候，您仍然需要一些数学库来处理任意大的值，但这应该可以帮助您避免对于较小的输入值。

于 2012-06-13T13:55:33.577 回答