บทที่ 2 การแก้ปัญหาและขั้นตอนวิธี

เนื้อหา การแก้ปัญหาและขั้นตอนวิธี

การแก้ปัญหาด้วยคอมพิวเตอร์

การระบุข้อมูลเข้า ข้อมูลออกและเงื่อนไขของปัญหา

การออกแบบขั้นวิธี

การทำซ้ำ

การจัดเรียงและค้นหาข้อมูล

การแก้ปัญหาด้วยคอมพิวเตอร์

ปัญหาที่สามารถแก้ได้ด้วยคอมพิวเตอร์ ไม่จำเป็นต้องเป็นปัญหาทางคณิตศาสตร์เสมอไป

ซึ่งก่อนจะแก้ปัญหาต้องเข้าใจปัญหาและความต้องการให้ชัดเจนแล้วค่อยพัฒนาขั้นตอนวิธีที่สามารถใช้งานได้

ขั้นตอนการแก้ปัญหาด้วยคอมพิวเตอร์ มี 7 ขั้นตอน

  1. นิยามปัญหา (Problem Definition)
  1. การบำรุงรักษา (Maintenance)
  1. การออกแบบอัลกอริทึม (Algorithm Design)
  1. การพัฒนาโปรแกรม (Program Development)
  1. การทดสอบความถูกต้อง (Program Testing)

สิ่งสำคัญที่สุด คือเราต้องทำความเข้าใจให้ได้ว่าปัญหาคืออะไร

ประเด็นหลักอยู่ที่ใด และต้องการให้ได้ผลลัพธ์อะไร

  1. การวิเคราะห์ปัญหา (Problem Analysis)

มีข้อมูลนำเข้า (input) อะไรบ้างที่จะทำให้ได้ผลลัพธ์

การหาผลลัพธ์ของปัญหา (output) ว่าคืออะไร

การออกแบบอัลกอริทึม เป็นการคิดหาขั้นตอนการแก้ปัญหาทีละขั้น เราต้องคิดว่าจะทำอย่างไรจึงจะแก้ปัญหาได้ และสามารถนำมาแปลงเป็นคำสั่งของภาษาโปรแกรมได้โดยง่าย

การพัฒนาโปรแกรมจะทำได้ง่าย ถ้าอัลกอริธึมถูกต้อง และมีความชัดเจน

การทดสอบ (Testing) เพื่อหาข้อผิดพลาดจากการเขียนคำสั่งผิด
ไวยกรณ์ของภาษา หรือข้อผิดพลาดจากการคำนวณ

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

การออกแบบ
ขั้นตอนวิธี

  1. การจัดทำเอกสาร (Documentation)

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

ข้อมูลที่เกี่ยวข้องกับการทำงานของคอมพิวเตอร์

ข้อมูลเข้า ( input) เป็นข้อมูลที่ใช้เพื่อประมวลผล

ข้อมูลออก ( Output) เป็นข้อมูลที่แสดงผลลัพธ์

การระบุข้อมูลเข้า และข้อมูลออกอาจจะไม่สามารถทำได้อย่างชัดเจน จึงต้องทำความเข้าใจกับปัญหามากขึ้น

การออกแบบขั้นตอนวิธี คือ ขั้นตอนการแก้ปัญหาอย่างเป็นลำดับ โดยประกอบด้วยชุดคำสั่งการทำงานอย่างเป็นลำดับและชัดเจน เครื่องมือในการออกแบบขั้นตอนวิธี ประกอบด้วย

บรรยาย (Narrative Description) การออกแบบขั้นตอนวิธีด้วยการบรรยาย เป็นการเขียนบรรยายวิธีการแก้ปัญหาอย่างเป็นลำดับโดยใช้ภาษาธรรมชาติเช่น วิธีการต้มบะหมี่กึ่งสำเร็จรูป

ลักษณะขั้นตอนวิธี

ใช้เวลาในการปฏิบัติการน้อย

ชัดเจนและกระทัดรัด

ให้คำตอบที่ถูกต้อง

แก้ปัญหาได้อย่างมีประสิทธิภาพ

รหัสเทียม (Pseudo Code) เป็นการเขียนโปรแกรมในรูปแบบภาษาอังกฤษที่มีขั้นตอนและรูปแบบแน่นอนกะทัดรัด

การอ่านข้อมูล สามารถใช้คำสั่ง READ, INPUT หรือ GET ได้

ประโยชน์ของรหัสเทียม (Pseudo Code)

เป็นเครื่องมือในการกำหนดโครงร่างกระบวนการทำงานของการเขียนโปรแกรมและใช้เป็นต้นแบบในการทบทวน ปรับปรุงแก้ไขและพัฒนาโปรแกรมของโปรแกรมเมอร์และนักวิเคราะห์ระบบ

หลักการเขียนรหัสเทียม(Pseudo Code)

ใช้ภาษาอังกฤษที่เข้าใจง่าย

ในหนึ่งบรรทัด มีเพียงหนึ่งประโยคคำสั่งเท่านั้น

ใช้ย่อหน้าแบ่งการแสดงการทำงานเพื่อให้อ่านง่าย

แต่ละประโยคคำสั่งให้เขียนจากบนลงล่าง และมีทางออกทางเดียว

กลุ่มของประโยคคำสั่งอาจรวมเป็นหมวดหมู่แล้วเรียกใช้เป็นโมดูล

การแสดงผลข้อมูล สามารถใช้คำสั่ง DISPLAY, PRINT, PROMPT หรือ WRITE ได้

การกำหนดเงื่อนไขหรือการตัดสินใจ (Dicision) ใช้คำสั่ง if...then

การทำงานแบบวนซ้ำ ด้วย REPEAT ... UNTIL
การทำงานแบบวนซ้ำด้วย WHILE ... ENDWHILE

การทำงานแบบวนซ้ำด้วย FOR ... ENDFOR

ผังงาน (FlowChart) เป็นการใช้สัญลักษณ์ เพื่ออธิบายขั้นตอนการทำงานของโปรแกรม

รูปแบบผังงาน (FlowChart)

แบบลำดับ ( Sequential )

แบบมีเงื่อนไข ( Condition )

แบบวนลูป ( Loop )

การทำซ้ำ
คืออะไร

การทำงานลักษณะเดียวกันหลายรอบ

ลดจำนวนการเขียนขั้นตอนวิธี

อธิบายขั้นตอนวิธีที่ซับซ้อนให้เข้าใจง่าย

โปรแกรมมีขนาดเล็ก

รูปแบบการทำซ้ำ

การทำซ้ำแบบจำนวนรอบไม่แน่นอน

การทำซ้ำแบบไม่รู้จบ

การทำซ้ำแบบจำนวน
รอบแน่นอน

ผังงานการทำซ้ำ

เป็นรูปแบบที่มีการกระทำกระบวนการหนึ่งหลายๆครั้งโดยมีเงื่อนไขในการควบคุม

การทำงานแบบตามลำดับ (Sequence)

การทำงานแบบมีเงื่อนไข (Condition)

การจัดเรียงและ
ค้นหาข้อมูล

ขั้นตอนวิธีในการจัดเรียงข้อมูล การค้นหาข้อมูล

การจัดเรียงข้อมูลเป็นสิ่งที่พบอยู่เสมอ เมื่อต้องการประมวลผลข้อมูลจำนวนมาก การเรียงลำดับข้อมูลด้วยเงื่อนไขที่เหมาะสม จะทำให้การค้นหาข้อมูลทำได้อย่างมีประสิทธิภาพ เช่น การทำข้อมูลนักศึกษามาจัดเลียงลำดับรหัสนักศึกษา เพื่อนำไปใช้ในการพิมพ์ใบเซ็นชื่อเข้าสอบหรือการเรียงข้อมูลพนักงานตามรหัสพนักงานเพื่อใช้การพิมพ์สลิปเงินเดือน

การเลือกข้อมูลที่น้อยที่สุดมาไว้เป็นลำดับแรก จากนั้นในรายการข้อมูลที่เหลืออยู่จะเลือกข้อมูลที่มีค่าน้อยที่สุดมาเป็นข้อมูลในรายการคำตอบ ลำดับที่ 2 ทำไปเรื่อยๆ จนครบทุกจำนวน

การจัดเรียงข้อมูล

แบบแทรก ( Insertion Sort)

เป็นการนำข้อมูลที่ยังไม่ถูกพิจารณามาแทรกในตำแหน่งที่ถูกต้องโดยค่าของข้อมูลที่กำลังพิจารณาต้องมีค่ามากกว่าหรือเท่ากับ ค่าของข้อมูลตัวหน้า หรือ น้อยกว่าหรือเท่ากับ ค่าของข้อมูลตัวหลัง ในรายการที่เรียงลำดับไว้แล้ว

การค้นหาข้อมูล

เป็นกระบวนการหาตำแหน่งของข้อมูลตามค่าของคีย์ โดยมีอัลกอริทึมการค้นหา เป็นเทคนิคการค้นหาข้อมูลตามค่าของคีย์ที่เป็นค่าที่รับเข้ามาเพื่อค้นหาการค้นหาจะสิ้นสุดลงเมื่อพบข้อมูลที่มีค่าคีย์ตรงกันหรือไม่พบข้อมูล

การค้นหาแบบตามลำดับ (Sequence Search)

การหาข้อมูลแบบเป็นลำดับขั้นตอน โดยจะค้นหาตั้งแต่ตัวแรกเรียงลำดับไปทีละตัวจนกว่าจะพบข้อมูลที่ต้องการ หรือเปรียบเทียบไปจนถึงตัวสุดท้าย

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