C++で数列中に現れる連続する0のペアを数える方法

問題の概要

1から始まる数列生成器を考えます。各ステップで「0」は「10」へ、「1」は「01」へと変換されます。そのため、ステップが進むごとに数列は以下のように変化していきます。

• ステップ1: 01
• ステップ2: 1001
• ステップ3: 01101001 ……

この記事の目的は、与えられたステップ数における連続する2つの0（00）のペアの出現回数を求めることです。例えば、ステップ1では連続する0のペアは0個、ステップ2では1個、ステップ3でも1個となります。

• ステップ4: 1001011001101001
• ステップ5: 01101001100101101001011001101001

数列の規則性

数列を観察すると、次の性質が見えてきます。

• 数列の長さはステップ数 n に対して 2ⁿ ずつ増加していく。
• 数列は12文字ごとに同じパターンで自己反復する。
• 長さ12のパターンの中には、連続する0のペアがちょうど2つ含まれている。

したがって、ステップ数 S のとき、長さ12のパターンの繰り返し回数は 2S ÷ 12（整数除算）で求められます。さらに先頭部分に初期ペアが1つ存在するため、連続する0のペアの総数は次の式で計算できます。

ペアの総数 = 1（先頭の初期ペア）+ 2 ×（長さ12のパターンの繰り返し回数）

計算例

入力 − steps = 5

出力 − 連続する0のペアの数：5

説明 − 上に示したとおり、ステップ5の数列は次のようになります。

Step 5: 01101001100101101001011001101001
連続する0のペアの数は 5 個。

公式による確認:
2^5 = 32、32 ÷ 12 = 2（整数部）
ペア数 = 1 + 2 × 2 = 5

入力 − steps = 10

出力 − 連続する0のペアの数：171

説明 − 公式に当てはめると、2¹⁰ = 1024、1024 ÷ 12 = 85 より、ペア数 = 1 + 2 × 85 = 171 となります。

プログラムの考え方

ステップ数を入力として受け取り、次のように条件分岐して処理します。steps = 1 の場合は連続する0のペアが 0 個、steps = 2 または 3 の場合は 1 個です。それ以外の場合は、式 temp = 2steps ÷ 12 を計算し、count = 2 × temp + 1 から答えを求めます。

アルゴリズムの手順

• 変数 decimal にステップ数を入力として受け取る。
• 関数 Zero_pairs(int decimal) は、decimal を受け取り、そのステップにおける連続する0のペア数を返す。
• カウントの初期値を 0 とする。
• decimal <= 1 なら 0 を返す。
• decimal == 2 または decimal == 3 なら 1 を返す。
• それ以外の場合は temp = pow(2, decimal) / 12 を計算し、count = 2 × temp + 1 を求める。
• count を結果として返す。

C++実装例

#include<bits/stdc++.h>
using namespace std;
int Zero_pairs(int decimal){
    int count = 0;
    if(decimal <=1){
        count = 0;
    }
    else if(decimal == 2 || decimal == 3){
        count = 1;
    }
    else{
        int temp = (pow(2, decimal) / 12);
        count = 2 * temp + 1;
    }
    return count;
}
int main(){
    int decimal = 7;
    cout<<"Count of Pairs Of Consecutive Zeros are: "<<Zero_pairs(decimal);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Count of Pairs Of Consecutive Zeros are: 21

これは、ステップ7の場合、2⁷ = 128、128 ÷ 12 = 10 となり、count = 2 × 10 + 1 = 21 と計算できるためです。

まとめ

このように、数列を実際に生成しなくても、その周期的な構造を利用した公式「count = 2 × (2^steps ÷ 12) + 1」を使えば、定数時間で連続する0のペア数を効率よく求められます。ステップ数が大きくなった場合でも高速に答えを導き出せる点が、このアプローチの大きな利点です。