1

私はC でProject Euler #14に取り組んでおり、基本的なアルゴリズムを理解しました。ただし、必要に応じて 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;
}
4

3 に答える 3

3

あなたの元のプログラムは、私のマシンでは 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;
}
于 2010-06-22T16:51:44.627 に答える
1

私の記憶が正しければ、問題は遅いアルゴリズムではありません。現在のアルゴリズムは、PE が要求する処理に対して十分に高速です。問題はオーバーフローです: 数を何度も 3 倍してしまい、最終的には signed int に格納できる最大値を超えてしまうことがあります。unsigned int を使用し、それでもうまくいかない場合 (ただし、うまくいくと確信しています)、64 ビット int ( long long) を使用します。

これは非常に高速に実行されるはずですが、さらに高速に実行したい場合は、他の回答で既に対処されています。

于 2010-06-22T16:00:45.657 に答える
1

これが本質的に使い捨てのプログラムであることを考えると (つまり、実行して答えが得られたら、何年もサポートするつもりはありません :)、シーケンスの長さを保持するグローバル変数を用意することをお勧めします。計算済み:

int lengthfrom[UPTO] = {};

最大サイズが数百万の場合は、一度に RAM に簡単に収まるメガバイトのメモリについて話していることになります。

上記は、起動時に配列をゼロに初期化します。あなたのプログラムでは、反復ごとに、配列にゼロが含まれているかどうかを確認してください。そうであれば、計算を続けなければなりません。そうでない場合は、さらに多くの反復が続くことがわかっているので、これまでに行った回数にそれを追加するだけで完了です. もちろん、新しい結果を配列に格納します。

このサイズの配列にローカル変数を使用する誘惑に駆られないでください: スタックに割り当てようとしますが、十分な大きさにならず、クラッシュする可能性があります。

また、このシーケンスでは値が上下することを覚えておいてください。そのため、プログラムでそれに対処する必要があります (おそらく、配列を UPTO 値よりも長くし、 を使用してassert()、サイズよりも大きいインデックスを保護します)。アレイの）。

于 2010-06-22T15:59:02.710 に答える