删除这个，否则我的大学会有问题，因为其他人会复制代码

Question

int64_t collatz(int64_t a)
{
    if (a < max)
    {
        if(table[a] != 0)
        {
            return table[a];
        }
    }
    int64_t len = 1;
    if (a != 1)
    {
        if (a%2==0)
            len += collatz(a/2);
        else
            len += collatz(a*3+1);
    }
    if (a < max)
    {
        table[a]=len;
    }
    return len;
}

当我删除 collatz 函数中的最后一个 if 语句时，出现分段错误。我无法理解这一点，因为数组大小是 100.000.000 并且我从不允许输入大于该值的数字。我也知道一个数字可能会超出函数内的限制，例如99.999.999 但我很确定高于 100.000.000 的数字永远不会满足函数中的最后一个 if 语句，但如果我以某种方式删除它，我会遇到分段错误。

Answer 1

您的程序中至少存在三个潜在的分段错误来源：

1. 在计算多达 100,000,000 个种子的 Collatz 序列时，将遇到数字 1,092,571,914,585,050。该值大于 2⁶³，因此无法用

   int64_t

   表示。您的程序很可能会将其视为非常大的负数，因此

   table[a]

   将访问内存越界。 （由Fe2O3发现。）
2. 您的

   collatz

   例程是递归的。每个递归调用都使用堆栈空间，因此足够长的链将耗尽堆栈。然而，我认为最长的 Collatz 链达到 100,000,000 个种子是 949 次迭代，你应该有堆栈空间，所以我怀疑这就是原因。 （由dimich发现。）

3. if (a <= max)

   允许

   a

   为

   max

   ，但

   table

   被定义为

   int64_t table[max]

   ，因此

   table[a] = len;

   会溢出数组。这不太可能是问题，因为段错误需要

   table

   恰好在页边界上结束。 （由Chris发现。）

您可以通过在整个程序中将

int64_t

更改为

uint64_t

并将

PRId64

更改为

PRIu64

来解决 1。

您可以通过将

collatz

重写为迭代而不是递归来补救 2。

您可以通过将

a <= max

更改为

a < max

来补救 3。

Answer 2

在

collatz

函数中，您有

table

作为大小为

max

的数组。这意味着最大有效索引是

max - 1

。然而，您测试

a

小于 或等于

max

。这允许越界数组访问，并且可能导致分段错误。

    if (a <= max)
    {
        if(table[a] != 0)
        {
            return table[a];
        }
    }