2進表現で連続する1がない1からnビットの数値？

この問題では、連続する1を持たない2進数を見つける必要があります。 3ビットの2進数文字列には、連続する1を持つ3つの2進数011、110、111があり、連続する1がない5つの数値があります。したがって、このアルゴリズムを3ビットの数値に適用すると、答えは5になります。

a [i]がビット数がiで連続する1を含まない2進数のセットであり、b [i]がビット数がiで連続する1を含む2進数のセットである場合、次に、-

a[i] := a[i - 1] + b[i - 1]

b[i] := a[i - 1]

入力

このアルゴリズムは、2進数のビット数を取ります。入力を4とします。

出力

連続する1がないバイナリ文字列の数を返します。

ここで、結果は− 8になります（連続する1がない8つのバイナリ文字列があります）

アルゴリズム

countBinNums（n）

Input: n is the number of bits.
Output: Count how many numbers are present which have no consecutive 1.
Begin
   define lists with strings ending with 0 and ending with 1
   endWithZero[0] := 1
   endWithOne[0] := 1
   for i := 1 to n-1, do
      endWithZero[i] := endWithZero[i-1] + endWithOne[i-1]
      endWithOne[i] := endWithZero[i-1]
   done
   return endWithZero[n-1] + endWithOne[n-1]
End

例

#include <iostream>
using namespace std;
int countBinNums(int n) {
   int endWithZero[n], endWithOne[n];
   endWithZero[0] = endWithOne[0] = 1;
   for (int i = 1; i < n; i++) {
      endWithZero[i] = endWithZero[i-1] + endWithOne[i-1];
      endWithOne[i] = endWithZero[i-1];
   }
   return endWithZero[n-1] + endWithOne[n-1];
}
int main(){
   int n;
   cout << "Enter number of bits: "; cin >> n;
   cout << "Number of binary numbers without consecutive 1's: "<<countBinNums(n) << endl;
   return 0;
}

出力

Enter number of bits: 4
Number of binary numbers without consecutive 1's: 8