主页 / 问题 / 830048
Accepted
firet
Asked:2020-05-19 08:15:46 +0000 UTC2020-05-19 08:15:46 +0000 UTC

将递归重写为循环：不带 11 的 n 位序列数

  • 772

有一个任务给定一个自然数 n，从 0 到 1 确定不包含两个连续序列的长度为 n 的序列的数量。

有一个答案

def seq_count(n, p = 0):
    if not n: return 1
    return seq_count(n - 1, 0) + (0 if p else seq_count(n - 1, 1))

您需要迭代地重写。

seq_count(3)将返回5，因为可能的组合：

000 001 011 111 010 100 110 101

连续不包含 2 个单位：

000 001 010 100 101

但是为什么它起作用是完全不可理解的，这就是为什么我要求你重写它的循环。

python

3 个回答

  1. Best Answer

    为什么它起作用是完全无法理解的，这就是为什么我要求你循环重写它

    在这种情况下，递归解决方案（通常是动态规划问题的情况）从字面上描述了解决方案：也就是说f(0...) = f(00..) + f(01..)，f(1...) = f(10..)长度为 n 的不包含 11 的位序列的数量等于长度为 (n- 1）从0开始，如果前一位不为​​1，加上以1开头的序列数（排除11）：

    def count(n, previous_bit=0):
    assert n>=0
    return 1 if n==0 else (
        count(n-1, 0)
        + (previous_bit == 0) * count(n-1,1))

    这几乎与正面解决方案一样清晰（要对所有长度为 n 位的位序列进行排序，计算有多少不包含 11）：

    def brute_force(n):
    return sum(1 for bits in map(bin, range(2**n)) if '11' not in bits)

    循环可以隐藏解决方案的明显性：

    def fib(a=0, b=1):
    """Fibonacci sequence"""
    while True:
        yield a
        a, b = b, a+b

    所有选项产生相同的结果：

    for n, f in zip(range(10), fib(1, 2)):
    print(n, count(n), f, brute_force(n))

    结果：

    0 1 1 1
1 2 2 2
2 3 3 3
3 5 5 5
4 8 8 8
5 13 13 13
6 21 21 21
7 34 34 34
8 55 55 55
9 89 89 89

    通过添加@functools.lru_cache(maxsize=5)before count()，您可以记住之前的几个结果，以免重新计算它们。

    如果不需要确切的结果（一个近似值就足够了），那么有一些封闭的公式可以让您在 O (1) 时间内找到结果。有关详细信息，请参阅斐波那契数列的偶数和的答案中的链接。

    • 3

  2. 您可以重复生成组合并计算那些连续没有两个单元的组合：

    import itertools


items = [''.join(i) for i in itertools.product('01', repeat=3)]
print(items)  # ['000', '001', '010', '011', '100', '101', '110', '111']

items = [i for i in items if '11' not in i]
print(items)  # ['000', '001', '010', '100', '101']
print(len(items))  # 5

    有一个算法，现在你可以检查一下：

    import itertools


def seq_count_v2(n):
    items = [''.join(i) for i in itertools.product('01', repeat=n)]
    items = [i for i in items if '11' not in i]
    return len(items)

  
for i in range(3, 10):
    print(seq_count(i), seq_count_v2(i))

    火柴：

    5 5
8 8
13 13
21 21
34 34
55 55
89 89

    PS。我知道算法seq_count_v2没有优化，但我决定展示这个想法本身

    • 2

  3. 让我们试着不给鱼，而是给鱼竿。

    假设有一个长度为K的规则序列。这个序列可以以0结尾-那么至少0，至少可以添加1。如果它以1结尾，那么只能添加0。或者另一种解释：一个0序列，可以从较短的0序列和较短的1序列中得到，但1序列只能从0序列中得到。

    表示第一个 F0(K)，第二个 F1(K) 的数量。它们的数量取决于先前长度的序列数量：

    F0(K) = F0(K-1) + F1(K-1)
F1(K) = F0(K-1)
S(K) = F0(K) + F1(K)  //общее количество правильных последовательностей

    剩下的就是设置单位长度的初始值，并循环更新值。

    PS 结果序列包含一些非常显着的数字

    • 1

相关问题