arrays - 如何生成具有特定属性的位序列

Question

我想生成一个最小长度的位序列，其中最后一个 0 位于 2 1 之间，给定一个正整数 x。

例子:

0 是 x=0

1 是 x=1

00 是 x=2

01 是 x=3

10 是 x=4

000 是 x=5

001 是 x=6

010 是 x=7

100 是 x=8

101 是 x=9

0000 是 x=10

等等

是否存在从给定整数 x 创建这些位序列的构建方案？

Answer 1

观察长度为n且以0或1开头的编码N(n)的个数是:

n 0 1 总计

1 1 1 2

2 2 1 3

3 3 2 5

4 5 3 8

这些列实际上是移位的斐波那契序列，因为对于一个 n 位序列，如果它以 1 开头，那么下一个数字不能是 1，所以我们只有 N(n-2) 个选择，但是如果它以 0 开头，那么我们有 N(n-1) 个选择。

利用它，您可以通过计算编码的长度以及有多少个编码具有更小的长度，将原始问题转化为“找到长度为 l 的第 k 个编码”。这个转换后的问题可以通过递归来解决。只有 O(logn) 位数字，所以这将在 O(logn) 内结束。

Python代码:

# 10-32
# 0000
# 0001
# 0010
# 0100
# 0101
# 1000
# 1001
# 1010
# 00000
# 00001
# 00010
# 00100
# 00101
# 01000
# 01001
# 01010
# 10000
# 10001
# 10010
# 10100
# 10101
# 000000
# 000001

fib = [1, 1, 2, 3, 5, 8, 13, 21]

def encode(m):
    d = 1
    for i in fib[2:]:
        if m < i:
            break
        m -= i
        d += 1
    s = ''
    for i in range(d, 0, -1):
        if m < fib[i]:
            s += '0'
        else:
            m -= fib[i]
            s += '1'
    return s

for i in range(50):
    print(i, encode(i))