1

これは私の教科書の問題です。コラッツ予想(または "3n + 1" 問題) は次のように機能します (自然数 n が与えられます)。

while n > 1 do
    if n is even then
        n = n / 2
    else
        n = 3n + 1
    end if
end while

私はその予想に関するいくつかの論文をざっと読んだことがありますが、それらはすべて私の頭を通り過ぎました。アルゴリズムの複雑さの基本的な理解を得ようとしています。実行される操作の数の上限または下限についてコメントすることは可能ですか (最悪の場合)?

私が推測できた唯一のことは、最良の入力は n = 2^k の形式でなければならないということです (これにより、ops が最も少なくなります)。このことから、最悪の場合の入力は 2 の累乗ではないと言っても過言ではありませんか?

大まかな上限または下限を概念化するのに苦労しています。任意のnについて、実行された計算の最小/最大量についてコメントするには、奇数から偶数への切り替えが多すぎるようです (3 倍に増加するか、2 倍に減少します)。

どんな助けでも大歓迎です。

4

1 に答える 1

3

@Kevin のコメントからの構築: 現時点では、このプロセスがすべての入力に対して終了するかどうかさえわかりません。シーケンスが常に終了する可能性は十分にあり、シーケンスが終了しない入力が存在する可能性も十分にあります。

シーケンスが特定の入力に対して決して終了しない場合、最悪のケースの入力は、シーケンスが決して停止しない任意の数になります。これは必ずしも「任意の非 2 の累乗」と同じではありません。なぜなら、数列が収束する既知の非 2 の累乗が多数あるためです (たとえば、15 など)。

シーケンスがすべての入力に対して常に終了する場合、「最悪の場合」の入力が何であるかを判断するために、その理由をより詳しく調べる必要があります。2 の累乗以外のすべてが最悪の場合の入力になるとは考えにくいです。フィボナッチ数がユークリッドのアルゴリズムに最悪の場合の入力を与える方法と同様に、そのサイズに近い数の最悪の場合の入力を形成する自然数の無限のファミリが存在する可能性があります。

もちろん、これは今のところ知られていません - それが未解決の問題に取り組むことの美しさです!

お役に立てれば！

于 2013-06-03T20:58:07.670 に答える