Practical Algorithms Logo Practical Algorithms
• 18 min

ตามหาลูกเป็ดในปราสาท

จะเดินตามหาลูกเป็ดให้เจอในห้อง 9 ห้องได้ยังไงใน 14 วัน ถ้าเปิดประได้แค่ทีละห้องต่อวัน

เป็ดไอคอนของเรื่องเล่าชาวอัลกอ Practical Algorithms
Practical Algorithms: เรื่องเล่าชาวอัลกอ
เพจที่อยากให้คนไทยมีเนื้อหาอัลกอริทึมดีๆ ให้ได้อ่านกัน
Pre-Posn Math
ลูกเป็ดชาวอัลกอใส่มงกุฎ นั่งอยู่หน้าปราสาท

โจทย์

มีปราสาทอยู่แห่งหนึ่งมีห้องที่ติดกันอยู่ทั้งหมด 9 ห้อง ห้องจะเริ่มจากหมายเลขที่ 1 และจบที่หมายเลขที่ 9

ห้องทุกห้องจะเชื่อมกับหมายเลขที่ติดกันเรียงจากซ้ายไปขวา เช่น ห้องที่ 2 จะเชื่อมกับห้องที่ 1 และ 3 ยกเว้นห้องปลายสุดคือห้องที่ 1 กับห้องที่ 9 จะเชื่อมกับแค่ห้องที่ 2 และห้องที่ 8 ตามลำดับ

มีลูกเป็ดแอบนอนอยู่ในห้องใดห้องหนึ่งในคืนที่ 1 หลังจบในแต่ละคืน ลูกเป็ดจะต้องเดินไปห้องข้างๆ อย่างเช่น ถ้าคืนที่ ii อยู่ห้องที่ 5 คืนที่ i+1i+1 จะอยู่ห้องที่ 4 ไม่ก็ห้องที่ 6 แน่ๆ เราต้องการหาว่าลูกเป็ดอยู่ที่ห้องไหนกันแน่ โดยแต่ละคืนเราจะสามารถเปิดห้องได้ 1 ห้องเพื่อตามหาว่าลูกเป็ดอยู่ไหน ถามว่าภายในเวลา 14 วัน สามารถเปิดประตูตรงกับห้องที่มีลูกเป็ดแอบอยู่ในวันนั้นได้หรือไม่

เฉลย

สิ่งที่ต้องสังเกตอย่างแรกคือ เรามีโอกาสเปิดเจอตั้งแต่วันแรกไหม

คำตอบคือ: ก็มีโอกาสแหละ (แต่ก็น้อยนะ)

แล้วถ้าจะเปิดสุ่มไปเรื่อยๆแบบไม่สนอะไรเลย จะเจอไหม ก็เหมือนกันว่าเป็นไปได้ แต่ไม่ได้การันตีนะ ก่อนอื่นต้องลองถามตัวเองดูก่อนว่า

การเปิดแต่ละห้องให้ข้อมูลอะไรกับเราบ้างในวันถัดๆไป?

สังเกตก่อนว่าการถามห้องแรก และห้องสุดท้ายไม่มีประโยชน์อะไรเลย เพราะถ้าลูกเป็ดไม่ได้อยู่ห้องนั้น แล้วยังไงต่อล่ะ?

1
2
3
4
5
6
7
8
9

ลองถามห้องที่ 1 ดูว่าได้อะไรไหม

คืนถัดไปลูกเป็ดก็อยู่ห้องไหนก็ได้อยู่ดี (แต่ percent ของแต่ละห้องไม่เท่ากันนะ) เราก็ไม่ได้ข้อมูลอย่างอื่นเพิ่มมาอยู่ดี

1
2
3
4
5
6
7
8
9

เปลี่ยนไปถามห้องที่ 2 แทนในวันแรก

ทีนี้ถ้าเปลี่ยนใหม่มาถามห้องที่ 2 ก่อน เราจะได้อะไรบ้าง ถ้าลูกเป็ดอยู่เลยก็โชคดีไป แต่เราต้องการรับประกันว่าจะหาให้เจอ ดังนั้นจะไม่คิดกรณีเจอทันทีไว้ก่อนนะ แต่ถ้าลูกเป็ดไม่อยู่มันแปลว่าอะไรล่ะ

1
2
3
4
5
6
7
8
9

ในคืนที่ 2 ห้องที่ 1 จะไม่มีลูกเป็ดอยู่

เนื่องจากว่าห้องที่ 1 มาได้ทางเดียวจากห้องที่ 2 และเรารู้ว่าในคืนแรกลูกเป็ดไม่ได้อยู่ห้องที่ 2 ดังนั้น เราก็มั่นใจได้ว่า ในคืนถัดไปห้องที่ 1 จะไม่มีลูกเป็ดอยู่แน่ ทำให้เราจะเหลือแค่ห้องที่ 2 - 9 ที่มีความเป็นไปได้ว่าลูกเป็ดจะอยู่ในคืนถัดมา

1
2
3
4
5
6
7
8
9

ในคืนที่ 2 เราจะถามห้องที่ 3

1
2
3
4
5
6
7
8
9

ในคืนที่ 2 ถ้าห้องที่ 1 และ 3 ไม่มีลูกเป็ดอยู่ ห้องที่ 2 ในคืนที่ 3 จะไม่มีใครอยู่แน่ๆ

หลังจากนั้นจะถามห้องที่ 3 ต่อ เพราะว่า ถ้าลูกเป็ดไม่อยู่ห้องที่ 3 ในคืนถัดไป ห้องที่ 2 จะไม่มีใครอยู่แน่ๆ เพราะว่าห้องที่ 2 สามารถมาได้จากห้องที่ 1 และ 3 เท่านั้น เราก็จะเหลือแค่ห้องที่ 1 (จากการเดินมาจากห้อง 2) และห้องที่ 3 - 9 ที่เป็นไปได้ว่าลูกเป็ดจะอยู่ในคืนถัดมา

1
2
3
4
5
6
7
8
9

ในคืนที่ 3 เราจะถามห้องที่ 4

หลังจากนั้นจะถามห้องที่ 4 ต่อ ซึ่งทำให้เรามั่นใจแล้วว่าห้องที่ 2 และ 4 ไม่มีใครอยู่ ดังนั้นก็สามารถสรุปต่อไปว่าในคืนถัดไป ห้องที่ 1 และ 3 จะไม่มีใครอยู่แน่ๆ

และเราสามารถตรวจสอบแบบนี้ต่อไปได้เรื่อยๆจนถึงห้องที่ 8

1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9

ไล่ตรวจสอบเรียงไปเรื่อยๆถึงห้องที่ 8

ตอนนี้ใช้ไปแล้วทั้งหมด 7 วัน และมั่นใจได้ว่าลูกเป็ดไม่อยู่ห้องที่ 2, 4, 6 และ 8 แน่ๆ ซึ่งในคืนถัดไปก็แปลว่า ในคืนถัดไป เราจะมั่นใจได้ว่าห้องเลขคี่จะไม่มีลูกเป็ดอยู่

1
2
3
4
5
6
7
8
9

ห้องในคืนที่ 8

ที่เหลืออีก 7 วันเหมือนไล่เก็บตกมากกว่าว่าห้องไหนที่ตอนนี้เป็นไปได้บ้าง ซึ่งเราจะเช็กห้องไหนก็ได้ที่ตอนนี้มีความเป็นไปได้ แต่ต้องเรียงจากซ้ายไปขวา หรือ ขวาไปซ้ายนะ เพื่อว่าลูกเป็ดจะได้ไม่มีทางเดินสวนกับเราได้

1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9

ไล่ถามเก็บตกห้องที่เหลือไปเรื่อยๆ

วิธีนี้ก็จะใช้อีกทั้งหมด 7 วัน รวมเป็นทั้งหมด 14 วันตามที่โจทย์กำหนดพอดี

โจทย์เพิ่มเติม

  • ถ้าเปลี่ยนเงื่อนไขเป็นถามกี่ห้องก็ได้ที่ติดกัน เช่นถามห้องช่วง 1 ถึง 5 ไปเลย จะต้องใช้เวลาน้อยสุดกี่วันในการหาว่าลูกเป็ดอยู่ห้องไหน โดยที่จะนับว่าเจอห้องที่มีลูกเป็ดอยู่เมื่อเปิดประตูห้องนั้นเพียงห้องเดียวแล้วเจอเลย โดยไม่ต้องเปิดประตูห้องอื่น
แชร์หน่อยก๊าบ ⊹
  • คัดลอกแล้ว!
0