C言語プログラム：連続する「00」「111」を避けて、N個の0とM個の1を出力する方法

N個の「0」とM個の「1」を組み合わせて数列を作ることを考えます。ただし、この数列には「00」（0が2つ連続）や「111」（1が3つ連続）という並びが含まれてはいけません。本記事では、その条件を満たす数列をC言語で出力する方法を解説します。

入力：N = 5、M = 9
出力：1 1 0 1 1 0 1 1 0 1 0 1 0 1

数列が作れるための条件

まず押さえておきたいのが、数列の構成可否を判定する条件式です。次の条件がfalseである必要があります。

(m < n-1) || m >= 2 * (n + 1)

この式がtrueになる場合、すなわち1が少なすぎる（m < n−1）か多すぎる（m ≥ 2×(n+1)）ときは、条件を満たす並び方が存在しません。

理由を整理すると：

• 0を隣り合わせにしないため、n個の0の間には最低でも n−1 個の1が必要 → m ≥ n−1
• 1を3つ連続させないため、0と0の間および両端の隙間（計 n+1 箇所）に置ける1は各2個まで → m ≤ 2×(n+1)

つまり n−1 ≤ m ≤ 2n+2 の範囲内であれば、必ず目的の数列を構成できます。

なお、解答を見る前に、まずはご自身でロジックを考えてみることをおすすめします。

アルゴリズム

START
Step 1 -> 変数 n と m に値を入力する
Step 2 -> IF m == n-1 ならば（0が1個多いケース）
    WHILE m > 0 かつ n > 0 の間
        「01」を出力
        m と n を 1 ずつ減らす
    END WHILE
    IF n != 0 ならば
        残りの「0」を出力
    END IF
    IF m != 0 ならば
        残りの「1」を出力
    END IF
Step 3 -> ELSE IF (m < n-1) || m >= 2 * (n + 1) ならば
    「数列を作成できません」と出力
Step 4 -> ELSE
    WHILE m - n > 1 かつ n > 0 の間
        「1 1 0」を出力
        m を 2 減らし、n を 1 減らす
    END WHILE
    WHILE n > 0 の間
        「1 0」を出力
        m と n を 1 ずつ減らす
    END WHILE
    WHILE m > 0 の間
        「1」を出力
        m を 1 減らす
    END WHILE
Step 5 -> END ELSE
STOP

ロジックのポイント

1が多く余るケースでは、「1 1 0」というブロックで0を挟みながら1を優先的に消費します。これにより「111」の連続を回避できます。その後、残った0は「1 0」のペアとして処理し、最後に余った1のみを末尾へ出力します。この順序で処理することで、どこにも「00」や「111」が現れない数列が完成します。

C言語での実装例

#include <stdio.h>
#include <math.h>

int main() {
    int n = 5, m = 9;
    if (m == n - 1) { // mがnより1小さい場合：0と1を交互に出力
        while (m > 0 && n > 0) { // mとnを使い切るまでループ
            printf("01");
            m--;
            n--;
        }
        if (n != 0) // 余った0を出力
            printf("0");
        if (m != 0) // 余った1を出力
            printf("1");
    }
    else if ((m < n - 1) || m >= 2 * (n + 1)) { // trueの場合は数列を作成不可
        printf("Can't have sequence for this\n");
    } else {
        while (m - n > 1 && n > 0) {
            printf("1 1 0 ");
            m -= 2;
            n--;
        }
        while (n > 0) {
            printf("1 0 ");
            n--;
            m--;
        }
        while (m > 0) {
            printf("1 ");
            m--;
        }
    }
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

1 1 0 1 1 0 1 1 0 1 0 1 0 1

結果を確認すると、0がちょうど5個、1がちょうど9個含まれており、「00」や「111」という並びが一切出現していないことがわかります。