一定长度的没有连续零的二进制字符串的数量与斐波那契数相关。

Question

我正在尝试开发一种算法，该算法可以确定没有特定长度的连续零的二进制字符串的数量。我找到了基于斐波那契数列的解决方案。我不明白，以 0 或 1 结尾且不包含重复 0 的二进制字符串如何依赖于斐波那契数列。
谁能解释一下？

例如，长度为 3 的答案将为 5，因为：

*没有连续零的字符串

Answer 1

设 Z(k) 是有效二进制字符串的数量，以 0 结尾。表示这样的字符串 *0

设 O(k) 是有效二进制字符串的数量，以 1 结尾。表示这样的字符串 *1

我们可以构建长度为 k+1 的 *0，只需在 *1 的末尾添加 0，因此

Z(k+1) = O(k)

我们可以构建长度为 k+1 的 *1，将 1 添加到任何 *1 的末尾和任何 *0 的末尾，所以

O(k+1) = O(k) + Z(k)

考虑所有长度为 (k+2) 的有效字符串

F(k+2) = 
       Z(k+2) +      O(k+2)          = 
       O(k+1) +      O(k+1) + Z(k+1) = 
       O(k) + Z(k) + O(k+1) + Z(k+1) =
       F(k)        + F(k+1)

你看到类似斐波那契的关系了吗？

一定长度的没有连续零的二进制字符串的数量与斐波那契数相关。

Number of the binary strings without consecutive zeroes of a certain length correlates with Fibonacci numbers.

java

algorithm

fibonacci