ปัญหามีอยู่ว่า
นักเรียน 18 คนที่สูงต่างกันทั้งหมดยืนเข้าแถวตอนเพื่อเคารพธงชาติ ครูประจำชั้นต้องการให้นักเรียนยืนเรียงตามลำดับความสูงโดยให้นักเรียนที่สูงที่สุดอยู่ท้ายแถว เมื่อครูเดินตรวจแถว หากพบว่า นักเรียนที่ยืนติดกันนั้นเรียงลำดับความสูงไม่ถูกต้อง ก็จะทำการสลับตำแหน่งนักเรียนคู่ที่พบนั้น แล้วเดินตรวจเรื่อยๆ จนกว่านักเรียนจะเรียงลำดับความสูงได้ถูกต้องทั้งหมด ถ้าครูต้องสลับตำแหน่งนักเรียนทั้งหมด 150 คู่ แล้วนักเรียนจะเข้าแถวได้แตกต่างกันทั้งหมดกี่วิธี
ผมคิดด้วยมือได้แล้วไม่ชัวร์ เพราะไม่รู้จะตรวจสอบยังไงดี เขียนโปรแกรมก็ไม่ว่างพอ ไม่เก่งด้วย (หมายเหตุ ปัญหาที่ผมถาม หยิบมาจาก TMO ครั้งที่ 1 , สอบเมื่อ 2 พ.ค. 2547)
อ้อ.ลืมบอกไป ผมคิดแล้วได้ 951 วิธีครับ.
ข้อนี้ใช้โปรแกรมหาจำนวนการจัดเรียงที่เป็นไปได้ทั้งหมดจะใช้เวลานานมากครับ (18! = 6.40E+15 วิธี)
ผมจึงสร้างโปรแกรมที่ใช้คำนวณจำนวนคู่ของการสลับตำแหน่งจากการรูปแบบการเข้าแถวของนักเรียนรูปแบบ หนึ่ง ๆ ขึ้นแทน เช่น ถ้าการจัดเรียงแถวของนักเรียนเป็น
หัวแถว 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 ท้ายแถว
ครูต้องสลับตำแหน่งนักเรียนทั้งหมด 153 ครั้ง (153 คู่) โดยจะเริ่มสลับจากหัวแถวไปท้ายแถว และเริ่มสลับ จากท้ายแถวกลับขึ้นมาหัวแถวอีก วนเวียนไปเช่นนี้ กระทั่งได้รูปแบบการจัดเป็น
หัวแถว 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ท้ายแถว ครับ
ผมหาจำนวนวิธีที่นักเรียนจะเข้าแถวแตกต่างกันได้ทั้งหมด 16 วิธี ที่จะต้องผ่านการสลับตำแหน่ง 150 ครั้ง ตามวิธีที่อธิบายไว้ข้างต้น ดังต่อไปนี้ครับ
16 17 18 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
18 15 16 17 14 13 12 11 10 9 8 7 6 5 4 3 2 1
18 17 14 15 16 13 12 11 10 9 8 7 6 5 4 3 2 1
18 17 16 13 14 15 12 11 10 9 8 7 6 5 4 3 2 1
18 17 16 15 12 13 14 11 10 9 8 7 6 5 4 3 2 1
18 17 16 15 14 11 12 13 10 9 8 7 6 5 4 3 2 1
18 17 16 15 14 13 10 11 12 9 8 7 6 5 4 3 2 1
18 17 16 15 14 13 12 9 10 11 8 7 6 5 4 3 2 1
18 17 16 15 14 13 12 11 8 9 10 7 6 5 4 3 2 1
18 17 16 15 14 13 12 11 10 7 8 9 6 5 4 3 2 1
18 17 16 15 14 13 12 11 10 9 6 7 8 5 4 3 2 1
18 17 16 15 14 13 12 11 10 9 8 5 6 7 4 3 2 1
18 17 16 15 14 13 12 11 10 9 8 7 4 5 6 3 2 1
18 17 16 15 14 13 12 11 10 9 8 7 6 3 4 5 2 1
18 17 16 15 14 13 12 11 10 9 8 7 6 5 2 3 4 1
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 1 2 3
ทั้ง 16 วิธีดังกล่าวผ่านการตรวจสอบจากโปรแกรมแล้วว่า ต้องสลับตำแหน่ง 150 ครั้งครับ
เนื่องจากคุณ mrgon หาได้ถึง 951 วิธี คงต้องนำมาตรวจสอบกับโปรแกรมก่อนครับว่า ถูกต้องตามเงื่อนไขโจทย์หรือไม่ครับ
วิธีการใช้โปรแกรม
เมื่อดาวน์โหลดโปรแกรมจากลิงก์ข้างบนแล้ว ให้บันทึกไฟล์เก็บไว้ใน disk หรือ harddrive ต่างหาก ก่อนที่จะรันโปรแกรมครับ และทุกครั้งที่จะรันโปรแกรมให้กด enable macro ก่อน
โปรแกรมมีอยู่ด้วยกัน 2 worksheets ครับ คือ RandomSearch และ Result
ควรใช้ EXCEL2000 หรือสูงกว่าในการรันโปรแกรมนี้ครับ ถ้าใช้ EXCEL 97 อาจเกิดปัญหา
ใน Worksheets RandomSearch ผู้ใช้อาจกดปุ่ม Click to Operate เพื่อให้โปรแกรมยกตัวอย่างการจัดเรียง แถวของนักเรียนทั้ง 18 คน (อยู่ในแถวที่ 2 ของ Worksheet) และตรวจสอบจำนวนการสลับตำแหน่งที่เป็น ไปได้ทั้งหมด อย่างในภาพตัวอย่างข้างล่าง จำนวนการสลับตำแหน่งคือ 86 วิธี
ผู้ใช้อาจป้อนการจัดเรียงแถวใด ๆ ขึ้นเอง (มีข้อแม้ว่าต้องเป็นตัวเลขระหว่าง 1-18 เท่านั้น และต้องไม่ซ้ำกัน ตัวโปรแกรมยังไม่ได้รับการออกแบบถึงขั้น trap errors ได้ครับ เพราะเวลามีจำกัด) โดยป้อนใน Worksheet RandomSearch แถว 1 ระหว่างคอลัมน์ A ถึง R แล้วกดปุ่ม Check Pair No.
ถ้ามีข้อมูลที่ต้องการตรวจสอบมากกว่าหนึ่งชุด ให้ใช้ Worksheet Result แทนครับ หลังจากป้อนรายละเอียด
การจัดเรียงแถวแล้วให้กดปุ่ม Check No. of swapped pair
