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

ここで、1つの興味深い問題が発生します。 nの値が1つ与えられたとします。連続する1がないように、長さnのすべての文字列を見つける必要があります。 n =2の場合、数値は{00、01、10}なので、出力は3です。

動的計画法を使用してそれを解決できます。テーブル「a」と「b」があるとします。ここで、arr [i]は、連続する1が存在せず、0で終わる長さiのバイナリ文字列の数を格納します。同様に、bは同じですが、1で終わる数を保持します。最後の1つに0または1を追加できます。は0ですが、最後の1が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