多少n长的二进制序列问题

Question

如何在 python/java 或任何其他语言中找到此问题的解决方案：

提前致谢

Answer 1

由于程序不是证明，您仍然需要证明它，这里是一些 Python 代码：

def zig_zag(seq):
    """tests if binary sequence seq satsifies zig-zag pattern"""
    for i in range(len(seq)-1):
        if (i%2 == 0 and seq[i] > seq[i+1]) or (i%2 == 1 and seq[i] < seq[i+1]):
            return False
    return True

def count_zig_zags(n):
    """counts the number of binary zig-zag patterns of length n"""
    count = 0
    for i in range(2**n):
        b = bin(i)[2:]
        if zig_zag(b): count += 1
    return count

例如：

>>> [count_zig_zags(n) for n in range(1,12)]
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]

证明将通过强归纳法。

多少n长的二进制序列问题

how many n-length binary sequence problem

math

binary

sequence