求对于不包含2个连续0的n位二进制位串的个数有关的递推关系

2025-12-17 21:41:12
推荐回答(1个)
回答1:

1位:1、0----2种可能
2位:11、01、10----3种可能
3位:111、110、101、011、010----5种可能
4位:1111、1110、1101、1011、0111、0101、1010、0110----8种可能
5位:11111、11110、11101、11011、
    10111、01111、01011、01101、
    01110、10101、10110、01010、11010----13种情况

所以,递推公式为:Fn=Fn-1+Fn-2