这是一个采访问题,似乎与Project Euler Problem 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是我们需要输出的数字.
有谁知道它可能是什么？