程序在C / C ++中计算不带连续1的二进制字符串的数量？

在这里，我们将看到一个有趣的问题。假设给出n的一个值。我们必须找到所有长度为n的字符串，这样就不会有连续的1。如果n = 2，则数字为{00，01，10}，因此输出为3。

我们可以使用动态编程来解决。假设我们有一个表“ a”和“ b”。其中arr [i]存储长度为i的二进制字符串的数量，其中不存在连续的1，并且以0结尾。类似地，b保持相同，但是数字以1结尾。我们可以在最后一个后缀0或1。为0，但如果最后一个为1，则仅加0。

让我们看一下获得此想法的算法。

算法

noConsecutiveOnes(n)-

Begin
   define array a and b of size n
   a[0] := 1
   b[0] := 1
   for i in range 1 to n, do
      a[i] := a[i-1] + b[i - 1]
      b[i] := a[i - 1]
   done
   return a[n-1] + b[n-1]
End

示例

#include <iostream>
using namespace std;
int noConsecutiveOnes(int n) {
   int a[n], b[n];
   a[0] = 1;
   b[0] = 1;
   for (int i = 1; i < n; i++) {
      a[i] = a[i-1] + b[i-1];
      b[i] = a[i-1];
   }
   return a[n-1] + b[n-1];
}
int main() {
   cout << noConsecutiveOnes(4) << endl;
}

输出结果

8