หาจำนวนวิธีจัดสถานีหยุดรถไฟด้วย C++

มีสถานีรถไฟระหว่างทาง n สถานีระหว่างจุด X และ Y นับจำนวนวิธีจัดรถไฟให้หยุดที่ s สถานี โดยที่ไม่มีสถานีใดอยู่ติดกันสองสถานี ในบทความนี้ เราจะอธิบายทุกวิธีที่เป็นไปได้ในการหาจำนวนสถานีหยุด โดยดูจากโจทย์ เราสามารถสรุปได้ว่าต้องหาการจัดหมู่ (Combination) ที่รถไฟสามารถหยุดที่ s สถานีได้

วิธีการแก้ปัญหา

ลองดูตัวอย่าง: มีสถานีระหว่างทาง 8 สถานี และเราต้องหาวิธีจัดให้รถไฟหยุดที่ 3 สถานีระหว่างทาง

n = 8, s = 3

เรามี (n - s) คือ 5 สถานีที่เหลือซึ่งรถไฟไม่สามารถหยุดได้

เรามี 5 สถานี A, B, C, D, E ที่รถไฟไม่หยุด ตอนนี้เรามี 6 ช่องว่าง (จุดประกาศ) สำหรับจัด 3 สถานีหยุด โดยที่ไม่มีสถานีใดติดกัน จำนวนวิธีคือ:

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

มี 20 วิธีในการจัด 3 สถานีหยุดระหว่างจุด X และ Y ตัวอย่าง:

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;
    // เลือก s ตำแหน่งจาก 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 ไว้ในตัวแปร temp

• คำนวณ flag1 ซึ่งเป็นตัวเศษ [fact(n) - fact(r)]

• คำนวณ flag2 ซึ่งเป็นตัวส่วน [fact(r)]

• แสดงผลลัพธ์

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนวิธีที่รถไฟสามารถหยุดที่สถานีระหว่างทางได้ โดยที่ไม่มีสถานีใดติดกันสองสถานี เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีการแก้ปัญหาทั้งหมด สามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python ได้เช่นกัน