C++を使用して停止ステーションの数を見つける

ポイントXとYの間にn個の中間駅があります。2つの駅が隣接しないように、s駅に停車するように列車を配置できるさまざまな方法の数を数えます。そのため、この記事では、停車駅の数を見つけるためのあらゆる可能なアプローチについて説明します。問題を見ると、sの駅数で列車を止めることができる組み合わせを見つける必要があることがわかります。

問題を解決するためのアプローチ

中間駅が8つあり、3つの中間駅で電車を止める方法を見つける必要がある例を見てみましょう。

n = 8, s = 3

（n-s）、つまり電車が止まらない駅が5つ残っています

電車が止まらないA、B、C、D、Eの5つの駅があります。これで、2つの駅が連続しないように、3つの停車駅を配置するための6つの点線の場所ができました。したがって、方法の数は-

6c3= [fact(6) - fact(3)] / fact(3) = 6 * 5 * 4 / 3 * 2 * 1 = 20

ポイントXとYから3つの停車駅を配置する方法は20あります。ここに例があります-

Input : n = 15 s = 4
Output : 495
Input : n = 8 s = 3
Output : 20

例

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n = 8, s = 3;
    int flag1 = 1, flag2 = 1, temp = s, ans;
    // selecting 's' positions out of 'n-s+1'
    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の値を一時変数に格納します。

• 分子[fact（n）-fact（r）]であるflag1を計算しています。

• 分母であるflag2を計算する[fact（r）]

• 結果を印刷します。

結論

この記事では、2つの駅が連続しないように、中間駅で列車を停止できる方法の数を見つけるために問題を解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチについても学びました。同じプログラムをC、Java、Python、その他の言語などの他の言語で作成できます。