Please enable JavaScript.
Coggle requires JavaScript to display documents.
บทที่ 2 แก้ปัญหาและขั้นตอนวิธี - Coggle Diagram
บทที่ 2 แก้ปัญหาและขั้นตอนวิธี
การแก้ปัญหาด้วยคอมพิวเตอร์
วิเคราะห์และกำหนดรายละเอียดของปัญหา
เป็นการทำความเข้าใจเกี่ยวกับรายละเอียดเงื่อนไขข้อกำหนด รวมถึงข้อจำกัดต่าง ๆ ของปัญหา
ข้อมูลที่จำเป็นในการแก้ปัญหา ตรวจสอบว่ามีข้อมูลเพียงพอหรือไม่
จะหาข้อมูลเพิ่มเติมให้ครบถ้วนต่อการใช้แก้ปัญหาได้อย่างไร ข้อมูลผลลัพธ์ที่ได้คืออะไร
และจะตรวจสอบความถูกต้องของผลลัพธ์ที่ได้อย่างไร
การวางแผนการแก้ปัญหา เครื่องมือที่ใช้ในการวางแผนการแก้ปัญหา สำหรับการพัฒนาโปรแกรม
อาจเลือกใช้รหัสลำลอง หรือผังงาน โดยวิธีการแก้ปัญหาที่ได้เรียกว่า ขั้นตอนวิธีหรืออัลกอริทึม (algorithm)
ซึ่งเป็นลำดับขึ้นตอนในการแก้ปัญหาหรือการทำงานที่ชัดเจน
การดำเนินการปัญหา เป็นกระบวนการที่ได้วางแผนไว้มาปฏิบัติ
หรือพัฒนาโปรแกรมเพื่อแก้ปัญหา โดยอาจใช้ภาษาโปรแกรมช่วยในการดำเนินการ
การตรวจสอบและประเมินผล ขั้นตอนนี้จะทำควบคู่ไปกับขั้นตอนการดำเนินการแก้ปัญหา
โดยการตรวจสอบผลลัพธ์ที่ได้ไม่ถูกต้อง หรือยังมีส่วนที่ต้องแก้ไขปรับปรุงอยู่
ต้องย้อนกลับไปทำซ้ำตั้งแต่ขั้นตอนแรกจนกว่าจะได้ผลลัพธ์ที่ถูกต้อง
การจัดเรียงลำดับข้อมูล (Sorting)
เป็นกระบวนการเพื่อจัดการข้อมูลให้จัดเรียงตามลำดับซึ่งเป็นเทคนิคในการค้นหาข้อมูลให้มีประสิทธ์ภาพมาก
ขึ้น โดยสามารถแบ่งเป็น 2 ประเภทๆ หลักคือ
การเรียงลำดับภายใน (Internal Sorting) เป็นการเรียงลำดับข้อมูลภายในหน่วยความจำหลัก (Primary
Memory) ซึ่งจะเหมาะสมกับข้อมูลทีมีปริมาณไม่มาก เนื่องจากหน่วยความจำหลักมีขนาดจำกัด
ซึ่งมีวิธีการเรียงลำดับข้อมูล โดยสมารถแบ่งประเภทย่อยได้ดังนี้
1.1 วิธีเรียงลำดับแบบแทรก (Insertion )
วิธีเรียงลำดับข้อมูลแบบ Insertion Sort
วิธีเรียงลำดับข้อมูลแบบ Shell Sort
1.2 วิธีเรียงลำดับแบบเลือก (Selection)
วิธีเรียงลำดับข้อมูลแบบ Selection Sort
วิธีเรียงลำดับข้อมูลแบบ Heap Sort
1.3 วิธีเรียงลำดับแบบแลกเปลี่ยน (Exchange)
วิธีเรียงลำดับข้อมูลแบบ Bubble Sort
วิธีเรียงลำดับข้อมูลแบบ Quick Sort
การค้นหาข้อมูล
ตัวชี้วัด
ประยุกต์ใช้แนวคิดเชิงคำนวณในการพัฒนาโครงงานที่มีการบูรณาการกับวิชาอื่นอย่างสร้างสรรค์และเ
ชื่อมโยงกับชีวิตจริงสาระการเรียนรู้ ขั้นตอนในการค้นหาข้อมูล เช่น
การค้นหาแบบลำดับและการค้นหาแบบทวิภาค
การค้นหาข้อมูลที่มีประสิทธิภาพนั้น ขึ้นอยู่กับหลักการค้นหา รวมถึงขั้นตอนของการค้นหานั้น
การค้นหาข้อมูลพื้นฐานมีหลากหลายวิธี เช่น การค้นหาข้อมูลแบบลำดับ การค้นหาข้อมูลแบบทวิภาค
และการค้นหาข้อมูลแบบแฮชชิง
การใช้เทคนิคการค้นหาข้อมูลแบบใดต้องดูลักษณะของงาน
ซึ่งจะช่วยให้เราสามารถตัดสินใจเลือกเทคนิคการค้นหาข้อมูลที่เหมาะสมได้
การค้นหาข้อมูลแบบลำดับ(Sequential Search)
การค้นหาข้อมูลแบบลำดับ(Sequential Search) การหาข้อมูลแบบเป็นลำดับขั้นตอน
โดยจะค้นหาตั้งแต่ตัวแรกเรียงลำดับไปทีละตัวจนกว่าจะพบข้อมูลที่ต้องการ
หรือเปรียบเทียบไปจนถึงตัวสุดท้าย การค้นหาวิธีนี้เป็นวิธีที่ง่ายที่สุด
อัลกอริทึ่มในการค้นหาไม่ซับซ้อนสามารถใช้กับข้อมูลที่เรียงลำดับแล้วหรือข้อมูลที่ยังไม่ได้เรียงลำดับก็ได้
โดยผลลัพธ์จากการค้นหาข้อมูลจะมีความเป็นไปได้อยู่ 2 แบบ คือ
พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์(Successful Search)
ไม่พบตำแหน่งข้อมูลที่ต้องการภายในลิสต์ (Unsuccessful Search)
การค้นหาข้อมูลแบบทวิภาค (Binary Serach)
การค้นหาข้อมูลแบบทวิภาค เหมาะสำหรับค้นหาข้อมูลที่มีการเรียงลำดับอยู่แล้ว
โดยการค้นหาแต่ละรอบจะลดขอบเขตการค้นหาลงทีละครึ่ง
การค้นหาข้อมูลแบบทวิภาคมีประสิทธิภาพดีมากและเป็นแนวคิด หลักในการพัฒนาระบบฐานข้อมูล
หลังพิจารณาข้อมูลแต่ละครั้ง ขอบเขตของดัชนีที่เป็นไปได้จะลดลงประมาณครึ่งหนึ่ง
ถ้าข้อมูลในรายการมีจำนวน n ตัว
จำนวนรอบที่ต้องทํางานจะเท่ากับจํานวนครั้งในการลดค่าขอบเขตที่เป็นไปได้จาก n
ทีละครึ่งจนเหลือค่าเท่ากับ 1 ซึ่งค่าดังกล่าวสอดคล้อง กับฟังก์ชันลอการิทึม (logarithm) ฐาน 2 ของ n
ดังนั้นความซับซ้อนของ ขั้นตอนวิธีการค้นหาแบบทวิภาคจะแปรผันตรงกับ log2 n นั่นคือเรา
สามารถเขียนว่าการค้นหาแบบทวิภาคมีความซับซ้อนเป็น O(log2 n)
เทคนิคการค้นหาข้อมูลด้วยวิธีนี้
กำหนดข้อมูลที่ต้องการค้นหาและทำการเรียงข้อมูลตามความต้องการ เรียงจากมากไปน้อย
หรือจากน้อยไปมากก็ได้
ทำการแบ่งข้อมูลออกเป็น 2 ส่วน แล้วทำการหาค่ากลาง
เมื่อทราบแล้วว่าค่าของคีย์ฟิลด์อยู่ครึ่งแรกหรือครึ่งหลังแล้ว
ก็จะนำข้อมูลในครึ่งดังกล่าวทำการหาค่ากลางอีก ทำแบบนี้ไปเรื่อย ๆ จนกระทั้งได้ข้อมูลที่ต้องการ
หรือจนกระทั่งไม่สามารถแบ่งข้อมูลได้อีก
การทำซ้ำ
ในการทำงานบางครั้งย่อมมีการทำงานรูปแบบเดียวกันซ้ำๆ หลายรอบ ซึ่งลักษณะการทำซ้ำ เช่น
การทำซ้ำในรายการ การทำซ้ำด้วยเงื่อนไข
ออกแบบขั้นตอนวิธีที่มีเงื่อนไขและการทำซ้ำ โดยใช้ blockly
ให้ออกแบบขั้นตอนวิธีเพื่อแก้ปัญหาต่อไปนี้ โดยใช้เครื่องมือในเว็บไซต์
http://blockly.programming.in.th/
Count: นับจำนวนข้อมูลที่มีค่าไม่เกิน M บาท
https://blockly.programming.in.th/count/
Closest: หาข้อมูลที่มีค่าใกล้เคียงที่สุด
https://blockly.programming.in.th/closest/
Rank: หาอันดับจากการร้องเพลง
https://blockly.programming.in.th/rank/
Guess: เกมทายเลข
https://blockly.programming.in.th/guess/