連続する1を含まない2進文字列の個数を数えるC/C++プログラム

2進数とは、0と1という2種類の数字のみで構成される数のことです。すべての2進数はビットの並び（ストリーム）とみなすことができ、これを「2進文字列」と呼びます。本記事では、N桁の2進文字列のうち、「1が連続して現れない」という条件を満たすものが何通りあるかを求める方法を解説します。

例えば、N = 5 の場合、条件を満たす2進文字列は以下の13通りになります。

00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10001, 10010, 10100, 10101

アプローチ1：全列挙による方法

一つ目の方法は、N桁のすべての2進文字列を生成し、その中から条件を満たすものだけを出力するというものです。しかし、この方法では文字列の総数が桁数に対して指数関数的に増加するため、実用面での効率はあまり良くありません。

アプローチ2：再帰を使う方法

もう一つの方法は、再帰を利用するアプローチです。再帰の各段階で、途中まで構築した文字列に「0」と「1」をそれぞれ追加し、残りの桁数を1減らして再帰呼び出しを行います。

ここでのポイントは、「直前の桁が0である場合にのみ、1を追加して再帰する」という点です。このルールを守ることで、出力される文字列に1が連続して現れることは決してなくなります。

入力：n = 5
出力：5桁の2進文字列のうち、1が連続しないものの数は 13

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

実は、この問題の答えはフィボナッチ数列と密接な関係があります。n桁の2進文字列で1が連続しないものの個数は、フィボナッチ数の F(n+2) に一致します。例えば n = 5 の場合、F(7) = 13 となり、上記の出力結果と一致します。この性質を利用すれば、動的計画法によってより高速に答えを求めることも可能です。

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

#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
    if (n == 0)
        return 0;
    if (n == 1) {
        if (last_digit)
            return 1;
        else
            return 2;
    }
    if (last_digit == 0)
        return countStrings(n - 1, 0) + countStrings(n - 1, 1);
    else
        return countStrings(n - 1, 0);
}
int main() {
    int n = 5;
    cout << "Number of " << n << "-digit binary strings without any "
    "consecutive 1's are " << countStrings(n, 0);
    return 0;
}