algorithm - 找出0,2,4,6,8组成的递增序列中的第n个数？

Question

我们有一个递增序列，其中每个元素仅由偶数组成(0、2、4、6、8)。我们如何找到这个序列中的第 n 个数

是否有可能在 O(1) 时间内找到此序列中的第 n 个数字。

序列:0, 2, 4, 6, 8, 20, 22, 24, 26, 28, 40, 42, 44, 46, 48, 60, 62, 64, 66, 68, 80, 82、84、86、88、200、202 等等。

Answer 1

此数列中的第 n 个数字是以 5 为底数的 n，数字加倍。

def base5(n):
    if n == 0: return
    for x in base5(n // 5): yield x
    yield n % 5

def seq(n):
    return int(''.join(str(2 * x) for x in base5(n)) or '0')

for i in xrange(100):
    print i, seq(i)

这在 O(log n) 时间内运行。我认为不可能在 O(1) 时间内完成。

可以通过将数字加倍与生成 n 的基数 5 数字相结合来简化一点:

def seq(n):
    return 10 * seq(n // 5) + (n % 5) * 2 if n else 0