C言語で「1」が連続しないバイナリ文字列の数を数える方法

問題概要

この記事では、長さ n のすべてのバイナリ文字列の中から、「1」が隣り合って現れない文字列の総数を C 言語で求める方法を解説します。

2進数（バイナリ）とは

2進数は数値表現の手法の一つで、デジタルシステムで最も広く利用されています。使用する記号は「0」と「1」の2種類だけで、オン／オフのように動作状態が2つしかないデバイス（例えば「開」か「閉」のどちらかの状態を持つスイッチなど）で自然に表現できるのが特徴です。

そして「バイナリ文字列」とは、0 と 1 のみで構成される文字列のことを指します。

具体例で理解する

入力：n = 2
出力：3
説明：条件を満たすのは「00」「01」「10」の3つだけです。「11」は1が連続しているため除外されます。

入力：n = 7
出力：34

アルゴリズムのアプローチ

この問題は動的計画法（DP）の考え方を使うと効率よく解けます。ポイントは、文字列の末尾が「0」で終わる場合と「1」で終わる場合を分けて数えることです。

• 文字列の長さ n を入力として受け取ります。
• count 関数内で、サイズ n の配列 arr[] と arr_2[]、および結果を格納する変数 temp を用意します。
• arr[i] は「末尾が 0 で終わる長さ i+1 の文字列の数」、arr_2[i] は「末尾が 1 で終わる長さ i+1 の文字列の数」を表します。
• 初期値として、両配列の 0 番目の要素に 1 を代入します。
• i = 1 から i < n までループし、arr[i] = arr[i-1] + arr_2[i-1]、arr_2[i] = arr[i-1] を計算します。
• 最後に temp = arr[n-1] + arr_2[n-1] を求めて出力します。

なお、この漸化式はフィボナッチ数列と同じ構造を持っており、答えはフィボナッチ数 F(n+2) と一致します。

C言語による実装例

#include<stdio.h>
// 1が連続しないバイナリ文字列の数を計算する関数
void count(int num){
    int arr[num];
    int arr_2[num];
    int i = 0, temp = 0;
    arr[0] = arr_2[0] = 1;
    // i が num 未満である間ループ
    for (i = 1; i < num; i++){
        arr[i] = arr[i-1] + arr_2[i-1];
        arr_2[i] = arr[i-1];
    }
    temp = arr[num-1] + arr_2[num-1];
    printf("長さ%dのバイナリ文字列のうち、1が連続しないものの数 : %d\n", num, temp);
}
int main(){
    // count 関数を呼び出す
    count(10);
    count(7);
    count(1);
    return 0;
}

実行結果

長さ10のバイナリ文字列のうち、1が連続しないものの数 : 144
長さ7のバイナリ文字列のうち、1が連続しないものの数 : 34
長さ1のバイナリ文字列のうち、1が連続しないものの数 : 2

まとめ

本プログラムの時間計算量は O(n)、必要なメモリも O(n) と非常に効率的です。「1が連続しないバイナリ文字列の数」はフィボナッチ数列と密接な関係があるため、漸化式の仕組みさえ理解できればシンプルに実装できます。