การสร้าง Swapping Game จากปัญหา swap puzzle

ชื่อนักเรียนผู้จัดทำโครงงานวิทยาศาสตร์

อุษณีย์ เลี่ยวตระกูล, ณิชาภัทร มาตย์แสง, นิวาริน วิโนทัย

อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์

ณัฐวุฒิ ดุมลักษณ์

โรงเรียนที่กำกับดูแลโครงงานวิทยาศาสตร์

โรงเรียนภูเก็ตวิทยาลัย

ปีที่จัดทำโครงงานวิทยาศาสตร์

พ.ศ. 2562

บทคัดย่อโครงงานวิทยาศาสตร์

การสร้าง Swapping game จากปัญหา swap puzzle เป็นโครงงานคณิตศาสตร์ที่ศึกษาเกี่ยวกับขั้นตอนในการแก้ swap puzzle โดยขั้นตอนในการแก้ swap puzzle ใด ๆ โดยรูปแบบทั่วไปให้เป็นตารางเอกลักษณ์ทำได้โดยเขียน cycle จากตารางขนาด m x n หลังจากนั้นเขียนทรานสโพสิชันหลักจาก cycle และนำ

ทรานสโพสิชันหลักมาจำแนกเป็นทรานสโพสิชันย่อย โดยพิจารณาการ swap ตามแถวก่อนตามหลัก สุดท้ายนำ

ทรานสโพสิชันย่อยที่ได้มาทำการสลับตำแหน่งใน swap puzzle จะได้ตารางเอกลักษณ์ ซึ่งผลรวมของจำนวนครั้งในการ swap ทั้งหมดของตารางขนาด m x n คือ ผลรวมของการ swap ย่อยที่เกิดจากทุกๆทรานสโพสิชัน และจากการจัดตารางขนาด n x n ให้ได้เป็นตารางเอกลักษณ์สามารถทำได้โดยหลายวิธี และแต่ละวิธีจะทำให้เกิดจำนวนครั้งในการ swap ที่แตกต่างกัน ซึ่งการจัดโดยรูปแบบตัว S มีจำนวนครั้งของการ swap ที่มากที่สุดที่เกิดขึ้นจากการจัดตารางขนาด n x n เมื่อ n เป็นจำนวนคี่ มีค่าเท่ากับ (n-1)(5n^2-1)/4 )ครั้ง และ เมื่อ n เป็นจำนวนคู่ มีค่าเท่ากับ n(n-1)(5n)/4 ครั้ง จัดโดยรูปแบบทั่วไปมีจำนวนครั้งของการ swap ที่มากที่สุดที่เกิดขึ้นจากการจัดตารางขนาด n x n เมื่อ n เป็นจำนวนคี่ มีค่าเท่ากับ (5n+3)(n+1)^2/2ครั้ง และ เมื่อ n เป็นจำนวนคู่ มีค่าเท่ากับ (n-1)(5n^2-2n-2)/2 ครั้ง และรูปแบบการจัดที่ทำให้เกิดจำนวนครั้งของการ swap ที่น้อยที่สุดคือการจัดในรูปแบบตัว L ซึ่งมีจำนวนครั้งของการ swap ที่มากที่สุดที่เกิดขึ้นจากการจัดตารางขนาด n x n มีค่าเท่ากับ n(7n^2-6n-1)/6ครั้ง เมื่อ n > =2