Tìm số trạm dừng bằng C ++

Có n số ga xe lửa trung gian giữa điểm X và điểm Y. Hãy đếm số cách sắp xếp các đoàn tàu khác nhau để dừng tại các ga sao cho không có hai ga nào ở cạnh nhau. Vì vậy, trong bài viết này, chúng tôi sẽ giải thích mọi cách tiếp cận có thể có để tìm ra số lượng trạm dừng. Xem xét vấn đề, chúng ta có thể thấy rằng chúng ta cần tìm các tổ hợp mà các đoàn tàu có thể dừng ở số ga.

Phương pháp giải quyết vấn đề

Hãy lấy một ví dụ rằng có tám ga trung gian và chúng ta cần tìm cách dừng các chuyến tàu ở ba ga trung gian.

n = 8, s = 3

Chúng ta còn (n - s), tức là còn lại năm ga mà tàu không thể dừng,

Chúng tôi có năm ga A, B, C, D, E, trên đó các chuyến tàu không thể dừng. Bây giờ chúng tôi có sáu vị trí rải rác để bố trí ba trạm dừng sao cho không có hai trạm liên tiếp. Do đó, số cách là -

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

Có 20 cách để bố trí ba trạm dừng từ điểm X và Y. Đây là ví dụ -

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

Ví dụ

#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;
}

Đầu ra

Number of ways : 20

Giải thích về Quy tắc trên

Để hiểu mã C ++ này, chúng ta có thể chia giải pháp thành các bước.

• Lấy số lượng trạm trong n và dừng các trạm ở dạng đầu vào.

• Khởi tạo flag1 và gắn cờ 2 biến bằng 1 và lưu trữ giá trị của s trong một biến tạm thời.

• Tính cờ1 là tử số [fact (n) - fact (r)].

• Tính flag2 là mẫu số [fact (r)]

• Kết quả in.

Kết luận

Trong bài này, chúng ta giải một bài toán để tìm số cách các đoàn tàu có thể dừng lại trên các ga trung gian sao cho không có hai ga nào liên tiếp nhau. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác.