โจทย์คลาสสิก: มีผู้โดยสาร n คน** ขึ้นเครื่องบินที่มีที่นั่ง **n ที่นั่ง** (หมายเลข 1 ถึง n) ผู้โดยสารคนแรก **สูญเสียตั๋ว** จึงนั่งสุ่ม ที่นั่งใดก็ได้ ผู้โดยสารคนต่อๆ ไปจะทำตามกติกา:
- หากที่นั่งของตัวเองว่าง -> นั่งที่นั่งของตัวเอง
- หากที่นั่งของตัวเองมีคนนั่งแล้ว -> **สุ่ม** เลือกที่นั่งว่างที่เหลือ
โจทย์: หาความน่าจะเป็นที่ **ผู้โดยสารคนที่ n (คนสุดท้าย)** จะได้นั่งที่นั่งของตัวเอง (ที่นั่งหมายเลข n)
ข้อสังเกตสำคัญ (Key Insight)
ปัญหานี้มีคำตอบที่น่าประหลาดใจคือ:
- ถ้า n = 1 -> ความน่าจะเป็น = 1 (คนเดียว นั่งที่เดียว)
- ถ้า n ≥ 2 -> ความน่าจะเป็น = 0.5 (50%) เสมอ!
เหตุผล (Intuition): กระบวนการจะจบลงที่ "ที่นั่งคนแรก" หรือ "ที่นั่งคนสุดท้าย" เท่านั้น โอกาสเท่ากัน
ตัวอย่างโค้ด C++
class Solution {
public:
double nthPersonGetsNthSeat(int n) {
if (n == 1) return 1.0;
return 0.5;
}
};
ตัวอย่าง Input / Output
Input: 2 Output: 0.50000
Input: 100 Output: 0.50000
สรุป
ไม่ต้อง Simulation หรือ DP ซับซ้อน คำตอบคือ 1.0 สำหรับ n=1, และ 0.5 สำหรับ n>1 นี่คือโจทย์ที่ทดสอบ "ความคิด" มากกว่าทักษะเขียนโค้ดครับ
