在由0,2,4,6,8构成的递增序列中找到第n个数字？

• Z时代
• 2024-01-10
• 分类：问答

我们有一个递增的序列，其中每个元素仅由偶数数字组成（0、2、4、6、8）。我们怎么能find the nth number in this

sequence

是否有可能在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 and so on.

回答：

此序列中的第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

以上是 在由0,2,4,6,8构成的递增序列中找到第n个数字？ 的全部内容， 来源链接： utcz.com/qa/400775.html