9

这是一个面试问题，似乎与 Project Euler 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是我们需要输出的数字个数。

有谁知道它可能是什么？

4

1 回答 1

10

我认为您可以通过向后运行该过程在 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) 时间。要看到这一点，请注意每个生成的数字所做的工作是一个常数（出列并将最多两个新数字插入队列）。

希望这可以帮助！

于 2011-03-25T20:17:56.600 回答