지점 X와 Y 사이에 n개의 중간 기차역이 있습니다. 두 개의 역이 서로 인접하지 않도록 기차가 s개의 역에 정차하도록 배열할 수 있는 다양한 방법의 수를 세십시오. 따라서 이 기사에서는 정류장 수를 알아내기 위해 가능한 모든 접근 방식을 설명합니다. 문제를 살펴보면 기차가 여러 역에서 멈출 수 있는 조합을 찾아야 함을 알 수 있습니다.
문제 해결을 위한 접근 방식
예를 들어 8개의 중간 역이 있고 기차가 3개의 중간 역에서 멈출 수 있는 방법을 찾아야 합니다.
n = 8, s = 3
(n - s), 즉 기차가 멈출 수 없는 5개의 역이 남아 있습니다.
우리는 기차가 정차할 수 없는 5개의 역 A, B, C, D, E가 있습니다. 이제 우리는 두 개의 역이 연속되지 않도록 세 개의 중지 역을 배열하기 위해 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을 계산 중입니다.
-
분모[fact(r)]
인 flag2 계산 -
인쇄 결과입니다.
결론
이 기사에서는 두 개의 역이 연속적이지 않도록 기차가 중간 역에서 멈출 수 있는 방법의 수를 찾는 문제를 풉니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.