1.5 กรณีศึกษา
ตัวอย่างต่อไปนี้จะใช้แนวคิดเชิงคำนวณในการแก้ปัญหาบางปัญหาอาจไม่ได้ใช้ครบทุกองค์ประกอบ
ขึ้นอยู่กับลักษณะของปัญหา แต่ทุกปัญหาจะต้องได้อัลกอริทึมในการแก้ปัญหาที่ถูกต้อง
รวดเร็ว และมีประสิทธิภาพ
ตัวอย่างที่
1.6 สอนน้องจัดหนังสือ
สมมติว่านักเรียนต้องการสอนน้องให้รู้จักรีการจัดเรียงหนังสือตามลำดับความสูงให้เป็นระเบียบเพื่อให้มีความสวยงามและง่ายต่อการค้นหา
นักเรียนต้องคิดกระบวนการเป็นขั้นตอนออกมา เพื่อให้น้องสามารถปฏิบัติตามได้ง่าย
ไม่ว่าจะมีหนังสือกี่เล่มและมีลำดับเริ่มตันแบบใดก็ได้ นักเรียนจะมีชั้นตอนในการจัดเรียงอย่างไร
การแบ่งปัญหาใหญ่เป็นปัญหาย่อย
การพยายามจัดหนังสือกองใหญ่ทั้งกองนั้นอาจเกิดความยุ่งยาก
การแบ่งปัญหาใหญ่เป็นปัญหาย่อยช่วยทำให้การออกแบบขั้นตอนการแก้ปัญหาทำได้เป็นระบบมากขึ้น
โดยอาจจะแบ่งเป็นปัญหาย่อยได้ดังต่อไปนี้
หนังสือเล่มใดควรจัดไว้เป็นลำดับแรก
ในกองหนังสือที่เหลือ
หนังสือเล่มใดควรเลือกออกมาเป็นหนังสือที่วางอยู่ในลำดับที่สอง
ในกองหนังสือที่เหลือ
หนังสือเล่มใดควรเลือกออกมาเป็นหนังสือที่วางอยู่ในลำดับที่สาม
จะเห็นได้ว่าปัญหาในการจัดหนังสือทั้งกองสามารถแบ่งเป็นปัญหาย่อยได้โดยคัดเลือกหนังสือเล่มที่สูงที่สุดออกจากกองใหญ่
(สมมติว่ากองใหญ่มี n เล่ม)
ทำให้ขนาดของกองหนังสือลดลงเหลือ n-1 เล่ม
ปัญหาย่อยในที่นี้คือการจัดเรียงหนังสือในกองที่มี ก-1 เล่ม ซึ่งเป็นปัญหาในรูปแบบเดิมที่มีความซับซ้อนน้อยลง
การแตกปัญหาในตัวอย่าง
“สอนน้องจัดหนังสือ” ได้ผลลัพธ์เป็นปัญหาย่อยดังนี้
ปัญหาย่อยที่
1 หนังสือเล่มใดควรจัดไว้เป็นลำดับแรก
ปัญหาย่อยที่ 2 ในกองหนังสือที่เหลือ
หนังสือเล่มใดควรเลือกออกมาเป็นหนังสือที่วางอยู่ในลำดับที่สอง
ปัญหาย่อยที่ 3 ในกองหนังสือที่เหลือ
หนังสือเล่มใดควรเลือกออกมาเป็นหนังสือที่วางอยู่ในลำดับที่สาม
การพิจารณารูปแบบในการสอนน้องจัดหนังสือ
จากการแตกปัญหาในตัวอย่าง
“สอนน้องจัดหนังสือ” นักเรียนอาจจะอธิบายคำตอบของปัญหาย่อยได้ดังนี้
ปัญหาย่อยที่ 1 หนังสือเล่มใดควรจัดไว้เป็นลำดับแรก
คำตอบ หนังสือเล่มที่มีความสูงมากที่สุด
ปัญหาย่อยที่
2 ในกองหนังสือที่เหลือ
หนังสือเล่มใดควรเลือกออกมาเป็นหนังสือที่วางอยู่ในลำดับที่สอง
คำตอบ หนังสือเล่มที่มีความสูงมากที่สุดในกองที่เหลือ
ปัญหาย่อยที่
3 ในกองหนังสือที่เหลือ
หนังสือเล่มใดควรเลือกออกมาเป็นหนังสือที่วางอยู่ในลำดับที่สาม
คำตอบ หนังสือเล่มที่มีความสูงมากที่สุดในกองที่เหลือ
ปัญหาย่อยสุดท้ายที่มีขนาด
1
เห็นได้ว่าแต่ละปัญหาย่อยนั้นต่างก็มีรูปแบบเดียวกัน
และมุ่งหาคำตอบในลักษณะเดียวกันคือ
ปัญหาย่อย ในกองหนังสือที่เหลือ
หนังสือเล่มใดควรเลือกออกมาเป็นหนังสือที่วางอยู่ในลำดับถัดไป
คำตอบ หนังสือเล่มที่มีความสูงมากที่สุดในกองหนังสือที่เหลืออยู่
การคิดเชิงนามธรรมในปัญหาสอนน้องจัดหนังสือ
เนื่องจากขั้นตอนที่นำไปปฏิบัติตามต้องการเพียงการจัดเรียงหนังสือตามลำดับจากสูงไปต่ำ
รายละเอียดที่จำเป็นเพื่อใช้ในการตัดสินใจเลือกหนังสือจึงมีเพียงความสูงของหนังสือแต่ละเล่ม
ในขณะที่สีและความหนาของหนังสือนั้นถือเป็นรายละเอียดที่ไม่จำเป็น
จึงสามารถตัดออกไปได้ในการออกแบบกระบวนการแก้ปัญหา
ถ้านักเรียนต้องการใช้เพียงความสูงของหนังสือแต่ละเล่มเพื่อใช้พิจารณาในกาจัดเรียง
นักเรียนสามารถใช้ตัวเลขหนึ่งจำนวนแทนความสูงของหนังสือแต่ละเล่ม
เพื่อใช้ในการออกแบบอัลกอริทึม โดยจากปัญหาย่อยที่เคยตั้งเอาไว้ก่อนหน้านี้ว่า
ในกองหนังสือที่มีอยู่
หนังสือเล่มใดควรค้ออกมาเป็นหนังสือที่วางไว้ในลำดับถัดไป
มีกระบวนการแก้ปัญหาแบบเดียวกันกับปัญหาที่ระบุว่า
ในชุดจำนวนที่พิจารณาอยู่ จำนวนใดมีค่ามากที่สุด
อัลกอริทีมสำหรับสอนน้องจัดหนังสือ
กระบวนการที่ผ่านมาสามารถนำมาออกแบบเป็นอัลอริทีมสำหรับให้น้องปฏิบัติตามได้ดังนี้
ขั้นตอนหลัก
1. ทำขั้นตอนต่อไปนี้ซ้ำจนกระทั่งไม่มีหนังสือเหลืออยู่ในกอง
1.1 เลือกหนังสือที่มีความสูงมากที่สุดในกอง
1.2 นำหนังสือที่เลือกจากขั้นดอน 11 จัดเรียงไว้บนโต๊ะ โดยวางไว้ถัดจากแถวหนังสือที่จัดไว้แล้วก่อนหน้านี้
ถ้ายังไม่มีหนังสือในแถวให้วางหนังสือเล่มนี้ไว้เป็นเล่มแรก
อัลกอริทึมสำหรับการจัดเรียงลำดับ (sorting
algorithm)
อัลกอริทึมสำหรับสอนน้องจัดหนังสือเป็นอัลกอริทึมสำหรับการเรียงลำดับมีชื่อว่า
"การเรียงลำดับแบบเลือก (selection sort)" ซึ่งมีวิธีการที่เข้าใจง่ายแต่ค่อนข้างช้า
เมื่อมีสิ่งที่ต้องเรียงลำดับเป็นจำนวนมาก
นอกเหนือจากการเรียงลำดับแบบเลือกยังมีอัลกอริทึมสำหรับการเรียงลำดับอีกหลายวิธีดูตัวอย่างและการทำงานของอัลกอริทีมเหล่านี้ได้จากลิงค์ https://www.toptal.com/developers/sorting-algorithms
ไม่มีความคิดเห็น:
แสดงความคิดเห็น