登机门|登机门CS 2008 |问题78

设xn表示长度为n且不包含连续0的二进制字符串的数量。Xn满足以下哪种复发？

（A） A. （B） B （C） C （D） D

答复: （D） 说明：

• 对于n=1，即长度为1的二进制字符串，字符串为“0”、“1”。 X1=2
• 对于n=2，即长度为2的二进制字符串，字符串为“01”、“10”、“11”。 （此处字符串“00”将被拒绝，因为它有连续的零）。 所以，X2=3
• 对于n=3，即长度为3的二进制字符串，字符串为“010”、“011”、“101”、“110”、“111”。

0 01（被拒绝） 0 10 0 11 1 01 1 10 1 11 那么，X3=5 这表明X3=X2+X1 因此，X（n）=X（n-1）+X（n-2） 如果你在上面的帖子中发现任何错误，请在下面发表评论。

这个问题的小测验