C/C++で連続する1を含まないバイナリ文字列の個数を数えるプログラム

ここでは、少し頭を使う面白い問題を紹介します。ある整数 n が与えられたとき、「1 が隣り合って現れない」長さ n のバイナリ文字列（0 と 1 だけで構成される文字列）が全部でいくつ存在するかを求めます。

たとえば n = 2 の場合、条件を満たす文字列は {00, 01, 10} の 3 つなので、答えは 3 になります。「11」だけが除外されるわけです。

この問題は動的計画法（DP）を使えば効率よく解くことができます。考え方は次のとおりです。まず 2 つの配列 a と b を用意します。

• a[i]：長さ i・連続する 1 を含まない・末尾が 0 であるバイナリ文字列の個数
• b[i]：長さ i・連続する 1 を含まない・末尾が 1 であるバイナリ文字列の個数

文字を新しく付け加えるとき、直前の文字が 0 なら 0 でも 1 でも続けられますが、直前の文字が 1 の場合は 0 しか付け加えられません。したがって、遷移式は次のように表せます。

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

アルゴリズム

noConsecutiveOnes(n) の処理の流れは以下のとおりです。

Begin
    サイズ n の配列 a と b を定義する
    a[0] := 1
    b[0] := 1
    i が 1 から n-1 までの間、繰り返す:
        a[i] := a[i-1] + b[i-1]
        b[i] := a[i-1]
    繰り返し終了
    return a[n-1] + b[n-1]
End

C++による実装例

#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

n = 4 の場合の答えは 8 です。実際に列挙してみると、0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010 の 8 通りとなり、いずれにも「11」は含まれていないことが確認できます。

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。なお、サンプルコードで使っている可変長配列（VLA）は C++ の標準規格には含まれていないため、移植性を重視する実務コードでは std::vector<int> などを利用するのが安全です。