collatz 函数中的分段错误

Question

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#define max 100000000
int64_t table[max];
int64_t collatz(int64_t a);
int main(int argc,char*argv[])
{
    if (argc !=3)
    {
        printf("ERROR\nUsage: ./collatz {argv1} {argv2}\n");
        return 1;
    }
    int64_t maxlen = 0;
    int64_t num1 = atoi(argv[1]);
    int64_t num2 = atoi(argv[2]);
    if (num1 < 1 || num2 < 1 || num1 > max || num2 > max)
    {
        printf("%"PRId64"\n",maxlen);
        return 2;
    }
    int64_t i;
    for (i=num1;i<=num2;i++)
    {
        int64_t len = collatz(i);
        if (len > maxlen)
        {
            maxlen = len;
        }
    }
    printf("%" PRId64 "\n", maxlen);
    return 0;
}
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

在

collate

函数中，您有

table

作为大小为

max

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

max - 1

。然而，您测试

a

小于 或等于

max

。这允许越界数组访问。

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