c - 在c中存储已知序列

Question

我正在研究 Project 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;
}