algorithm - 科拉兹猜想相关访谈

这是一个采访问题，似乎与欧拉计划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是我们需要输出的数字数量。

有谁知道这可能是什么？

最佳答案

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

希望这可以帮助!

关于algorithm - 科拉兹猜想相关访谈，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5437445/