มีสถานีรถไฟกลางจำนวน n แห่งระหว่างจุด X และ Y นับจำนวนวิธีต่างๆ ที่รถไฟสามารถจัดให้จอดที่สถานีต่างๆ ได้ เพื่อไม่ให้มีสถานีสองแห่งอยู่ติดกัน ดังนั้นในบทความนี้ เราจะอธิบายทุกแนวทางที่เป็นไปได้เพื่อค้นหาจำนวนสถานีที่หยุดรถ เมื่อพิจารณาจากปัญหาแล้ว เราจะพบว่าต้องหาชุดค่าผสมที่สามารถหยุดรถไฟได้ตามจำนวนสถานี
แนวทางการแก้ปัญหา
มาดูตัวอย่างกันว่ามีสถานีกลางแปดแห่งและเราต้องหาวิธีที่จะหยุดรถไฟที่สถานีกลางสามสถานี
n = 8, s = 3
เรามี (n - s) คือ เหลืออีกห้าสถานีที่รถไฟไม่สามารถหยุดได้
เรามีห้าสถานี A, B, C, D, E ซึ่งรถไฟไม่สามารถหยุดได้ ตอนนี้ เรามีจุดจุดหกจุดเพื่อจัดสถานีหยุดสามแห่ง เพื่อไม่ให้มีสถานีสองแห่งติดต่อกัน ดังนั้น จำนวนวิธีคือ −
6c3= [fact(6) - fact(3)] / fact(3) = 6 * 5 * 4 / 3 * 2 * 1 = 20
มี 20 วิธีในการจัดเรียงสถานีหยุดสามแห่งจากจุด 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;
// 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;
} ผลลัพธ์
Number of ways : 20
คำอธิบายของโค้ดด้านบน
เพื่อให้เข้าใจโค้ด C++ นี้ เราสามารถแบ่งโซลูชันออกเป็นขั้นตอนได้
-
การนับจำนวนสถานีใน n และสถานีหยุดใน s เป็นอินพุต
-
การเริ่มต้นตัวแปร flag1 และ flag 2 ด้วย 1 และเก็บค่าของ s ไว้ในตัวแปร temp
-
กำลังคำนวณ flag1 ซึ่งเป็นตัวเศษ [fact(n) - fact(r)].
-
กำลังคำนวณ flag2 ซึ่งเป็นตัวส่วน [fact(r)]
-
ผลการพิมพ์
บทสรุป
ในบทความนี้ เราแก้ปัญหาเพื่อค้นหาจำนวนวิธีที่รถไฟสามารถหยุดบนสถานีกลางได้ โดยจะไม่มีสองสถานีต่อเนื่องกัน นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ
