5

私は現在解決中です、プロジェクトオイラー問題14：

次の反復シーケンスは、正の整数のセットに対して定義されています。

n → n/2 (n is even)
n → 3n + 1 (n is odd)  

Using the rule above and starting with 13, we generate the following sequence:
               13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1  

Which starting number, under one million, produces the longest chain?

この問題を解決するために、次のアルゴリズムを考案しました。

  • 冗長な計算が多く含まれる番号ごとにシリーズを個別に見つけるのではなく、シリーズを1から逆方向に展開しようとします。つまり、番号から始めて、その前の要素を予測します。
  • 複数のシリーズを生成できるため、リンクリストを使用してすべてのシリーズの最近の数を保存します。（アイデアは、より長いシリーズを持つ要素のみを格納することです。）
  • 指定された制限内のすべての番号が見つかるまで、これをループします。制限の下の最後の番号は、最も長いシリーズになります。

これが私のコードです： 

void series_generate(long num)
{
    long n = 1;
    addhead(n);             //add 1 to list.
    while (n < num) 
    {
            series *p;
            for (p = head; p != NULL; p = p->next)
            {
                    long bf = p->num - 1;
                    if (p->num%2 == 0 && bf != 0 && bf%3 == 0) {
                            bf /= 3;
                            if (bf != 1)
                                    addhead(bf);
                            if (bf < num)
                                    n++; 
                    }
                    p->num *= 2;
                    if ( p->num < num)
                            n++;

            }       
    }       
}

これが完全なコードへのリンクです。 しかし、思った通りの答えが得られません。このアルゴリズムが機能しない理由を誰かが説明できますか？

4

1 に答える 1

9

コラッツツリーをレベルごとに逆方向に構築しようとしています。したがってk、内部ループの-番目の反復の後、リストには（オーバーフローが発生していなくても）kコラッツシーケンスで1に到達するために正確にステップを必要とするすべての数値が含まれます。

このアプローチには2つの重大な問題があります。

  1. レベルのサイズは指数関数的に増加し、サイズは約3レベルごとに2倍になります。100を超えないレベルを保存するのに十分なメモリがありません。
  2. レベルの最大メンバーkは2kです。メンバーに使用されているタイプに応じて、numレベル31、32、63、または64でオーバーフローが発生します。次に、署名されたタイプを使用すると、未定義の動作が発生し、リストに負の数が含まれる可能性があり、すべてがうまくいきません。符号なしの型を使用する場合、リストには0が含まれ、すべてが混乱します。

27は1に到達するために111ステップを必要とするnum > 27ため、常にオーバーフローが発生し、間違った結果が得られます。

于 2012-07-04T18:44:26.567 に答える