連続する1を含まないnビットの2進数の個数を求めるアルゴリズム

この問題では、「連続する1」（隣り合う2桁がどちらも1になっている部分）を含まない2進数の個数を求めます。3ビットの2進文字列を考えてみると、011・110・111 の3つには連続する1が含まれており、それ以外の5つの数には連続する1が存在しません。したがって、このアルゴリズムを3ビットの数に適用した場合の答えは5になります。

ここで、i ビットかつ連続する1を含まない2進数の集合を a[i]、i ビットかつ連続する1を含む2進数の集合を b[i] と定義すると、次のような漸化式が成り立ちます。

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

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

この漸化式の直感的な理由は次のとおりです。新しい桁として「0」を追加する場合は、直前の状態がどんな文字列でも制約を受けないため、両方の集合から遷移できます。一方、新しい桁として「1」を追加できるのは、直前の末尾が「0」の場合だけです。これにより、動的計画法（DP）で効率よく答えを求められます。

入力

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

出力

連続する1を含まない2進文字列の個数を返します。

この場合の結果は8です。（連続する1を持たない2進文字列が8つ存在します）

アルゴリズム

countBinNums(n)

入力: n はビット数
出力: 連続する1を含まない数の個数
Begin
    末尾が0の文字列用リストと、末尾が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

このアルゴリズムの計算量は O(n)、必要な記憶領域も O(n) であり、ビット数に対して線形時間で答えが得られるのが特徴です。

サンプルコード（C++）

#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