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

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

ตัวแปร

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

ในการเขียนขั้นตอนวิธีอาจจะระบุว่าให้กำหนดค่าให้กับตัวแปร หรืออาจใช้

สัญลักษณ์ ← ในการเขียน เช่น

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

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

สัญลักษณ์ที่ใช้ในการเขียนขั้นตอนวิธีนอกเหนือจากการใช้สัญลักษณ์ทางคณิตศาสตร์ทั่วไป

← , := , <-- , = หมายถึง การกำหนดค่าให้กับตัวแปร

! , "~"   , ¬ หมายถึง นิเสธ

!= , <> หมายถึง การไม่เท่ากัน

>= หมายถึง การเปรียบเทียบมากกว่าหรือเท่ากับ

<= หมายถึง การเปรียบเทียบน้อยกว่าหรือเท่ากับ

** , ^ หมายถึง การยกกำลัง

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

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

ตัวอย่างที่ 2.3 ระบบรดน้ำต้นไม้อัตโนมัติ

การตัดสินใจรดน้ำต้นไม้ในขั้นตอนวิธีของระบบรดน้ำต้นไม้อัตโนมัติ ระบบจะต้องอ่านข้อมูลความชื้นของดินแล้วเปรียบเทียบกับค่าที่กำหนดไว้ (สมมติค่าความชื้นที่กำหนดเป็น 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 ส่งสัญญาณปิดน้ำ

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

การออกแบบและพิจารณาเงื่อนไข

1.การสร้างเงื่อนไขอย่างง่าย

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

ถ้า x > Max แล้ว 

ให้ Max ← x

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

ในทางตรรกศาสตร์ "ประพจน์" (proposition) คือ ข้อความ ที่สามารถบอกค่าความจริงได้ ซึ่งจะมีค่าเป็นจริงหรือเท็จเท่านั้น ในการกำหนดเงื่อนไขในขั้นตอนวิธีมักจะเขียนในรูปแบบของประโยคเปิดซึ่งเป็นประโยคที่มีตัวแปร เช่น x > Max และเมื่อแทนค่าตัวแปรแล้ว ประโยคเปิดจะกลายเป็นประพจน์ เพราะสามารถบอกค่าความจริงได้

ตัวอย่างที่ 2.4 ตรวจสอบพิกัดโรงเรียน

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

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

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

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

1.การจัดเรียงแบบเลือก (selection sort)

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

ตัวอย่างที่ 2.7 เรียงลำดับจำนวนเต็ม

83 56 97 61 6 7 78 63 93 12

87 50 44 7 54 42 90 34 56 62

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

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

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

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

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

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

3. ทำซ้ำ N รอบ

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

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

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

1. รายการคำตอบ :    -                             

รายการข้อมูลที่เหลือ :    83 56 97 61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                           

2. รายการคำตอบ :    6                            

รายการข้อมูลที่เหลือ :    83 56 97 61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                           

3. รายการคำตอบ :    6   7                   

รายการข้อมูลที่เหลือ :     83 56 97 61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                          

4. รายการคำตอบ :    6   7 7           

รายการข้อมูลที่เหลือ :     83 56 97 61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                          

5. รายการคำตอบ :    6   7 7 12           

รายการข้อมูลที่เหลือ :     83 56 97 61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                          

6. รายการคำตอบ :    6   7 7 12 34           

รายการข้อมูลที่เหลือ :     83 56 97 61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                          

.

.

.

20. รายการคำตอบ :    6 7 7 12 34 42 44 50 54 56 56 61 62 63 78 83 87 90 93 97             

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

2.การจัดเรียงแบบแทรก (insertion sort)

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

1. รายการคำตอบ :    -                            

รายการข้อมูลที่เหลือ :    83 56 97 61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                           

2. รายการคำตอบ :    83                            

รายการข้อมูลที่เหลือ :    56 97 61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                           

3. รายการคำตอบ :    56 83                            

รายการข้อมูลที่เหลือ :    97 61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                           

4. รายการคำตอบ :    56 83 97                            

รายการข้อมูลที่เหลือ :    61 6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                           

5. รายการคำตอบ :    56 61 83 97                            

รายการข้อมูลที่เหลือ :    6 7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                           

6. รายการคำตอบ :    6 56 61 83 97                            

รายการข้อมูลที่เหลือ :    7 78 63 93 12 87 50 44 7 54 42 90 34 56 62                           

.

.

.

20. รายการคำตอบ :    6 7 7 12 34 42 44 50 54 56 56 61 62 63 78 83 87 90 93 97            

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

ถ้าต้องการค้นหาข้อมูล 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 อยู่ที่ตำแหน่งนั้น