เราได้เรียนรู้เรื่องการระบุข้อมูลเข้า ข้อมูลออกและเงื่อนไขของปัญหา รวมถึงเราได้เรียนรู้เรื่องการออกแบบขั้นตอนวิธีในการแก้ปัญหา เช่น การหาผลรวม การหาค่ามากที่สุด การหาค่าน้อยที่สุด การพิจารณาเลขคู่/เลขคี่ หรือการพิจารณาปีอธิกสุรทิน กันมาแล้ว แต่ในบางปัญหาอาจมีความซับซ้อนมากกว่า ดังนั้น เราอาจจะต้องใช้วิธีการออกแบบขั้นตอนวิธีในรูปแบบที่แตกต่างกันออกไป
ความหมายของการทำซ้ำ
การทำซ้ำ เป็นหนึ่งในขั้นตอนวิธีที่นิยมใช้แก้ปัญหา ใช้สำหรับการทำงานที่มีลักษณะเดียวกันซ้ำหลายรอบ
ประเภทของการทำซ้ำ
1. การทำซ้ำในรายการ จะเป็นการพิจารณารายการข้อมูล ทีละตัว จนครบทุกตัวในรายการ
2. การทำซ้ำด้วยเงื่อนไข เป็นการทำงานโดยใช้การคำนวณแบบต่างๆ มากำหนดเป็นเงื่อนไขในการทำซ้ำ
ตัวอย่างที่ 1 การทำซ้ำในรายการ
โจทย์ : แม่ค้ามีข้อมูลลูกค้าจำนวน 10 คน แม่ค้าอยากทราบว่ามีลูกค้าที่มีอายุไม่เกิน 18 ปี จำนวนกี่คน
ขั้นตอนวิธี : หาจำนวนลูกค้าที่มีอายุไม่เกิน 18 ปี
ข้อมูลเข้า : รายการอายุของลูกค้า
ข้อมูลออก : จำนวนลูกค้าที่มีอายุไม่เกิน 18 ปี
ขั้นตอนวิธี
1. count <- 0
2. พิจารณาข้อมูลรายการอายุของลูกค้าทีละตัว ไปจนครบ
2.1 ให้ x แทน อายุของลูกค้าที่พิจารณาอยู่
2.2 ถ้า x น้อยกว่า หรือเท่ากับ 18 แล้ว
count <- count + 1
3. คืนค่าจำนวนลูกค้า เท่ากับ count
กำหนดให้รายการอายุลูกค้า L = {15, 19, 20, 20, 16, 16, 17, 18, 19, 15} และ count = 0
| รอบที่ | x | count |
| 1 | 15 | 1 |
| 2 | 19 | 1 |
| 3 | 20 | 1 |
| 4 | 20 | 1 |
| 5 | 16 | 2 |
| 6 | 16 | 3 |
| 7 | 17 | 4 |
| 8 | 18 | 5 |
| 9 | 19 | 5 |
| 10 | 15 | 6 |
คืนค่า count = 6
ตัวอย่างที่ 2 การทำซ้ำในรายการ
โจทย์ : ต้องการค้นหาข้อมูล target ที่อยู่ในรายการ L
ขั้นตอนวิธี : หาข้อมูล target ที่อยู่ในรายการ L
ข้อมูลเข้า : รายการ L
ข้อมูลออก : ค่าดัชนี i ของ target ในรายการ L
ขั้นตอนวิธี
1. ให้ค่าดัชนี i มีค่าตั้งแต่ 1 จนถึง L
2. พิจารณาข้อมูลในรายการ L ทีละตัว
2.1 ให้ y <- ข้อมูลตัวที่ i ในรายการ L
2.2 ถ้า y = target แล้ว
ให้คืนค่า i และจบการทำงาน
3. ตอบว่าไม่พบข้อมูล target และจบการทำงาน
กรณีที่ 1 กำหนดให้รายการ L = {75, 60, 65, 45, 50, 66, 70, 80} และ target = 50
| รอบที่ | i | y |
| 1 | 1 | 75 |
| 2 | 2 | 60 |
| 3 | 3 | 65 |
| 4 | 4 | 45 |
| 5 | 5 | 50 |
คืนค่า i = 5
กรณีที่ 2 กำหนดให้รายการ L = {75, 60, 65, 45, 50, 66, 70, 80} และ target = 99
| รอบที่ | i | y |
| 1 | 1 | 75 |
| 2 | 2 | 60 |
| 3 | 3 | 65 |
| 4 | 4 | 45 |
| 5 | 5 | 50 |
| 6 | 6 | 66 |
| 7 | 7 | 70 |
| 8 | 8 | 80 |
ไม่พบข้อมูล target = 99
ตัวอย่างที่ 3 การทำซ้ำในรายการ
โจทย์ : การประกวดการจัดทำพานไหว้ครู มีผลการให้คะแนนดังนี้
ทีมที่ 1 ได้คะแนนรวม 55 คะแนน
ทีมที่ 2 ได้คะแนนรวม 66 คะแนน
ทีมที่ 3 ได้คะแนนรวม 45 คะแนน
ทีมที่ 4 ได้คะแนนรวม 70 คะแนน
ทีมที่ 5 ได้คะแนนรวม 57 คะแนน
ทีมที่ 6 ได้คะแนนรวม 60 คะแนน
ต้องการทราบทีมที่ชนะการประกวด
ขั้นตอนวิธี : หาทีมที่ชนะการประกวด
ข้อมูลเข้า : ผลการให้คะแนน
ข้อมูลออก : ทีมที่ชนะการประกวด โดยพิจารณาจากคะแนนรวม
ขั้นตอนวิธี
1. ให้ i = 1 และ max = คะแนนรวมของลำดับที่ i
2. พิจารณาข้อมูลในผลการตัดสินทีละรายการ
2.1 ให้ score แทนคะแนนของทีมลำดับที่ n
2.2 ถ้า score มากกว่า max
2.2.1 ให้ i = n และ ให้ max = score
3. ตอบว่าทีมที่ชนะคือทีมที่ i
กำหนดให้ i = 1 และ max = 55
| รอบที่ | n | score | i | max |
| 1 | 1 | 55 | 1 | 55 |
| 2 | 2 | 66 | 2 | 66 |
| 3 | 3 | 45 | 2 | 66 |
| 4 | 4 | 70 | 4 | 70 |
| 5 | 5 | 57 | 4 | 70 |
| 6 | 6 | 60 | 4 | 70 |
ทีมที่ชนะ คือ ทีมที่ 4
ตัวอย่างที่ 4 การทำซ้ำด้วยเงื่อนไข
โจทย์ : ทอยลูกเต๋าให้ออกเลข 1
ขั้นตอนวิธี : เปรียบเทียบหน้าลูกเต๋า ที่ออกตรงกับเลข 1
ข้อมูลเข้า : สุ่มหน้าลูกเต๋า
ข้อมูลออก : “ถูกต้อง” “มากเกินไป”
ขั้นตอนวิธี
1. ให้ score <- สุ่มไปจำนวนเต็มระหว่าง 1 – 6
2. ถ้า score = 1 แล้ว
2.1 แสดงคำว่า “ถูกต้อง” และจบการทำซ้ำ
ไม่เช่นนั้น
2.2 แสดงคำว่า “มากเกินไป” และกลับไปทำข้อ 1
| รอบที่ | score (สุ่มตัวเลข) | ข้อความ |
| 1 | 5 | มากเกินไป |
| 2 | 6 | มากเกินไป |
| 3 | 2 | มากเกินไป |
| 4 | 1 | ถูกต้อง |
ตัวอย่างที่ 5 การทำซ้ำด้วยเงื่อนไข
โจทย์ : หาตัวประกอบของ 15
ขั้นตอนวิธี : หาจำนวนที่หาร 15 ลงตัว
ข้อมูลเข้า : –
ข้อมูลออก : ตัวประกอบของ 15
ขั้นตอนวิธี
1. ให้ n = 0
2. ทำซ้ำในขณะที่ n น้อยกว่าหรือเท่ากับ 15
2.1 ถ้า 15 หารด้วย n ลงตัว ให้
2.1.2 คืนค่า n
2.2 n = n+1
| รอบที่ | n | คืนค่า |
| 1 | 1 | 1 |
| 2 | 2 | |
| 3 | 3 | 3 |
| 4 | 4 | |
| 5 | 5 | 5 |
| 6 | 6 | |
| 7 | 7 | |
| 8 | 8 | |
| 9 | 9 | |
| 10 | 10 | |
| 11 | 11 | |
| 12 | 12 | |
| 13 | 13 | |
| 14 | 14 | |
| 15 | 15 | 15 |
จะเห็นได้ว่า แม้จะเขียนขั้นตอนวิธีเพียงไม่กี่คำสั่ง แต่สามารถทำให้เกิดการทำงานได้หลายรอบ ดังนั้น ในทางคอมพิวเตอร์จึงมีการวัดความซับซ้อนเชิงเวลา เพื่อหาประสิทธิภาพของขั้นตอนวิธี หรือที่นิยมเรียกว่า O (อ่านว่า Big-O)