連続する1を含まない2進数文字列の個数を求めるアルゴリズム

問題の概要

この問題では、「1」が連続して現れない2進数（バイナリ文字列）の個数を求めます。たとえば3桁の2進数文字列を考えてみると、011・110・111 の3つは連続する1を含むため対象外となり、条件を満たすのは残りの5つです。したがって、このアルゴリズムを3桁の2進数に適用した場合の答えは 5 になります。

解法のポイント：漸化式で考える

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

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

直感的に言うと、末尾に 0 を付ければどちらのグループからでも新しい文字列を作れますが、末尾に 1 を付けられるのは「直前が 0 で終わる文字列」だけだ、という性質を表しています。

入力と出力

入力: 2進数のビット数（例: 4）
出力: 連続する1を含まない2進数文字列の個数
結果: 8（4桁の場合、連続する1を含まない文字列は8個存在します）

アルゴリズム: countBinNums(n)

入力: n … ビット数
出力: 連続する1を持たない2進数の個数

「0で終わる文字列の個数（endWithZero）」と「1で終わる文字列の個数（endWithOne）」を配列で管理し、初期値を 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

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

補足: フィボナッチ数列との関係

n 桁の2進数文字列のうち連続する1を含まないものの個数は、フィボナッチ数列の第 (n+2) 項と一致することが知られています。n=3 のとき 5、n=4 のとき 8 となるのは、数列 1, 1, 2, 3, 5, 8, 13 … と照らし合わせると納得できるでしょう。また、ループを1周するだけで計算が完了するため、計算量は O(n) と非常に効率的です。