组合函数的 c 程序中的分段错误（核心转储）错误

Question

#include <stdio.h>
#include <stdlib.h>

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

int combination(int l, int m) {
    return factorial(l)/(factorial(l-m)*factorial(m));
}

int main() {
    int n,r;
    printf("Input taken in form of nCr\n");
    printf("Enter n: ");
    scanf("%d", &n);
    printf("Enter r: ");
    scanf("%d", &r);
    int y = combination(n, r);
    printf("Result: %d", y);

    return 0;
}

试图编写一个简单的代码来计算数学中的组合函数。它适用于小值，基本上工作到 n = 12，并且从 n = 13 开始给出错误的值。同样对于 n = 15 和 r = 2，它 returns 结果 -4。它给出了错误

segmentation fault (core dumped)

对于 n = 40 和 r = 20。我想知道如何解决这个问题以及为什么会这样。

Answer 1

当我运行你的程序在调试器中使用 n = 40 和 r = 20 在一个用 Microsoft Visual Studio 编译的 32 位二进制文件上时，我没有得到分段错误，但我在以下行中得到除以零的错误：

return factorial(l)/(factorial(l-m)*factorial(m));

factorial(l-m) 和 factorial(m) 都计算为 factorial(20)，即 2,192,834,560.

假设sizeof(int) == 4（32位），这个数不能用带符号的int表示。因此，int 溢出，根据官方 C 标准，导致 undefined behavior.

然而，即使行为未定义，我也可以合理地推测会发生以下情况：

由于溢出，数字2,192,834,560将变为-2,102,132,736。这是因为第二个数字对应于Two's complement binary representation中的第一个数字。

由于这个数字在您的代码中与自身相乘（假设 n = 40 和 r = 20），那么相乘的结果将是 4,418,962,039,762,845,696。这个数字肯定放不进有符号的int，所以又出现溢出

这个数字的十六进制表示是0x3D534E9000000000。

由于这个大数放不进32位的整数，所以多余的位全部去掉，相当于对结果进行modulo UINT_MAX + 1 (4,294,967,296).这个模运算的结果是 0.

因此，表达式

factorial(l-m)*factorial(m)

计算为 0。

这意味着行

return factorial(l)/(factorial(l-m)*factorial(m));

会导致被零除异常。

解决处理大数问题的一种方法是使用浮点数而不是整数。这些可以处理非常大的数字而不会溢出，但您可能会失去精度。如果你使用 double 而不是 float，你将不会那么容易丢失精度，即使你这样做，精度损失也会更小。

Answer 2

我猜有 2 个影响相互作用：

您的整数溢出，即 factorial(i) 的值对于足够大的 i 将变为负数，从而导致
您的递归（factorial 调用自身）占用了您所有的堆栈 space。

尝试将 factorial 中的条件从 if(i == 1) 更改为：

int factorial(int i) {
   if(1 == i) {
      return 1;
   } else if(1 > i) {
      return -1;
   }

   return i * factorial(i - 1);

}

这应该可以让您摆脱 SEGFAULT。

对于整数溢出，唯一可能的解决方案是不依赖于 C 整数运算，而是使用一些 bignum 库（或自己编写代码）。

对可能发生的事情的一些解释：

正如@WhozCraig 所指出的，整数最多只能保留 INT_MAX 范围内的数字。然而，factorial(i) 即使是相对较小的数字也会爆炸。但是，C 不会捕获此异常，您的整数将悄无声息地溢出为负数。这意味着在某些时候你开始用负数喂 factorial。

然而，对于每个函数调用，一些数据必须被压入堆栈（通常是 return 地址和局部变量，可能包括函数参数）。此内存将在函数 returns 后释放。这意味着，如果您调用 factorial(40)，如果一切正常，您将消耗 1 次调用 factorial.

的内存量的 40 倍

由于你的factorial没有正确处理负数，它最终会无休止地调用自己，时不时溢出，直到随机命中条件i == 1。从表面上看，在大多数情况下，这不会在您的堆栈耗尽之前发生。

Answer 3

这里是溢出问题。您的结果高于最大 int 值。

13! = 6227020800

超过 INT_MAX (2147483647)。如果你想处理更大的数字，你应该使用其他变量类型（例如 unsigned long long），或者在你的函数中处理溢出以避免内存崩溃。

这里有一个关于 c 语言溢出检查的有趣话题 here。

Also for n = 15 and r = 2, it returns the result -4

当一个变量上溢时，它可以下溢和循环溢出。这就是你得到负值的原因。我不确定，但我认为这是相关的。如果有人可以验证这一点，那就太好了。

Answer 4

13的价值！是 6227020800，它太大而不适合 32 位整数。通过尝试计算这个阶乘或更大的结果导致溢出 32 位 int。有符号整数溢出调用 undefined behavior.

在某些情况下，这种未定义的行为表现为输出错误的值，而在其他情况下则表现为崩溃。 factorial 函数崩溃的情况很可能是传递了一个小于 1 的值，这意味着递归调用将尝试一直向下到 INT_MIN 但在此之前会填满堆栈.

即使更改为 long long 也不足以解决此问题，因为中间结果会溢出。那么你如何解决这个问题？如果您手动计算这些值，则不会将所有数字相乘然后除以两个大数字。你会写出这些因素并抵消等式顶部和底部的项。例如，假设您要计算 ₁₂C₇。你会这样写：

12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
------------------------------------------------
( 5 * 4 * 3 * 2 * 1 ) * (7 * 6 * 5 * 4 * 3 * 2 * 1)

那就抵消掉7！从上到下：

12 * 11 * 10 * 9 * 8 
---------------------
 5 * 4 * 3 * 2

然后取消其他条款：

12 * 11 * 10 * 9 * 8     12 * 11 * 2 * 9 * 8    12 * 11 * 2 * 9 
---------------------  = -------------------- = --------------- =  4 * 11 * 2 * 9
 5 * 4 * 3 * 2              4 * 3 * 2                 3

然后乘以剩下的：

4 * 11 * 2 * 9 = 792

现在在代码中执行此操作。 :) 请务必将所有数据类型更改为 long long，因为 ₄₀C₂₀ 的结果仍然比32 位 int 可以容纳什么。此类型保证至少为 64 位。

组合函数的 c 程序中的分段错误（核心转储）错误

segmentation fault (core dumped) error in a c program for combination function

c

math

coredump

segmentation-fault