Site hosted by Angelfire.com: Build your free website today!

โปรแกรมแก้โจทย์ปัญหาของโจเซฟัส
(Josephus Problem Solver)

สวัสดีครับเพื่อน ๆ ชาวหว้ากอทุกท่าน จากกระทู้ Josephus

คุณช่างไฟ และคุณ packham ได้เฉลยและยกตัวอย่างวิธีแก้โจทย์ปัญหาของโจเซฟัส ตัวอย่างโจทย์ ปัญหาทำนองนี้คือ ถ้ามีสมาชิก m คน จัดแถวเรียงหนึ่ง แล้วให้คนที่หนึ่งเริ่มนับ 1 คนที่สองนับ 2 ไปจน ถึงคนที่ n แล้วคัดคนที่ n ออก และให้คนที่ n + 1 เริ่มนับ 1 ใหม่ คนที่ n + 2 นับ 2 ไปเรื่อย ๆ จนวกกลับ มาหาคนที่หนึ่งใหม่ โดยใครที่นับ n จะถูกคัดออกไปเรื่อย ๆ ด้วยวิธีการคัดออกนี้ ในที่สุดก็จะเหลือสมาชิก เพียง 1 คน ปัญหาคือ ถ้าจะให้อยู่รอดเป็นคนสุดท้าย เราควรจะไปอยู่ที่ตำแหน่งไหนดี ?

เพื่อให้เห็นตัวอย่างชัดเจนขึ้นดูภาพข้างล่างครับ ในกรณีมีสมาชิก 12 คน และให้นับถึง 7 จะเห็นว่าถ้าจะ ให้อยู่รอดเป็นคนสุดท้าย จะต้องยืนอยู่ในตำแหน่งที่ 12

ในกรณีที่มีสมาชิก m คน แล้วให้นับถึง 2 นั้น ได้มีผู้หาสูตรทั่วไปไว้แล้ว ดังในเอกสารอ้างอิงนี้ครับ ที่คุณ packham ได้ให้ไว้ ที่นี่

คำถามในกระทู้ที่แล้วคือ คนที่รอดเป็นคนสุดท้าย ในกรณีมีสมาชิก 50000 คน และให้นับถึง 7 เป็นคนที่ยืน อยู่ในตำแหน่งไหน

เพื่อพิสูจน์คำตอบนี้เราจำเป็นต้องใช้คอมพิวเตอร์มาช่วยแก้ปัญหา ซึ่งเราสามารถใช้ EXCEL2000 และ VBA6.0 ในการณ์นี้ได้อีกเช่นเคยครับ, dialog box ข้างล่างสาธิตการใช้โปรแกรมสำหรับคำถามข้างบน ซึ่งตัวโปรแกรมจะแสดง progress bar, เวลาที่ผ่านไปนับจากเริ่มการวิเคราะห์, และประมาณเวลาที่เหลือ ก่อนโปรแกรมจะรันเสร็จไว้ด้วย พร้อมทั้งแสดงรายละเอียดสมาชิกที่กำลังถูกคัดออก รอบที่วน และจำนวน สมาชิกที่เหลืออยู่ เพื่อน ๆ สามารถใช้โปรแกรมนี้สำหรับกรณีที่มีสมาชิกตั้งแต่ 2 จึงถึง 50000 คน ครับ และ อาจให้นับถึงตั้งแต่ 2 ไปจนถึง 20

เค้าโครงของโปรแกรมที่ใช้เป็นดังนี้ครับ

ตัวอย่างกราฟแสดงความสัมพันธ์ระหว่างตำแหน่งของสมาชิกที่เหลือรอดเป็นคนสุดท้าย (L(m,7)) กับจำนวนสมาชิก ซึ่งคำนวณไว้จนถึง 100 คน จากการให้นับถึง 7

ในกรณีที่มีสมาชิกในหลักร้อยหรือพัน เวลาที่ใช้คำนวณจะไม่นาน แต่ถ้าถึงหลักหมื่นอาจใช้เวลาเป็นชั่วโมง สำหรับ Pentium-2 ครับ (สำหรับโจทย์ปัญหาที่มีสมาชิก 50,000 คนจะใช้เวลา 2 ชั่วโมง)

คำตอบที่ได้ครับ คนที่รอดเป็นคนสุดท้าย ในกรณีมีสมาชิก 50000 คน และให้นับถึง 7 เป็นคนที่ยืนอยู่ในตำแหน่ง 38,699

การแก้ปัญหาโดยตรง จะช้าครับ ซึ่งคุณ packham ได้แนะนำวิธีแก้ปัญหาที่เร็วขึ้น โดยการใช้ความสัมพันธ์ แบบเวียนบังเกิด โดยค่อย ๆ นับขึ้นจากกรณีที่เราทราบคำตอบ ที่มีสมาชิก m จำนวนน้อย ๆ ตัวอย่างเช่น ถ้ามีสมาชิก 30 คน และนับถึง 7 เราทราบว่าในกรณีที่มีสมาชิก 3 คน คนที่เหลือรอดคนสุดท้ายคือ คนที่ 3

ในกรณีที่มีสมาชิก 4 คน, เราเริ่มนับจาก 7 mod 4 + 1 = 4, 1, 2 เนื่องจากคนที่ 3 คือคนที่ยืนอยู่บนตำแหน่งที่ 2
ดังนั้นในกรณีที่มีสมาชิก 4 คน คนที่เหลือรอดคนสุดท้ายคือคนที่ 2

ในกรณีที่มีสมาชิก 5 คน, เราเริ่มนับจาก 7 mod 5 + 1 = 3, 4 เนื่องจากคนที่ 2 คือคนที่ยืนอยู่บนตำแหน่งที่ 4
ดังนั้นในกรณีที่มีสมาชิก 5 คน คนที่เหลือรอดคนสุดท้ายคือคนที่ 4

ในกรณีที่มีสมาชิก 6 คน เราเริ่มนับจาก 7 mod 6 + 1 = 2, 3, 4, 5 เนื่องจากคนที่ 4 คือคนที่ยืนอยู่บนตำแหน่งที่ 5
ดังนั้นในกรณีที่มีสมาชิก 6 คน คนที่เหลือรอดคนสุดท้ายคือคนที่ 5

ในกรณีที่มีสมาชิก 7 คน เราเริ่มนับจาก 1, 2, 3, 4, 5 เนื่องจากคนที่ 5 คือคนที่ยืนอยู่บนตำแหน่งที่ 5
ดังนั้นในกรณีที่มีสมาชิก 7 คน คนที่เหลือรอดคนสุดท้ายคือคนที่ 5

ในกรณีที่มีสมาชิก 8 คน เราเริ่มนับจาก 8, 1, 2, 3, 4 เนื่องจากคนที่ 5 คือคนที่ยืนอยู่บนตำแหน่งที่ 4
ดังนั้นในกรณีที่มีสมาชิก 8 คน คนที่เหลือรอดคนสุดท้ายคือคนที่ 4

ในกรณีที่มีสมาชิก 9 คน เราเริ่มนับจาก 8, 9, 1, 2 เนื่องจากคนที่ 4 คือคนที่ยืนอยู่บนตำแหน่งที่ 2
ดังนั้นในกรณีที่มีสมาชิก 9 คน คนที่เหลือรอดคนสุดท้ายคือคนที่ 2

ฯลฯ กระทั่งถึงสมาชิกคนที่ 30 เราก็จะได้คำตอบ

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

ตัวโปรแกรมแก้ปัญหาโจเซฟัส ฉบับปรับปรุง

เพื่อน ๆ สามารถเลือกความเร็วของการคำนวณได้จากปุ่ม “Dawdling” สำหรับการคำนวณแบบปกติ และ “Expeditious” สำหรับการคำนวณที่รวดเร็วขึ้น ครับ ในกรณีที่จะใช้เวลามากกว่า 5 นาทีในการคำนวณ โหมด “Dawdling” จะถูกเปลี่ยนเป็น “Expeditious” โดยอัตโนมัติ ภาพข้างล่างแสดงการคำนวณใน โหมด “Dawdling” สำหรับ L(1000,7) ครับ