Collat​​z猜想相关采访

Question

这是一个采访问题,似乎与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是我们需要输出的数字.

有谁知道它可能是什么？

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)时间.要看到这一点,请注意每个生成的数字所做的工作是一个常量(出队并在队列中最多插入两个新数字).

希望这可以帮助!