大门|大门-CS-2015（第1组）|问题65

让我们 _N 表示包含两个连续1的长度为n的位字符串的数量。a的递归关系是什么 _N ? （A） A. _n–2 +a _n–1 + 2 ^n–2 （B） A. _n–2 +2a _n–1 + 2 ^n–2 （C） 2a _n–2 +a _n–1 + 2 ^n–2 （D） 2a _n–2 +2a _n–1 + 2 ^n–2 答复: （A） 说明： 简单解决方案 解决这个问题的一种方法是尝试使用较小的值并排除选项。

a0 = 0  
a1 = 0  
a2 = 1  ["11"]
a3 = 3  ["011", "110", "111"] 
a4 = 8  ["0011", "0110", "0111", "1101",
                    "1011", "1100", "1110", "1111"]

如果我们查一下 _3. ，我们可以看到，只有A和C满足该值。在（A）和（C）中，只有（A）满足A _4. .

另一个解决方案（有证据）

A string of length n (n >= 2) can be formed by 
following 4 prefixes

1) 11 followed by a string of length n-2
2) 00 followed by a string of length n-2
3) 01 followed by a string of length n-2
4) 10 followed by a string of length n-2

Number 1 has already two consecutive 1's so number 
of binary strings beginning with number 3 is 2n-2
as remaining n-2 bits can have any value.

Number 2 has two 0's so remaining n-2 bits must have
two consecutive 1's. Therefore number of binary strings
that can be formed by number 2 is an-2.

Number 3 and Number 4 together form all strings of length
n-1 and two consecutive 1's.

这个问题的小测验