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

问题描述：

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

---

最佳答案：

首先考虑第n位,
若n为1,则第n 位以前的个数就有a(n-1),
若n为0,则看n-1位,若为1的话,则有a(n-2);
若为0的话,则有2^(n-2);
所以递推公式为:an=a(n-1)+a(n-2)+2^(n-2)