在C中存储已知序列

Question

我正在尝试 Euler项目＃14 在C中，已经弄清楚了基本算法；但是，对于大量数量而言，它的运行速度不大，例如2,000,000；我认为，因为它必须一遍又一遍地生成序列，即使应该有一种存储已知序列的方法（例如，一旦到达16，我们就知道下一个数字是8、4、2 ，然后1）。

我不确定如何使用C的固定长度阵列执行此操作，但是必须有一个很好的方法（我敢肯定，这是非常有效的）。提前致谢。

如果有帮助，这就是我目前拥有的。

#include <stdio.h>
#define UPTO 2000000

int collatzlen(int n);

int main(){
    int i, l=-1, li=-1, c=0;
    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);
    return 1;
}

/* n != 0 */
int collatzlen(int n){
    int len = 0;
    while(n>1) n = (n%2==0 ? n/2 : 3*n+1), len+=1;
    return len;
}

Answer 1

您的原始程序在我的机器上需要3.5秒。这对您来说很慢吗？

我的肮脏和丑陋的版本需要0.3秒。它使用全局数组来存储已经计算的值。并在将来的计算中使用它们。

int collatzlen2(unsigned long n);
static unsigned long array[2000000 + 1];//to store those already calculated

int main()
{
    int i, l=-1, li=-1, c=0;
    int x;
    for(x = 0; x < 2000000 + 1; x++) {
        array[x] = -1;//use -1 to denote not-calculated yet
    }

    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen2(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);

    return 1;
}

int collatzlen2(unsigned long n){
    unsigned long len = 0;
    unsigned long m = n;
    while(n > 1){
        if(n > 2000000 || array[n] == -1){ // outside range or not-calculated yet
            n = (n%2 == 0 ? n/2 : 3*n+1);
            len+=1;
        }
        else{ // if already calculated, use the value
            len += array[n];
            n = 1; // to get out of the while-loop
        }
    }
    array[m] = len;
    return len;
}

Answer 2

鉴于这本质上是一个抛弃程序（即，一旦您运行并得到答案，您就不会支持它多年了:)，我建议有一个全球变量来保留序列的长度已经计算出来：

int lengthfrom[UPTO] = {};

如果您的最大尺寸为几百万，那么我们正在谈论内存的兆字节，这应该很容易立即适合RAM。

以上将在启动时将数组初始化为零。在您的程序中 - 对于每次迭代，请检查数组是否包含零。如果确实如此 - 您必须继续进行计算。如果不是 - 那么您知道继续进行更多的迭代，所以只需将其添加到您到目前为止所做的数字中，您就完成了。当然，然后将新结果存储在阵列中。

不要试图将局部变量用于此大小的数组：它将尝试在堆栈上分配它，这不会足够大，可能会崩溃。

另外 - 请记住，使用此序列，值和下降都会上升，因此您需要在程序中应对它（可能是使用数组比值更长，然后使用一个 assert() 防止索引大于阵列的大小）。

Answer 3

如果我没记错的话，您的问题不是一个缓慢的算法：您现在拥有的算法足以满足您要求您做的事情。问题是溢出：有时您最终将您的数字乘以3次，以至于最终将超过可以存储在签名的INT中的最大值。使用unsigned ints，如果它仍然不起作用（但是我很确定它确实可以），请使用64位ints（long long).

这应该很快运行，但是如果您想更快地这样做，其他答案已经解决了。