代码之家 › 专栏 › 技术社区 › Aaron Yodaiken

将已知序列存储在C中

collatz c

Aaron Yodaiken · 技术社区 · 15 年前

我正在工作 Project Euler #14 在C语言中,我们已经找到了基本的算法;但是,对于大数字来说,它的运行速度是令人难以忍受的,例如2000000;我猜想是因为它必须一次又一次地生成序列,即使应该有一种存储已知序列的方法(例如,一旦我们达到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;
}

3 回复 | 直到 11 年前

yehnan 15 年前

你原来的程序在我的机器上需要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;
}

psmears Touffy 15 年前

考虑到这基本上是一个丢弃程序(即,一旦你运行了它并得到了答案,你将多年不支持它),我建议使用一个全局变量来保存已经计算的序列长度:

int lengthfrom[UPTO] = {};

如果您的最大容量是几百万,那么我们将讨论兆字节的内存,它应该可以很容易地立即放入RAM中。

上面将在启动时将数组初始化为零。在您的程序中-对于每个迭代,检查数组是否包含零。如果是这样,你就得继续计算了。If not - then you know that carrying on would go on for that many more iterations, so just add that to the number you've done so far and you're done. 当然,然后将新结果存储在数组中。

不要试图对这种大小的数组使用局部变量:这将尝试在堆栈上分配它,因为堆栈不够大,可能会崩溃。

另外-记住,使用这个序列,值会上下移动,因此您需要在程序中处理这个问题(可能是通过让数组比上下移动的值长,并使用 assert() 防止索引大于数组大小)。

IVlad 15 年前

如果我没记错的话,你的问题不是一个缓慢的算法:你现在拥有的算法足够快,可以满足体育课的要求。问题是溢出:有时你的数字会被乘以3倍,以至于最终会超过可以存储在有符号整数中的最大值。使用无符号整数,如果仍然不起作用(但我很确定它起作用),使用64位整数。( long long )

这应该运行得很快,但是如果你想做得更快,其他的答案已经解决了这个问题。