Collatz猜想相关访谈

Question

这是一个面试问题，似乎与Euler 问题14项目有关

Collatz猜想说，如果您做以下操作

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)填充队列，然后从队列(2z，n+ 1)和(可能)((z-1)/ 3，n+ 1)连续地将一个元素(z，n)排到队列中。这实际上是在Collatz图中进行宽度优先搜索，从1开始。当我们在k深度找到第一个元素时，我们停止搜索。

假设Collatz猜想成立，我们就永远不会得到这样的重复。此外，我们会发现，所有的数字最多可以在k步中这样做(你可以用快速的归纳证明来快速地检查这个数字)。最后，这需要O(S)时间。要查看这一点，请注意，生成的每个数字所做的工作是一个常量(去队列并将最多两个新数字插入到队列中)。

希望这能有所帮助！