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

Question

我们有一个递增序列，其中每个元素仅包含偶数位 (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.

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

Answer 2

int Code()
{
    k=0;
   for(i=0;i<=10000;i++)
   {
       count=0;
       n=i;
       while(n!=0)
       {
           c=n%10;
           n=n/10;
           if(c%2!=0)
           {
               count=1;
           }
       }
       if(count==0)
       { a[k]=i;
       k++;}
    }
 }

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

Find the nth number in the increasing sequence formed by 0,2,4,6,8?

algorithm

sequences

sequence