c - 内存应该有效

Question

无需内存，此解决方案适用于 Euler Project 14工作正常!然后通过内存它应该工作得更快......但它几乎停在 i = 1818或附近。多奇怪!努力去理解有什么问题!你能帮我吗？

#include <stdio.h>

#define limit 1000000

int arr[limit];

int fun(long long int i) {
    long long int count = 1;
    long long int num;
    arr[limit];
    num = i;
    while (num > 1) {
        if (arr[num] != NULL) {
            count = count - 1 + arr[num];
            break;
        }
        if (num % 2 == 0) {
            num = num / 2;
            count++;
        } else {
            num = 3 * num + 1;
            count++;
        }
    }
    arr[i] = count;
    return count;
}

int main() {
    long long int i;
    for (i = 2; i < limit; i++) {
        long long int count = fun(i);
        printf("d %lld c: %lld\n", i, count);
    }
    return 0;
}

Answer 1

好的，我认为您的代码的主要问题是 Collat​​z 序列可以为您提供比下降到 1 之前开始的数字大得多的数字。根据 Project Euler 14 ，你应该找到低于 1000000 的起始数字，它在达到零之前产生最长的链。但是从 1819 年开始的 Collat​​z 序列包括大于一百万的数字。结果，您试图访问 arr[] 的元素那是越界的方式。

此外，正如评论中所指出的，声明 arr[limit];在您的 fun()函数没有任何用处。如果您在编译器中启用了警告，它可能会标记这一点，以及语句 if(arr[num]!=NULL) ，比较 void*带整数的指针。

如果你替换你的 while() 的第一条语句用 if (num < limit && arr[num]!=NULL) 阻止，那么你至少应该避免段错误。

您的 main()函数需要重写以找到产生最长链的起始编号，而不是仅仅打印出一百万行数据。

如果你愿意，你可以尝试运行这个:

#include <stdio.h>

#define LIMIT 1000000

int arr[LIMIT] = { 0 };

long fun(long i) {
    long count = 1;
    long num;
    num = i;
    while (num > 1) {
        if (num < LIMIT && arr[num] != 0) {
            count = count - 1 + arr[num];
            break;
        }
        if (num % 2 == 0) {
            num = num / 2;
            count++;
        }
        else {
            num = 3 * num + 1;
            count++;
        }
    }
    arr[i] = count;
    return count;
}

int main(){
    long i, longest=0, maxstart;
    for (i=2; i<LIMIT; i++) {
        long count = fun(i);
        if (count > longest) {
            longest = count;
            maxstart = i;
        }
    }
    printf("%ld\n",maxstart);
    return 0;
}