Tìm số cách dừng tàu tại các ga trung gian bằng C++

Cho n ga trung gian giữa hai điểm X và Y. Hãy đếm số cách sắp xếp dừng tàu tại s ga sao cho không có hai ga nào liền kề nhau. Bài toán này quy về việc tìm tổ hợp chọn s vị trí từ n - s + 1 vị trí có thể.

Phân tích bài toán

Ví dụ: n = 8, s = 3. Có n - s = 5 ga không dừng. Ta có 5 ga A, B, C, D, E không dừng, tạo ra 6 khoảng trống (kể cả hai đầu) để đặt 3 ga dừng sao cho không liền kề. Số cách = C(6, 3) = 20.

n = 8, s = 3
Số cách = C(6, 3) = 6! / (3! * 3!) = 20

Ví dụ khác:

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

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 8, s = 3;
    int flag1 = 1, flag2 = 1, temp = s, ans;
    int x = n - s + 1; // chọn s vị trí từ 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 << "Số cách: " << ans;
    else
        cout << "Không thể tìm thấy";
    return 0;
}

Kết quả

Số cách: 20

Giải thích mã nguồn

• Nhập số ga n và số ga dừng s.
• Khởi tạo flag1, flag2 = 1, temp = s.
• Tính tử số flag1 = tích từ n-s+1 xuống n-2s+2.
• Tính mẫu số flag2 = s!.
• Kết quả ans = flag1 / flag2.
• Kiểm tra điều kiện n - s + 1 >= s (tức n >= 2s - 1) để đảm bảo có thể sắp xếp.

Kết luận

Bài viết giải quyết bài toán đếm số cách dừng tàu tại các ga trung gian không liền kề bằng tổ hợp toán học. Độ phức tạp O(s). Mã nguồn C++ và cách tiếp cận toán học đã được trình bày chi tiết. Có thể triển khai bằng các ngôn ngữ khác.