记忆应该有效

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

好的，我认为你的代码的主要问题是 Collatz 序列可以给你的数字 much 比你在下降到 1 之前开始的数字高。根据到 Project Euler 14，你应该找到低于 1000000 的起始数字，它在达到零之前产生最长的链。但是从 1819 年开始的 Collatz 序列包括大于一百万的数字。因此，您正试图访问 arr[] 中超出范围的元素。

此外，正如评论中所指出的，fun() 函数中的语句 arr[limit]; 没有任何用处。如果你在你的编译器中启用了警告，它可能会标记这个，以及语句 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;
}

记忆应该有效

memoization should have worked

c

algorithm

dynamic

computer-science

memoization