求无连续1的n位0-1排列数的技术方法咨询

嘿，这个问题其实是斐波那契数列的经典应用场景，咱们一步步拆解清楚：

1. 先找规律：从小例子入手 #

先手动算几个小n值的结果，看看规律：

• n=1：有效序列是0、1，共2个
• n=2：有效序列是00、01、10，排除11，共3个
• n=3：有效序列是000、001、010、100、101，共5个
• n=4：有效序列数是8个
• n=5：有效序列数是13个

看出来了吗？这个序列是2,3,5,8,13...，本质就是起始项偏移的斐波那契数列。

2. 推导递推公式 #

设f(n)表示n位符合要求的序列数量，我们可以从序列的最后一位分析：

• 如果最后一位是0：那么前n-1位只要满足“无连续1”即可，数量就是f(n-1)
• 如果最后一位是1：那么前一位必须是0，前n-2位满足“无连续1”即可，数量就是f(n-2)

所以递推公式是：

f(n) = f(n-1) + f(n-2)

初始条件 #

为了让递推更顺畅，我们可以定义：

• f(0) = 1（空序列，作为边界条件）
• f(1) = 2（n=1时的2个有效序列）

验证一下：
f(2) = f(1)+f(0) = 2+1=3，和手动计算一致；
f(5)=f(4)+f(3)=8+5=13，正好对应题目示例的结果。

3. 代码实现 #

迭代版本（推荐，避免递归深度问题） #

这个版本效率高，适合大n值：

def count_valid_sequences(n):
    if n == 0:
        return 1
    # 初始化f(0)和f(1)
    prev_prev, prev = 1, 2
    for _ in range(2, n + 1):
        current = prev_prev + prev
        prev_prev, prev = prev, current
    return prev

递归版本（适合理解逻辑，n大时慎用） #

如果只是为了理解递推逻辑，递归写法更直观，但n超过1000会有栈溢出风险：

def count_valid_sequences_recursive(n):
    if n == 0:
        return 1
    if n == 1:
        return 2
    return count_valid_sequences_recursive(n-1) + count_valid_sequences_recursive(n-2)

4. 验证示例 #

当输入n=5时，调用函数返回13，和我们手动计算的结果一致，正确。

内容的提问来源于stack exchange，提问作者Heidar