Đề bài
Tìm số cách tàu dừng tại r trạm trong n trạm sao cho không có hai trạm dừng liên tiếp.
Giải thích
Tàu đi từ X đến Y, giữa có n trạm. Chọn r trạm dừng không liên tiếp. Số cách = tổ hợp C(n-r+1, r) hoặc hoán vị tùy phiên bản.
Ví dụ: n=16, r=6 → 462 cách.
Thuật toán
Input: n, r Bước 1: Tính p(n,r) = n! / (n-r)! Bước 2: In kết quả
Mã nguồn C
#include <stdio.h>
int main() {
int n = 16, s = 6;
printf("Tổng trạm: %d\nTrạm dừng: %d\n", n, s);
int p = s;
int num = 1, dem = 1;
while (p != 1) { dem *= p; p--; }
int t = n - s + 1;
while (t != (n - 2*s + 1)) { num *= t; t--; }
if ((n - s + 1) >= s)
printf("Số cách = %d", num / dem);
else
printf("Không có cách nào");
return 0;
}
Kết quả
Tổng trạm: 16 Trạm dừng: 6 Số cách = 462