长度为n的二进制数排除相邻两位是1的情况后有多少种可能

有一串数字   到底有几位我们可以自己先输入n来定  然后每位上的数字要么0  要么1   这样其实是有2的n次方种情况  但现在我要把相邻两位是1的排除了  这时候有多少种可能性。


一个小盆友突然给我了这道题。开始推错了2回...没想到最后推出来事斐波拉契数列。退化了，好无语。

设对于n位数， 满足条件的数目 最右一位是1的情况的集合为L(n)， 最右一位是0的情况的集合是M(n)

当x=n+1 那么a.对于任意一个L(n)中的情况， 后面补0
                    b.对于任意一个M(n)中的情况， 后面补0
                    c.对于任意一个M(n)中的情况， 后面补1

得到最后一位是0的情况(a & b) :  M(n+1) = L(n)+ M(n)
      最后一位是1的情况(c)        :  L(n+1) = M(n)

所以
f(n+1) = L(n)+ M(n) + M(n) = f(n) + L(n-1)+M(n-1) = f(n) + f(n-1)