C++で列車の停車駅の組み合わせ数を求める方法

地点XとYの間にはn個の中間駅があるとします。ここで、「どの2つの停車駅も隣り合わない」という条件のもとで、s個の駅に停車する列車の配置方法が何通りあるかを求める問題を考えてみましょう。この記事では、停車駅の組み合わせ数を求めるためのアプローチを段階的に詳しく解説します。この問題は、本質的には組合せ論の問題であり、s個の停車駅の選び方の総数を求めることになります。

問題を解くアプローチ

まず具体例として、中間駅が8個あり、そのうち3個の駅に停車させたい場合を考えてみます。

n = 8, s = 3

このとき、列車が停車できない駅は(n − s)、つまり5個残ることになります。

停車できない5つの駅をA、B、C、D、Eとします。これらの駅の間および両端には、3つの停車駅を「隣接しないように」挿入できる隙間が6箇所あります。したがって、求める方法の数は次のように計算できます。

6C3 = 6! / (3! × 3!) = (6 × 5 × 4) / (3 × 2 × 1) = 20

つまり、XからYまでの間に3つの停車駅を配置する方法は全部で20通りあることがわかります。

入出力例

入力：n = 15, s = 4
出力：495

入力：n = 8, s = 3
出力：20

C++での実装例

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n = 8, s = 3;
    int flag1 = 1, flag2 = 1, temp = s, ans;
    // 'n-s+1'個の位置の中から's'個を選択する
    int x = n - s + 1;
    while (x != (n - 2 * s + 1)) {
        flag1 = flag1 * x;
        x--;
    }
    while (temp != 1) {
        flag2 = flag2 * temp;
        temp--;
    }
    ans = flag1 / flag2;
    if ((n - s + 1) >= s)
        cout << "Number of ways : " << ans;
    else
        cout << "not possible to find";
    return 0;
}

実行結果

Number of ways : 20

コードの解説

このC++コードの動作を理解しやすくするために、処理をステップごとに分解してみましょう。

• 駅の総数をn、停車駅の数をsとして設定します。

• flag1とflag2の変数を1で初期化し、sの値を一時変数tempに保存します。

• flag1（分子）を計算します。(n−s+1)から(n−2s+2)までの整数を掛け合わせることで、組み合わせの分子部分を求めます。

• flag2（分母）を計算します。これはsの階乗（s!）に相当します。

• flag1をflag2で割って結果を求め、出力します。なお、(n−s+1)がs未満の場合は、条件を満たす配置が存在しないため「not possible to find」と表示されます。

まとめ

この記事では、「隣り合う駅に連続して停車しない」という条件のもとで、中間駅への停車方法の総数を求める問題を解きました。隙間に着目することで問題を単純な組み合わせ計算に帰着できる点がポイントです。C++による実装例とともに、問題を解決するための考え方の全体像も紹介しました。同じロジックはC、Java、Pythonなど他のプログラミング言語でも容易に実装できます。