9

これはインタビューの質問で、Project Euler Problem 14に関連しているようです。

コラッツ予想によると、次のようにすると

If n is even, replace n by n/2.
If n is odd, replace n by 3n+1.

最終的には 1 になります。

例えば、5 -> 16 -> 8 -> 4 -> 2 -> 1

予想が正しいと仮定すると、各数値には連鎖長があります。つまり、1 になるまでに必要なステップ数です (1 の連鎖長は 0 です)。

ここで、問題に自然数 n、m、および自然数 k が与えられ、1 と n の間のすべての数を見つけるアルゴリズムを与えます。これらの数の連鎖の長さは <= k です。また、これらの数字のチェーンには 1 から m までの数字のみを含める必要があるという制限もあります (つまり、m を超えることはできません)。

簡単な方法は、力ずくでそれを実行し、それをメモ化と組み合わせることです。

インタビュアーは、O(S) 時間アルゴリズムがあると言いました。ここで、S は出力する必要のある数値の数です。

誰がそれが何であるか知っていますか？

4

1 に答える 1

10

プロセスを逆方向に実行することで、O(S) でこれを解決できると思います。k が何であるかがわかっている場合、次のロジックを使用して、最大 k ステップで停止するすべての数値を構築できます。

  • 1 には長さ 0 のチェーンがあります。
  • 数値 z に長さ n の連鎖がある場合、2z には長さ n + 1 の連鎖があります。
  • 数 z が長さ n のチェーンを持ち、z - 1 が 3 の倍数 (0 または 3 以外) で、(z - 1)/3 が奇数の場合、(z - 1) / 3 は次のチェーンを持ちます。長さ n + 1。

これから、1 から始まるシーケンスで数字を構築し始めることができます。

                  1
                  |
                  2
                  |
                  4
                  |
                  8
                  |
                  16
                  | \
                  32 \
                  |   5
                  64  |
                 /|   10
                / 128 | \
               21     20 3

このアルゴリズムは、訪問する必要のある番号とそのチェーンの長さを格納するワーク キューを使用して実行できます。キューに (1, 0) のペアを入力し、要素 (z, n) をキューから連続的に取り出し、(2z, n + 1) と (おそらく) ((z - 1) / 3, n + 1) キューに入れます。これは基本的に、Collat​​z グラフで 1 から始まる幅優先探索を行っています。深さ k で最初の要素が見つかったら、検索を停止します。

コラッツ予想が正しいと仮定すると、この方法で重複が得られることはありません。さらに、この方法で最大 k ステップで到達可能なすべての数値を見つけることができます (これは簡単な帰納的証明ですぐに確認できます)。そして最後に、これには O(S) 時間がかかります。これを確認するには、生成された数値ごとに行われる作業が一定であることに注意してください (最大 2 つの新しい数値をキューから取り出してキューに挿入します)。

お役に立てれば！

于 2011-03-25T20:17:56.600 に答える