c/c++开发分享在C中避免使用置换(nPr,nCr)函数的整数溢出

我试图做一些与统计相关的function,所以我可以执行一些相关的程序(即:概率的统计计算,生成任意深度的Pascal三角形等)。

我遇到了一个问题,我可能会遇到溢出问题。 例如,如果我想计算nPr(n = 30,p = 1),我知道我可以将它减少到:

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

但是,在使用下面的函数进行计算时,由于整数溢出,我看起来总是会得到无效值。 是否有任何变通方法不需要使用库来支持任意大数字? 我已经在其他关于伽玛函数的post中读过一些内容,但找不到具体的例子。

 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(nr)); } int nPr(int n, int r) { return (factorial(n) / factorial(nr)); } 

    你看起来像是在正确的轨道上,所以你走了:

     #include  #include  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)(nr)/(double)r) * exp(lgamma(n) - lgamma(nr) - 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)(nr)) * exp(lgamma(n) - lgamma(nr))); } } 

    要编译,请执行: gcc -lm myFile.c && ./a.out

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

    我认为你有两个选择:

    如果您不必处理有符号值(并且看起来没有这样做),您可以尝试使用更大的整数类型,例如, unsigned long long 。 如果这还不够,则需要使用支持任意长整数的非标准库。 请注意,使用long long类型需要C99编译器支持(如果使用GCC,可能必须使用-std=c99进行编译)。

    编辑:您可以将更多内容放入一个long double ,在某些系统上为80位。

    我可能会变得很密集,但在我看来, double并且伽玛函数在这里是过度的。

    是否有任何变通方法不需要使用库来支持任意大数字?

    当然有。 你完全知道你在处理什么 – 整数范围的产品。 一系列整数是有限整数列表的特例。 我不知道用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! / (nr)! 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! (nr)!) */ return calculate_list_quotient( make_list(1, n), concatenate_lists(make_list(1, r), make_list(1, nr)) ) 

    请注意,我们从未实际计算过阶乘!

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

     public long combination(long n, long r) { if(r==0) return 1; else { long num = n * combination(n - 1, r - 1); return num/r; } } 

      以上就是c/c++开发分享在C中避免使用置换(nPr,nCr)函数的整数溢出相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注(猴子技术宅)。

      本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

      如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/545984.html

      发表评论

      电子邮件地址不会被公开。 必填项已用*标注