การทำซ้ำ

การทำซ้ำ

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

ความหมายของการทำซ้ำ

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

ประเภทของการทำซ้ำ

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)