Page 28 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 28
15-18 โครงสร้างข้อมูลแ ละข ั้นต อนว ิธี
ข้อมูลท ี่ส ่งกลับ
ค่าท่ีน ้อยท่ีสุดจ ากข้อมูลท ั้งหมดในอาร์เรย์
Function MinSearch (A, n)
1 BEGIN
2 x := A[1]
3 FOR i := 2 TO n DO
4 BEGIN
5 IF A[i] < x THEN
6 x := A[i]
7 END
8 RETURN x
9 END
การท �ำงาน
บรรทัดที่ 2 ก�ำหนดให้ส มาชิกต ัวแ รกเป็นค่าน ้อยส ุด
บรรทัดที่ 3-7 ก �ำหนดการท �ำซํ้าเริ่มตั้งแต่ส มาชิกต ัวท่ี 2 จนถึง n
บรรทัดที่ 5 เปรียบเทียบค่าน้อยส ุด (x) กับค่าป ัจจุบันข องอ าร์เรย์ (A[i])
บรรทัดท ่ี 6 ถ้าค่าปัจจุบันของอ าร์เรย์น ้อยก ว่า เปล่ียนค ่าน้อยท ี่สุดให้เป็นค่าปัจจุบันข องอ าร์เรย์
บรรทัดท่ี 7 ย้อนก ลับไปท �ำบรรทัดท ่ี 3 โดยเปล่ียนค่าดัชนีให้ช้ีตัวถัดไป
บรรทัดที่ 8 ถ้าท �ำซํ้าจนค รบท ุกส มาชิกแล้วให้ส่งค ่าก ลับเป็นค ่าน้อยท่ีสุด
จากตัวอย่างท่ี 15.4 และ 15.5 ในการประยุกต์ใช้ฟังก์ชันแบบบรูทฟอร์ซน้ัน ขั้นตอนวิธีการเหมือนเดิมคือ
เปรียบเทียบข ้อมูลก ับส มาชิกท ีล ะต ัว ส่วนท ่ีต ่างก ันค ือ ในก ารค ้นหาข ้อมูลน ้ันค ่าที่ต ้องการค ้นหาถ ูกส ่งม าเป็นข ้อมูลเ ข้า
ของฟังก์ชัน BruteForceSearch ส่วนการหาค่าน้อยท่ีสุดแ ละม ากท ี่สุดนั้นฟังก์ชัน MinSearch และ MaxSearch ใช้
สมาชิกตัวแรกของอาร์เรย์ในการเปรียบเทียบกับสมาชิกที่เหลือของอาร์เรย์ นอกจากนี้เงื่อนไขการเปรียบเทียบของ
ฟังก์ชัน BruteForceSearch ต้องการความเหมือนจึงใช้เคร่ืองหมาย “=” ส่วนฟังก์ชัน MinSearch ต้องการหาค่าท่ี
น้อยที่สุดจึงใช้เครื่องหมาย “<” และฟังก์ชัน MaxSearch ต้องการหาค่ามากท่ีสุดจึงใช้เคร่ืองหมาย “>” นอกจากน้ี
ฟังก์ชัน BruteForceSearch เม่ือพบข้อมูลที่ต้องการแล้วส่งค่ากลับทันที ส่วนฟังก์ชัน MinSearch และฟังก์ชัน
MaxSearch ต้องค ้นหาจ นถึงสมาชิกต ัวส ุดท้าย
กิจกรรม 15.1.2
1. โคด้ ของฟ งั ก์ชัน MinSearch และ MaxSearch ต่างก นั อ ยา่ งไร
2. กรณีแยท่ ีส่ ุดของข้ันตอนว ธิ ีบรทู ฟอ ร์ซเกิดข ึ้นเมอ่ื ใด
แนวตอบก จิ กรรม 15.1.2
1. ตา่ งก ันตรงบรรทัดที่ 5 ฟังกช์ นั MinSearch เปรยี บเทยี บ A[i] < x สว่ นฟงั กช์ ัน MaxSearch เปรยี บ
เทยี บ A[i] > x
2. กรณแี ยท่ ส่ี ุดเกดิ ขึน้ เม่อื ข ้อมลู ท ี่ตอ้ งการค้นหาไม่มอี ย่ใู นอารเ์ รย์ห รอื เปน็ ข ้อมลู ต ัวสดุ ท้าย
