Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++를 사용하여 정류장 수 찾기

<시간/>

지점 X와 Y 사이에 n개의 중간 기차역이 있습니다. 두 개의 역이 서로 인접하지 않도록 기차가 s개의 역에 정차하도록 배열할 수 있는 다양한 방법의 수를 세십시오. 따라서 이 기사에서는 정류장 수를 알아내기 위해 가능한 모든 접근 방식을 설명합니다. 문제를 살펴보면 기차가 여러 역에서 멈출 수 있는 조합을 찾아야 함을 알 수 있습니다.

문제 해결을 위한 접근 방식

예를 들어 8개의 중간 역이 있고 기차가 3개의 중간 역에서 멈출 수 있는 방법을 찾아야 합니다.

n = 8, s = 3

(n - s), 즉 기차가 멈출 수 없는 5개의 역이 남아 있습니다.

C++를 사용하여 정류장 수 찾기

우리는 기차가 정차할 수 없는 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 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.