C言語で解く停車駅選択問題：連続しない停車駅の組み合わせ数を求める方法

問題概要

本プログラムは、n個の駅のうちr個の駅に列車を停車させる場合について、「どの2つの停車駅も隣り合わない（連続しない）」という条件を満たす停車駅の選び方が何通りあるかを求めるものです。

問題の解説

列車は地点Xから地点Yまで走行し、その区間にはn個の駅があります。このうちr個の駅に停車しますが、隣接する2つの駅に続けて停車することはできないという制約が課されています。

この条件を満たす選び方の総数は、組合せの公式を使って直接求められます。まず、停車しない（n−r）個の駅を一列に並べると、両端を含めて（n−r+1）個の「隙間」が生まれます。この隙間からr個を選んで停車駅を配置すれば、停車駅どうしが隣接することはありません。したがって、求める組み合わせの数は次の式で表されます。

C(n−r+1, r) = (n−r+1)! ∕ (r! × (n−2r)!)

計算例

入力 : n = 16 , r = 6
出力 : 462

解説 − 16駅のうち6駅に、どの2駅も連続しないように停車する方法の数は、上記の公式により次のように求まります。

C(16−6+1, 6) = C(11, 6) = 11! ∕ (6! × 5!) = 462

アルゴリズム

入力 : 駅の総数 n と、列車が停車する駅の数 r
手順1 : 分子 (n−r+1) × (n−r) × … × (n−2r+2) と、分母 r! を計算する
手順2 : 分子 ÷ 分母 の値を出力する
補足 : n−r+1 ＜ r の場合、条件を満たす停車駅の選び方は存在しない

C言語による実装例

#include <stdio.h>

int main(void) {
    int n = 16, s = 6;   /* n: 駅の総数、s: 停車駅の数 */

    printf("Total number of stations = %d\n", n);
    printf("Number of stopping station = %d\n", s);

    int p = s;
    int num = 1, dem = 1;

    /* 分母: s!（階乗）を計算 */
    while (p != 1) {
        dem *= p;
        p--;
    }

    /* 分子: (n-s+1)! / (n-2s+1)! を計算 */
    int t = n - s + 1;
    while (t != (n - 2*s + 1)) {
        num *= t;
        t--;
    }

    /* n-s+1 >= s のときのみ解が存在する */
    if ((n - s + 1) >= s)
        printf("Possible ways = %d\n", num / dem);
    else
        printf("no possible ways\n");

    return 0;
}

実行結果

Total number of stations = 16
Number of stopping station = 6
Possible ways = 462

まとめ

このプログラムでは、階乗を丸ごと計算すると大きな値でオーバーフローしやすいため、必要な範囲だけ分子と分母を掛け合わせて処理しており、計算量はO(r)と非常に効率的です。より大きなnやrに対応したい場合は、int型ではなくlong long型などの大きな整数型を使用することをおすすめします。