Write a program in C/C++ to count the number of binary strings without consecutive 1's?

Here we will see an interesting question. Suppose a value n is given. We must find all strings of length n in which there are no consecutive 1's. If n = 2, the numbers are {00, 01, 10}, so the output is 3.

We can use dynamic programming to solve it. Suppose we have a table 'a' and 'b'. where arr[i] stores the number of binary strings of length i that have no consecutive 1's and terminate with 0. Similarly, b is the same but ends in 1. We can add 0 or 1 if the last one is 0, but only add 0 if the last one is 1.

Let's look at the algorithm to get this idea.

Algorithm

noConsecutiveOnes(n) -The Chinese translation of

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

Example

is:

Example

#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;
}

Output

8

The above is the detailed content of Write a program in C/C++ to count the number of binary strings without consecutive 1's?. For more information, please follow other related articles on the PHP Chinese website!