科拉茨猜想相关采访

Question

这是一个面试问题，似乎与欧拉项目 问题 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 处的第一个元素时，我们停止搜索。

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

希望这有帮助！