โปรแกรม C หาจำนวนวิธีการหยุดรถไฟที่สถานี (Stopping Station Problem)

โจทย์

หาจำนวนวิธีที่รถไฟจะหยุดที่ r สถานี จาก n สถานี ทั้งหมด โดยเงื่อนไขคือ ไม่มีสองสถานีที่หยุดติดกัน

ตัวอย่าง

Input: n = 16, r = 6
Output: 462

คำอธิบาย

ใช้สูตรจัดเรียง (Permutation): ⁿP_r = n! / (n-r)!
แต่ปัญหานี้เป็นการเลือก r สถานีจาก n สถานี โดยไม่ให้ติดกัน ซึ่งเทียบเท่ากับการเลือก r ตำแหน่งจาก (n-r+1) ช่องว่าง

จำนวนวิธี = C(n-r+1, r) = (n-r+1)! / (r! × (n-2r+1)!)

อัลกอริทึม

1. รับค่า n (สถานีทั้งหมด) และ r (จำนวนสถานีที่หยุด)
2. คำนวณ p(n,r) = n! / (n-r)! แบบปรับเปลี่ยนสำหรับเงื่อนไขไม่ติดกัน
3. ถ้า (n-s+1) >= s ให้คำนวณและแสดงผล มิฉะนั้นแสดง "no possible ways"

โค้ดภาษา C

#include <stdio.h>

int main() {
    int n = 16, s = 6;
    printf("Total number of stations = %d\nNumber of stopping station = %d\n", n, s);
    
    int p = s;
    int num = 1, dem = 1;
    
    // คำนวณตัวส่วน r!
    while (p != 1) {
        dem *= p;
        p--;
    }
    
    // คำนวณตัวเศษ (n-s+1) × ... × (n-2s+2)
    int t = n - s + 1;
    while (t != (n - 2*s + 1)) {
        num *= t;
        t--;
    }
    
    if ((n - s + 1) >= s)
        printf("Possible ways = %d", num / dem);
    else
        printf("no possible ways");
    
    return 0;
}

ผลลัพธ์

Total number of stations = 16
Number of stopping station = 6
Possible ways = 462