尝试 Project Euler #14 时出现分段错误

Question

请不要给我解决方案。告诉我哪里错了。这是我的代码：

#include <stdio.h>

int Collatz_Count(int n);

int cache [10000000] = {0};
int main(void)
{
    int n, answer, count = 0;

    for (n = 1; n < 1000000; ++n)
    {
        if (Collatz_Count(n) > count)
        {
            count = Collatz_Count(n);
            answer = n;
        }
    }

    printf("The number is %d and the count is %d\n", answer, count);

    return 0;
}

int Collatz_Count(int n)
{
    if (n == 1)
    {
        return 0;
    }

    if (n < 1000000)
    {
        if (cache[n] != 0)
        {
            return cache[n];
        }
        else
        {
            if ((n % 2) == 0)
            {
                cache[n] = (1 + Collatz_Count(n / 2));
            }
            else
            {
                cache[n] = (1 + Collatz_Count(3 * n + 1));
            }

            return cache[n];
        }
    }
    else
    {
        if ((n % 2) == 0)
        {
            return (1 + Collatz_Count(n / 2));
        }
        else
        {
            return (1 + Collatz_Count(3 * n + 1));
        }
    }

}

我在执行程序时得到 "Segmentation Fault (Core Dumped)"。刚学会memoization，想应用一下

我尝试设置 'n < 100000' 并且它工作正常但在 'n < 1000000'.

时没有

评论少了真的很抱歉

Answer 1

我运行程序使用gdb。问题是 Collatz_Count 的参数最终超过了整数的有效运行ge，这是未定义的行为。

许多编译器在发生此类溢出时绕回负数，然后尝试使用负索引访问 cache 会出现分段错误。

将 int 替换为 long long 应该可以解决问题。

尝试 Project Euler #14 时出现分段错误

Segmentation fault when trying Project Euler #14

c

memoization