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

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

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

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

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

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

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

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

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

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

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

ขั้นตอนที่ 1  สร้างรายการคำตอบที่เป็นไปได้  โดยเลือกเฉพาะรายการอาหารหลัก

1.1 พิจารณารายการอาหารทีละรายการ

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

สำหรับขั้นตอนที่ 2 จะดำเนินการต่อจากรายการคำตอบของขั้นตอนที่ 1

ขั้นตอนที่ 2  คำนวณคะแนนสำหรับเลือกอาหารในรายการ

2.1 พิจารณารายการอาหารหลักจากขั้นตอนที่ 1 ทีละรายการจนครบ

    2.1.1 ขณะที่พิจารณาอาหารลำดับที่ i  (i แทนลำดับที่ของอาหารที่กำลังพิจารณา)

    2.1.2 ให้ Q แทนคะแนนคุณภาพของอาหารลำดับที่ i

    2.1.3 ให้  R  แทนคะแนนความนิยมของอาหารลำดับที่ i 

    2.1.4 คำนวณคะแนน S  เท่ากับ  (0.6 x Q) + (0.4 x R)

    2.1.5 ให้คะแนนสำหรับจัดอันดับของอาหารลำดับที่ i  เท่ากับ  S

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

สังเกตว่า ในการระบุขั้นตอนวิธีข้างต้น มีการระบุให้คอมพิวเตอร์ทำงานซ้ำ ๆ กัน โดยสั่งให้คอมพิวเตอร์พิจารณาอาหารทั้งหมดที่มี  รวมทั้งมีการระบุให้คอมพิวเตอร์ทำงานตามเงื่อนไข เช่น ในขั้นตอนที่ 1.1.1 มีการตรวจสอบประเภทอาหาร      

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

2.1.4  ตัวแปร

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

ในการเขียนขั้นตอนวิธีอาจระบุว่า ให้กำหนดค่าให้กับตัวแปร หรืออาจใช้สัญลักษณ์ <---  ในการเขียน เช่น 

x <--- 10  จะเป็นการระบุให้ตัวแปร x  มีค่าเท่ากับ  10

z <--- z + 1   จะเป็นการกำหนดให้เพิ่มค่าตัวแปร z ขึ้นอีก 1 กล่าวคือ ถ้าก่อนการทำงานตัวแปร z มีค่าเท่ากับ 10  หลังการทำงาน ตัวแปร z มีค่าเท่ากับ  11

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

ตัวอย่างที่ 2.1  ปัญหาการหา ห.ร.ม.

พิจารณาตัวอย่างปัญหาการหา ห.ร.ม. จากหัวข้อในบทที่ 1 นักเรียนสามารถระบุข้อมูลเข้า ข้อมูลออก รวมทั้งเงื่อนไขได้ดังนี้

>> ข้อมูลเข้า   :  จำนวนเต็มบวกสองจำนวน คือ A  และ B

>> ข้อมูลออก  :  จำนวนเต็มบวกหนึ่งจำนวน คือ C  ที่มีคุณสมบัติดังนี้

1. C เป็นจำนวนเต็ม บวก

2. C หาร  A  และ   B  ลงตัว

3. C มีค่ามากที่สุดเท่าที่เป็นไปได้

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

ตัวอย่างที่ 2.3 การแบ่งกลุ่มทำงาน

นักเรียนต้องจัดกิจกรรมวันภาษาไทย  จากการประชุมมีงานที่ต้องทำ ดังนี้  

1>  จัดบอร์ดหน้าห้องเกี่ยวกับภาษาไทย

2> จัดเตรียมงานโต้วาที

3> เป็นกลุ่มผู้โต้วาที โดยมีสองกลุ่ม กลุ่มละ 3 คน

4> อ่านกลอนทำนองเสนาะ

5> ร้องเพลงไทยสมัยใหม่

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

 >> ข้อมูลเข้า   :  รายการของงานทั้งหมด ข้อมูลของนักเรียนแต่ละคนที่ระบุว่าสามารถทำงานใดได้บ้าง และต้องการทำงานใดเป็นพิเศษ

>> ข้อมูลออก  :  ข้อมูลที่ระบุว่านักเรียนคนใดทำงานอะไร โดยมีเงื่อนไขดังนี้

-->  นักเรียนควรได้ทำงานที่ตนเองเลือกว่าสามารถทำงานนั้นได้

-->  ถ้าเป็นไปได้ นักเรียนควรได้ทำงานที่ตนเองเลือกว่าอยากทำเป็นพิเศษ

-->  นักเรียนแต่ละคนควรมีงานที่ต้องทำอย่างน้อย 1 อย่าง แต่ไม่ควรเกิน 2 อย่าง

-->  นักเรียนที่อยู่ในกลุ่มผู้โต้วาที  ไม่ควรเป็นผู้จัดเตรียมงานโต้วาที

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

ตัวอย่างที่ 2.5 การตัดสินใจรดน้ำต้นไม้ของระบบรดน้ำต้นไม้อัตโนมัติ

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

ในส่วนการทำงานหลักของขั้นตอนวิธี คือ การตัดสินใจรถน้ำต้นไม้ มีการทำงานตามลำดับ ดังนี้

1. อ่านค่าความชื้นของดิน

2. ให้ H แทนค่าควาชื้นดังกล่าว

3.  ถ้า  H < 0.1 แล้ว

3.1 ส่งสัญญาณเปิดน้ำ

ถ้าเงื่อนไขไม่เป็นจริง

3.2 ส่งสัญญาณปิดน้ำ

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

>> ขั้นตอนวิธี :   ควบคุมการเปิดปิดน้ำของเครื่องรถน้ำต้นไม้

>> ข้อมูลเข้า  :  ค่าความชื้นของดิน

>> ข้อมูลออก :  สัญญาณเปิดปิดน้ำ

1. ทำซ้ำทุก ๆ 1 นาที

    1.1 อ่านค่าความชื้นของดิน

    1.2 ให้ H แทนค่าควาชื้นดังกล่าว

    1.3  ถ้า  H < 0.1 แล้ว

1.3.1 ส่งสัญญาณเปิดน้ำ

ถ้าเงื่อนไขไม่เป็นจริง

1.3.2 ส่งสัญญาณปิดน้ำ

ขั้นตอนวิธีดังกล่าวเขียนเป็นผังงานได้ ดังรูป

ตัวอย่างที่ 2.6 การคำนวณคะแนนสอบ

      พิจารณาสถานการณ์จากตัวอย่างที่ 2.2 ต้องการคำนวณคะแนนสูงสุด คะแนนต่ำสด และคะแนนเฉลี่ยของนักเรียนในห้อง  โดยมีข้อมูลเข้าหรือข้อมูลออก ดังนี้

  >> ข้อมูลเข้า   :  รายการคะแนนสอบของนักเรียน 40 คน

 >> ข้อมูลออก  :  คะแนนสูงสุด  คะแนนต่ำสุด  คะแนนเฉลี่ย

        ปัญหานี้ สามารถแบ่งได้เป็นสามส่วน คือ การหาคะแนนสูงสุด  การหาคะแนนต่ำสุด  และการคำนวณหาคะแนนเฉลี่ย จะเริ่มพิจารณาจากปัญหาการหาคะแนนสูงที่สุดก่อน  ในการออกแบบนั้นจะเริ่มต้นสังเกตวิธีการที่นักเรียนใช้ในการหาค่าสูงสุดของข้อมูล พิจารณาตัวอย่างจำนวนเต็ม สิบจำนวน ดังนี้  40  51  36  15  42  47  9  28  57  16

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

>> ขั้นตอนวิธี :   หาค่าที่สูงที่สุดของข้อมูลในรายการ

>> ข้อมูลเข้า  :  รายการข้อมูล

>> ข้อมูลออก :  ค่าสูงสุดของข้อมูล

1.  พิจารณาข้อมูลตัวแรกให้ Max มีค่าเป็นข้อมูลดังกล่าว

2.  พิจารณาข้อมูลตัวถัดไปทีละจำนวน

    2.1   เรียกข้อมูลที่กำลังพิจารณาว่า  x

    2.2  ถ้า  x > Max  แล้ว

    ให้ Max  <--- x

3. ตอบว่าค่าที่สูงที่สุด คือ Max

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

>> ขั้นตอนวิธี :   หาผลรวมของข้อมูลในรายการ

>> ข้อมูลเข้า  :  รายการข้อมูล

>> ข้อมูลออก :  ผลรวมของข้อมูล

1. ให้ Total มีค่าเป็น 0

2.  พิจารณาข้อมูล ทีละจำนวนจนครบทุกจำนวน

     2.1  เรียกตัวที่กำลังพิจารณาว่า  x

     2.2  ให้  Total  <--- Total + x

3.  ตอบว่า ผลรวมคือ Total

เมื่อคำนวณหาผลรวมได้แล้ว ค่าเฉลี่ยจะมีค่าเท่ากับ  Total / 40

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

>> ขั้นตอนวิธี :   หาค่าเฉลี่ยของข้อมูลในรายการ

>> ข้อมูลเข้า  :  รายการข้อมูล

>> ข้อมูลออก :  ค่าเฉลี่ยของข้อมูล

1. ให้ Total มีค่าเป็น 0

2.  ให้  Count มีค่าเป็น 0

3.  พิจารณาข้อมูล ทีละจำนวน

     3.1  เรียกตัวที่กำลังพิจารณาว่า  x

     3.2  ให้  Total  <--- Total + x

3.3  ให้  Count  <--- Count + 1

4.  ตอบว่า ค่าเฉลี่ย คือ Total / Count

ขั้นตอนในข้อ 3.2 และ 3.3 มีการกำหนดให้  Total  มีค่าเป็น  Total + 1  เพื่อเพิ่มค่าให้กับตัวแปร Total และมีการกำหนดให้ Count มีค่าเป็น Count + 1  เพื่อเพิ่มค่าให้กับตัวแปร Count  การเขียนลักษณะนี้จะพบเห็นได้บ่อยครั้งในการเขียนโปรแกรม  ซึ่งแตกต่างจากการเขียนสมการทางคณิตศาสตร์

ตัวอย่างที่ 2.7  ตรวจสอบพิกัด

      แผนที่ฉบับหนึ่่งมีอัตราส่วน 1 เซนติเมตร ต่อ 1 กิโลเมตร และมีการตีตารางพิกัดทุก ๆ  หนึ่งเซนติเมตร ถ้าพิกัดของโรงเรียนอยู่ที่ตำแหน่ง (2,3) พิกัดของร้านอาหารอยู่ที่ตำแหน่ง (x,y) ในแผนที่ ถ้าต้องการตรวจสอบว่าร้านอาหารมีระยะห่างจากโรงเรียนไม่เกิน 1 กิโลเมตรหรือไม่  จะระบุเงื่อนไขดังนี้

>> เงื่อนไข :  จุด (x,y)  ห่างจากจุด (2,3) ในแผนที่ไม่เกิน 1 เซนติเมตร

            ในการตรวจสอบเงื่อนไขดังกล่าว  อาจต้องใช้ไม้บรรทัดวัดระยะห่างในแผนที่ หรือใช้ทฤษฎีบทพีทาโกรัส คำนวณระยะห่างของพิกัดของร้านอาหาร (x,y) กับจุด (2,3) ได้เท่ากับ  คลิ๊กดูภาพ

        ดังนั้น สามารถเขียนเงื่อนไขดังกล่าวในอีกรูปแบบหนึ่งเป็น  

>> เงื่อนไข :   คลิ๊กดูภาพ

2.4 การทำซ้ำ

          การแก้ปัญหาอาจต้องมีการทำงานลักษณะเดียวกันซ้ำหลายรอบ ในหัวข้อนี้จะได้ศึกษารูปแบบการเขียนขั้นตอนวิธีการทำซ้ำแบบต่าง ๆ 

2.4.1 การทำซ้ำในรายการ

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

พิจารณาข้อมูลในรายการทีละตัว จนครบ

1. ให้ตัวแปร x แทนข้อมูลที่พิจารณาอยู่

2. ประมวลผลตัวแปร x

จากรูปแบบการทำซ้ำดังกล่าว  ถ้านักเรียนมีเงิน M บาท  และมีรายการสินค้า A รายการ สามารถเขียนขั้นตอนวิธีนับจำนวนสินค้าที่มีราคาไม่เกิน M บาท ได้ดังนี้

ขั้นตอนวิธี :  หาจำนวนสินค้าที่มีราคาไม่เกิน M  บาท

ข้อมูลเข้า :   ราคาสินค้าในรายการ A 

ข้อมูลออก :  จำนวนสินค้าที่มีราคมไม่เกิน  M บาท

  1. ให้ตัวแปร  count <--- 0

  2. พิจารณาข้อมูลราคาสินค้าในรายการ A ทีละจำนวน  จนครบ

2.1 ให้  x แทนข้อมูลราคาสินค้าที่พิจารณาอยู่

2.2 ถ้า x  น้อยกว่าหรือเท่ากับ  M แล้ว

ให้ count  <---  count + 1

  3. คืนค่าจำนวนสินค้าเท่ากับ  count

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

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

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

ปัญหาดังกล่าวเป็นตัวอย่างหนึ่งของการค้นหาข้อมูลในรายการ กล่าวคือ เรามีรายการ A และต้องการค้นหาข้อมูล target  ในรายการ  รูปแบบการเขียนการทำซ้ำที่สั้นและกระชับ  จะระบุลำดับของข้อมูล (ดัชนี) แสดงได้ดังนี้

ขั้นตอนวิธี :  หาข้อมูล  target  ในรายการ  A

ข้อมูลเข้า :   ข้อมูลทุกตัวในรายการ A 

ข้อมูลออก :  ดัชนีของ  target ในรายการ A

   1.  ให้  L  <--- จำนวนข้อมูลในรายการ  A

   2. ให้ดัชนี i  มีค่าตั้งแต่ 1, 2, 3, ... จนถึง L

   3. ให้พิจารณาข้อมูลในรายการ  A  ทีละตัว

3.1  ให้  y <--- ข้อมูลตัวที่  i  ในรายการ  A

3.2  ถ้า  y =  target  แล้ว

คืนค่า  i  และจบการทำงาน

   4. ตอบว่าไม่พบข้องมูล target  และจบการทำงาน

----------------------------------------------------------------------------------------------------------------

สมมติว่า รายการ A  มีข้อมูล ดังนี้   95 , 69, 71 , 85 , 60 , 50 , 51 , 12 , 51 , 3

ตัวอย่าง  การทำงานตามขั้นตอนวิธีหาข้อมูล  85 (target)  ในรายการ A  แสดงได้ดังนี้

ขั้นตอนวิธีจะทำงาน ดังนี้

  1. ตัวแปร L จะมีค่าเท่ากับ  10

  2. รอบแรก ดัชนี i = 1  จากนั้นพิจารณา y เป็นข้อมูลตัวที่ 1 ในรายการ นั่นคือ y = 95 ซึ่งไม่ตรงกับ target

  3. รอบที่ 2 ดัชนี i = 2  จากนั้นพิจารณา y เป็นข้อมูลตัวที่ 2 ในรายการ นั่นคือ y = 69  ซึ่งไม่ตรงกับ target

  4. รอบที่ 3 ดัชนี i = 3  จากนั้นพิจารณา y เป็นข้อมูลตัวที่ 3 ในรายการ นั่นคือ y = 71  ซึ่งไม่ตรงกับ target

  5. รอบที่ 4 ดัชนี i = 4  จากนั้นพิจารณา y เป็นข้อมูลตัวที่ 4 ในรายการ นั่นคือ y = 85  ซึ่งเท่ากับ target  

     ขั้นตอนวิธีจะคืนค่า  4 และจบการทำงาน

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

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

ขั้นตอนวิธี :  หารายการอาหารที่มีคะแนนสำหรับเลือกอาหารมากที่สุด

ข้อมูลเข้า :   ตารางรายการอาหารหลักที่มีการคำนวณคะแนนสำหรับเลือกอาหารแล้ว

ข้อมูลออก :  อาหารที่เหมาะสมที่สุด โดยพิจารณาจากอาหารที่มีคะแนนสูงที่สุดในตาราง

  1.   ให้  x  เท่ากับ  1

ให้ Smax  แทนคะแนนของอาหารลำดับที่ x

  2.  พิจารณารายการอาหารหลักจากตาราง  ทีละรายการจนครบ

2.1  ขณะที่พิจารณาอาหารลำดับที่ y

2.2  ให้  S  แทนคะแนนของอาหารลำดับที่ y

2.3  ถ้า  S  มากกว่า  Smax  แล้ว

2.3.1  ให้  x  มีค่าเท่ากับ  y

2.3.2  ให้  Smax  มีค่าเท่ากับ  s

   3.  ตอบว่า อาหารลำดับที่   x  เป็นอาหารที่เหมาะสมที่สุด

2.4.2 การทำซ้ำด้วยเงื่อนไข

  นอกจากการเขียนขั้นตอนวิธีทำงานกับรายการแล้ว  นักเรียนอาจต้องใช้การทำซ้ำในการคำนวณแบบอื่น ๆ เช่น ถ้าต้องการประมาณค่าของรากที่สองของ 10  ที่เป็นทศนิยม 3 ตำแหน่ง  เขียนขั้นตอนวิธี  ได้ดังนี้

ขั้นตอนวิธี :  ประมาณค่ารากที่สองของ  10  ที่เป็นทศนิยม 3 ตำแหน่ง

ข้อมูลเข้า :   -

ข้อมูลออก :  ค่าประมาณของรากที่สองของ 10 ที่เป็นทศนิยม 3 ตำแหน่ง

  1. ให้  s  <---  0

  2. ให้  a  <---  0   (เก็บค่าประมาณที่ดีที่สุด)

  3.  ทำซ้ำในขณะที่  s <= 10

3.1  ถ้า  | S^2 - 10 |  <  | a^2 - 10 | แล้ว

a <---  s

3.2  s  <--- s + 0.001

  4.  คืนค่า  a  และจบการทำงาน

จากขั้นตอนวิธีข้างต้นเป็นการทำซ้ำด้วยเงื่อนไข  s <= 10  ดังนั้นจะมีการทำซ้ำในข้อ 3.1 และ 3.2 จนกว่า  s  จะมีค่ามากกว่า  10

ตัวอย่างที่ 2.9 เกมทายเลข

ให้นักเรียนสุ่มจำนวนเต็มระหว่าง  1 - 100  มาเป็นคำตอบหนึ่งจำนวน  และให้ผู้เล่นทายจำนวนที่เป็นคำตอบ  จากนั้นให้นักเรียนบอกคำใบ้ว่าจำนวนที่ทายมากกว่าหรือน้อยกว่าคำตอบ หรือ ตอบว่าเป็นคำตอบที่ถูกต้อง  ซึ่งมีขั้นตอนวิธี  ดังนี้

ขั้นตอนวิธี :  เปรียบเทียบจำนวนที่ผู้เล่นทายกับคำตอบที่สุ่มไว้ 

ข้อมูลเข้า :   จำนวนที่ผู้เล่นทาย

ข้อมูลออก :  "ค่าน้อยเกินไป"  "ค่ามากเกินไป"  "ถูกต้อง"

1. ให้  secret  <---  สุ่มจำนวนเต็มที่มีค่าระหว่าง 1 ถึง 100

2. ทำซ้ำไปเรื่อย ๆ 

2.1 ให้  answer  <---  จำนวนเต็มที่ผู้เล่นทาย

2.2  ถ้า  answer  <  secret  แล้ว    ตอบผู้เล่นว่า  "ค่าน้อยเกินไป"

2.3  ถ้า  answer  >  secret  แล้ว    ตอบผู้เล่นว่า  "ค่ามากเกินไป"

2.4  ถ้า  answer  =  secret  แล้ว    

      2.4.1  ตอบผู้เล่นว่า  "ถูกต้อง"

2.4.2  จบการทำซ้ำ

จากตัวอย่าง รูปแบบของการเขียนการทำซ้ำโดยไม่ระบุเงื่อนไขในส่วนเริ่มต้นของการทำซ้ำและจะระบุเงื่อนไขการจบการทำซ้ำ  answer  =  secret

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

         ในหัวข้อนี้นักเรียนจะได้รู้จักกับขั้นตอนวิธีพื้นฐานในการจัดเรียงข้อมูล (sort) และการค้นหาข้อมูล (search) ซึ่งเป็นกิจกรรมที่สัมพันธ์กันที่ใช้ในการแก้ปัญหาที่พบบ่อยในชีวิตประจำวัน

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

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

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

1) การจัดเรียงแบบเลือก (selection sort) เป็นการเลือกข้อมูลที่มีค่าตามเงื่อนไขมาไว้เป็นลำดับแรก เช่น เงื่อนไข  การเรียงข้อมูลจากน้อยไปหามาก  นักเรียนจะเลือกข้อมูลที่มีค่าน้อยที่สุดมาไว้เป็นลำดับแรกในรายการคำตอบและขีดทับข้อมูลที่เลือกแล้วในรายการ จากนั้นในรายการข้อมูลที่เหลืออยู่ จะเลือกข้อมูลที่มีค่าน้อยที่สุดมาเป็นข้อมูลในรายการคำตอบเป็นลำดับที่สอง         จากนั้นเลือกข้อมูลที่มีค่าน้อยที่สุดมาเป็นข้อมูลในรายการคำตอบเป็นลำดับที่สาม ไปเรื่อย ๆ แสดงดังตัวอย่าง 2.10)

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

ตัวอย่างที่ 2.10 การจัดเรียงแบบเลือก

ให้นักเรียนเรียงคะแนนสอบวัดความรู้วิชาเทคโนโลยี(วิทยาการคำนวณ) โดยเรียงคะแนนจากน้อยไปหามาก  จากข้อมูลคะแนนต่อไปนี้  84,  58,  96,  60,  8,  9,  77,  62,  92,  13,  86,  44,  50,  9,  90,  42,  61,  58,  35

ครั้งที่ 1    เลือกคะแนนที่น้อยที่สุด คือ 8  ไปเก็บในรายการคำตอบ 

    รายการคำตอบ  >>  8

ครั้งที่ 2    เลือกคะแนนที่น้อยที่สุดที่ยังไม่ถูกเลือก คือ 9  ไปเก็บในรายการคำตอบ 

    รายการคำตอบ  >>  8 ,  9

ครั้งที่ 3    เลือกคะแนนที่น้อยที่สุดที่ยังไม่ถูกเลือก คือ 9  ไปเก็บในรายการคำตอบ 

    รายการคำตอบ  >>  8,  9,  9 

ครั้งที่ 4    เลือกคะแนนที่น้อยที่สุดที่ยังไม่ถูกเลือก คือ 13  ไปเก็บในรายการคำตอบ 

    รายการคำตอบ  >>  8,  9,  9,  13 

    ทำเช่นนี้ไปเรื่อย ๆ จนหมด  (ทำซ้ำ)

สุดท้าย   รายการคำตอบ  >>  8,  9,  9, 13,  35,  42,  44,  50,  58,  58,  60,  61,  62,  77,  84,  86,  90,  92,  96

จากตัวอย่าง สามารถเขียนเป็นขั้นตอนวิธี ได้ดังนี้

ขั้นตอนวิธี :  การเรียงลำดับข้อมูลแบบเลือก

ข้อมูลเข้า :   รายการข้อมูล  L  

ข้อมูลออก :  รายการคำตอบ  S ที่เรียงลำดับแล้ว

1. ให้ S  แทนรายการคำตอบโดยเมื่อเริ่มต้น  S  จะเป็นรายการว่าง

2. ให้  N  <---  จำนวนข้อมูลในรายการ  L

3. ทำซ้ำ  N  รอบ

3.1 เลือกข้อมูลที่น้อยที่สุดจากรายการ L ที่ยังไม่ถูกเลือก และแทนข้อมูลนั้นด้วย M

3.2 ขีดทับข้อมูล M  ในรายการ  L

3.3  เพิ่ม  M  ต่อท้ายรายการคำตอบ S

ตัวอย่างที่ 2.11 การจัดเรียงแบบแทรก

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

84,  58,  96,  60,  8,  9,  77,  62,  92,  13,  86,  44,  50,  9,  90,  42,  61,  58,  35

       รายการข้อมูลที่เหลือ    84,  58,  96,  60,  8,  9,  77,  62,  92,  13,  86,  44,  50,  9,  90,  42,  61,  58,  35 

    รายการคำตอบ  >>  -

ครั้งที่ 1    รายการคำตอบ  >>  84,     //นำคะแนนตัวหน้าไปแทรกในรายการคำตอบ ซึ่งเป็นรายการว่าง

    รายการข้อมูลที่เหลือ   58,  96,  60,  8,  9,  77,  62,  92,  13,  86,  44,  50,  9,  90,  42,  61,  58,  35 

ครั้งที่ 2    รายการคำตอบ  >>  58,  84,     //แทรกในรายการตามเงื่อนไข (ต้องมากกว่าหรือเท่ากับข้อมูลตัวหน้าและน้อยกว่าหรือเท่ากับข้อมูล                                              ตัวหลัง (ซึ่ง 58 > 0 และ < 84  จึงถูกแทรกข้างหน้าในรายการคำตอบ)

    รายการข้อมูลที่เหลือ   96,  60,  8,  9,  77,  62,  92,  13,  86,  44,  50,  9,  90,  42,  61,  58,  35 

ครั้งที่ 3    รายการคำตอบ  >>  58,  84,  96    //แทรกในรายการตามเงื่อนไข (ซึ่ง 96 > 58 และ > 84  จึงถูกแทรกข้างหลังในรายการคำตอบ)

    รายการข้อมูลที่เหลือ   60,  8,  9,  77,  62,  92,  13,  86,  44,  50,  9,  90,  42,  61,  58,  35 

ครั้งที่ 4    รายการคำตอบ  >>  58,  60,  84,  96    //แทรกในรายการตามเงื่อนไข (ซึ่ง 60 > 58 และ < 84  จึงถูกแทรกระหว่าง 58 กับ 84                                                                               ในรายการคำตอบ)

    รายการข้อมูลที่เหลือ   8,  9,  77,  62,  92,  13,  86,  44,  50,  9,  90,  42,  61,  58,  35 

    ทำเช่นนี้ไปเรื่อย ๆ จนหมด  (ทำซ้ำ)

สุดท้าย    รายการคำตอบ  >>  8,  9,  9, 13,  35,  42,  44,  50,  58,  58,  60,  61,  62,  77,  84,  86,  90,  92,  96

    รายการข้อมูลที่เหลือ  -

จากตัวอย่าง สามารถเขียนเป็นขั้นตอนวิธี ได้ดังนี้

ขั้นตอนวิธี :  การเรียงลำดับข้อมูลแบบแทรก

ข้อมูลเข้า :   รายการข้อมูล  L  

ข้อมูลออก :  รายการคำตอบ  S  ที่เรียงลำดับแล้ว

1. ให้ S  แทนรายการคำตอบโดยเมื่อเริ่มต้น  S  จะเป็นรายการว่าง

2. ให้  N  <---  จำนวนข้อมูลในรายการ  L

3. ทำซ้ำ  N  รอบ

3.1  ให้   M  แทนข้อมูลที่กำลังพิจารณาในรายการ L

3.2  ให้  A   แทนข้อมูลตัวหน้า และ  B  แทนข้อมูลตัวหลัง

3.3   ถ้า  M >= A  and  M  <= B  แล้ว   

       ให้แทรก  M  ในรายการคำตอบ S  ที่เรียงลำดับแล้ว

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

นักเรียนได้ศึกษาการค้นหาข้อมูล target ในรายการ A แล้ว จากตัวอย่างที่ผ่านมา ขั้นตอนวิธีดังกล่าวเรียวกว่า ขั้นตอนวิธีค้นหาแบบตามลำดับ (sequential search) ขั้นตอนวิธีดังกล่าวจะพิจารณาข้อมูลทุกตัวในรายการทีละตัว ซึ่งเป็นขั้นตอนที่ดีที่สุดที่เป็นไปได้ในกรณีที่ข้อมูลไม่มีการเรียงลำดับ

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

จากตัวอย่าง 2.9 ลองพิจารณากลยุทธ์ในการทายที่เริ่มทายตั้งแต่ 1  2  3 ไปจนถึง 100 วิธีการนี้ถ้าคำตอบเป็น 95 นักเรียนจะต้องทายถึง 95 ครั้ง ในทำนองกลับกันถ้าใช้กลยุทธ์ในการทายจากมากไปหาน้อย กล่าวคือ เริ่มทายตั้งแต่ 100  99  98 ลงไปจนถึง 1 ถ้าคำตอบมีค่าน้อย นักเรียนก็จะต้องใช้จำนวนครั้งในการทายมาก สังเกตว่าด้วยกลยุทธ์ทั้งสองแบบนักเรียนไม่ได้ใช้ประโยชน์จากสมบัติการเรียงลำดับของตัวเลขเลย

     กลยุทธ์ที่มีประสิทธิภาพมากกว่าในการเล่นเกมทายตัวเลข คือ เริ่มต้นทายตัวเลขที่อยู่ตรงกลางของขอบเขตที่เป็นไปได้ ถ้าตัวเลขที่ทายไม่ถูกต้อง ให้พิจารณาปรับขอบเขตของคำตอบที่เป็นไปได้จากผลการทายที่ได้รับ เช่น ถ้าขอบเขตของคำตอบอยู่ระหว่าง 1 - 7  และทายว่าคำตอบคือ 4 แต่พบว่า เป็นคำทายที่มากเกินไป ก็สามารถปรับขอบเขตได้เป็น 1 - 3 แนวคิดดังกล่าวสามารถแสดงเป็นกลยุทธ์การทายเลขได้ดังรูป 2.6 ที่ใช้จำนวนการทายไม่เกิน 3 ครั้ง ซึ่งจะเป็นกรณีที่แย่ที่สุด (worst case) ของกลยุทธ์นี้

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

เนื่องจาก ขอบเขตของดัชนีที่เป็นไปได้คือ 1 - 7 ดัชนีแรกที่จะทายคือ 4 เมื่อพิจารณาข้อมูลลำดับที่ 4 ที่มีค่าเป็น James แล้วพบว่า John มาหลัง James จึงปรับขอบเขตของดัชนีเป็น 5 - 7 ขั้นถัดไปทายว่าดัชนีมีค่าเป็น 6 เมื่อพิจารณาข้อมูลลำดับที่ 6 มีค่าเป็น Mary แล้วพบว่า John มาก่อน Mary ทำให้ต้องปรับขอบเขตของดัชนีเป็น 5 ซึ่งเป็นค่าดัชนีที่เป็นไปได้เพียงค่าเดียว เมื่อพิจารณาข้อมูลลำดับดังกล่าวจะพชื่อ John อยู่ในตำแหน่งนั้น

วิธีการค้นหาลักษณะนี้เรียกว่าเป็น การค้นหาแบบทวิภาค (binary search)  เพราะว่าแต่ละขั้นจะแบ่งรายการข้อมูลออกเป็นสองส่วน     ขั้นตอนวิธีดังกล่าวเขียนได้ดังนี้

ขั้นตอนวิธี :  การค้นหาข้อมูลแบบทวิภาค

ข้อมูลเข้า :   รายการ A  ที่มีข้อมูลเรียงลำดับจากน้อยไปหามาก

ข้อมูลออก :  ดัชนี i ในรายการ A ที่เป็นตำแหน่งของข้อมูล target

1. ให้ n  <--- จำนวนข้อมูลในรายการ A

2. ให้ left <---  1

3. ให้ right <--- n 

4. ทำซ้ำขณะที่  left <= right

4.1 ให้ mid <--- (lift + right)/2     //หารโดยปัดเศษทิ้ง

4.2 ให้  x <--- ข้อมูลลำดับที่  mid  ในรายการ A

4.3 ถ้า  x = target  แล้ว  ให้คืนค่าดัชนีเท่ากับ  mid และจบการทำงาน

4.4 ถ้า  x < target  แล้ว     //ดัชนี mid มีค่าน้อยเกินไป  

 ให้  left <--- mid + 1   //ในกรณีนี้ให้ปรับขอบเขตล่าง

4.5 ถ้า  x > target  แล้ว    //ดัชนี mid มีค่ามากเกินไป

     ให้  right <--- mid - 1    //ในกรณีนี้ให้ปรับขอบเขตบน

   5. คืนคำตอบว่า ไม่พบข้อมูล target ในรายการ A

สรุปท้ายบท

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