連続する「1」を含まないバイナリ文字列の数を数えるPythonプログラム

この記事では、「連続する1が存在しないバイナリ文字列の総数を求める」という問題の解き方について、Pythonでの実装例を交えながら詳しく解説します。

問題文

問題： 正の整数 N が与えられます。このとき、長さ N のバイナリ文字列（0と1のみで構成される文字列）のうち、連続する「1」が一切含まれないものの総数を求めてください。

例えば N = 3 の場合、有効な文字列は「000」「001」「010」「100」「101」の5つとなり、「011」「110」「111」は連続する1を含むため除外されます。

アプローチ：動的計画法

この問題は動的計画法（DP）を使うことで効率的に解けます。各桁の状態を次の2つの配列で管理します。

• a[i] … 長さ i+1 の文字列のうち、末尾が「0」で終わる有効な文字列の数
• b[i] … 長さ i+1 の文字列のうち、末尾が「1」で終わる有効な文字列の数

遷移のルールは以下の通りです。

• 末尾に「0」を付けられるのは、直前の状態が何であってもよいため a[i] = a[i-1] + b[i-1]
• 末尾に「1」を付けられるのは、直前の末尾が「0」の場合のみのため b[i] = a[i-1]

最終的な答えは a[n-1] + b[n-1] となります。なお、この漸化式はフィボナッチ数列と同じ構造を持っている点も興味深い特徴です。

実装例

# 文字列の数をカウントする関数
def countStrings(n):
    a=[0 for i in range(n)]
    b=[0 for i in range(n)]
    a[0] = b[0] = 1
    for i in range(1,n):
        a[i] = a[i-1] + b[i-1]
        b[i] = a[i-1]
    return a[n-1] + b[n-1]

# メイン処理
n=5
print("The number of strings: ",countStrings(n))

出力結果

The number of strings: 13

N = 5 の場合、答えは13通りになります。実際に列挙すると「00000」「00001」「00010」「00100」「00101」「01000」「01001」「01010」「10000」「10001」「10010」「10100」「10101」の13個であり、確かに一致します。

コードのポイント

すべての変数はローカルスコープ内で宣言されており、ループの中で配列 a と b の値が逐次更新されていく様子を図で確認できます。計算量は O(N)、メモリ使用量も O(N) と非常に効率的です。さらに、直前の2つの値だけを保持すればよいため、変数2つだけを使って O(1) のメモリに削減することも可能です。

まとめ

この記事では、動的計画法を用いて「連続する1を含まないバイナリ文字列の総数」を求めるPythonプログラムの実装方法を学びました。フィボナッチ数列との関係や計算量の削減方法にも触れましたので、ぜひ自分のコードにも応用してみてください。