algorithm - 科拉兹猜想相关采访

Question

这是一个面试问题，似乎与欧拉计划有关Problem 14

Collat​​z 猜想说，如果您执行以下操作

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是我们需要输出的数字的个数。

有没有人知道它可能是什么？

Answer 1

我认为您可以通过向后运行流程在 O(S) 中解决此问题。如果你知道 k 是什么，那么你可以使用以下逻辑建立最多停在 k 步的所有数字:

• 1 有一个长度为 0 的链。
• 如果数字 z 有一个长度为 n 的链，则 2z 有一个长度为 n + 1 的链。
• 如果数字 z 有一个长度为 n 的链，z - 1 是三的倍数(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 图中进行广度优先搜索。当我们在深度 k 找到第一个元素时，我们停止搜索。

假设 Collat​​z 猜想成立，我们将永远不会以这种方式得到任何重复项。此外，我们将以这种方式找到最多 k 步内可到达的所有数字(您可以使用快速归纳证明快速检查这一点)。最后，这需要 O(S) 时间。要看到这一点，请注意每个生成的数字完成的工作是一个常量(出队并将最多两个新数字插入队列)。

希望这对您有所帮助!