連続する1のないバイナリ文字列の数をカウントするC/C ++プログラム？

2進数は、2つだけを含む数、つまり1つまたは2つを含む数です。すべての2進数は2進ビットのストリームであり、これを2進文字列と見なします。この文字列の場合、Nビットの連続する文字列を含まないバイナリ文字列の数を見つける必要があります。

たとえば、N-5の場合、与えられた制約を満たすバイナリ文字列は00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101

1つの方法は、すべてのN桁の文字列を生成し、指定された制約を満たす文字列のみを出力することです。しかし、この方法は、機能することに関してはそれほど効率的ではありません。

もう1つの方法は、再帰を使用することです。再帰の各ポイントで、部分的に形成された数値に0と1を追加し、1桁少ない数字で再帰します。ここでの秘訣は、1を追加し、部分的に形成された数値の最後の桁が0の場合にのみ繰り返すことです。これにより、出力文字列に連続する1が含まれることはありません。

Input: n = 5
Output: Number of 5-digit binary strings without any consecutive 1's are 13

例

#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
   if (n == 0)
      return 0;
   if (n == 1) {
      if (last_digit)
         return 1;
      else
         return 2;
   }
   if (last_digit == 0)
      return countStrings(n - 1, 0) + countStrings(n - 1, 1);
   else
      return countStrings(n - 1, 0);
}
int main() {
   int n = 5;
   cout << "Number of " << n << "-digit binary strings without any "
   "consecutive 1's are " << countStrings(n, 0);
   return 0;
}