Page 59 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 59
ขั้นตอนว ิธีก ารค้นหาข้อมูล 15-49
5. การป ระยกุ ตใ์ช้ข้นั ตอนวิธกี ารค้นหาขอ้ มูลแบบการประมาณคา่ ในชว่ ง
ข้ันต อนว ิธีแต่ละป ระเภทโดยทั่วไปแ ล้วมีงานที่เหมาะส มจ ะประยุกต์ใช้การค ้นหาแบบป ระมาณค ่าในช่วง เป็น
วิธีการท ่ีเหมาะส มม ากส �ำหรับการค้นหาข้อมูลขนาดใหญ่จ ากไฟล์บนดิสก์
กจิ กรรม 15.2.2
1. จากฟงั ก์ชนั interpolation_search บรรทัดท ่ี 12 ถ้า (adjust < 0) OR (adjust > 1) เป็นจ ริงแสดงวา่
ไม่พ บขอ้ มูล เพราะอ ะไร
2. นอกเหนอื จ ากข อ้ ก �ำ หนดท ว่ี า่ ข อ้ มลู ม กี ารจ ดั เรยี งม าแ ลว้ interpolation_search มขี อ้ ส มมตฐิ านเพม่ิ เตมิ
เก่ียวก ับข้อมูลอยา่ งไร
แนวต อบกิจกรรม 15.2.2
1. ถา้ ค ่า adjust ซึ่งเปน็ ค ่าท่ไี ดม้ าจากก ารค�ำ นวณอ ตั ราสว่ น (x - A[left]) / (A[right] - A[left]) ไมอ่ ยู่
ในช่วงระหวา่ ง 0 และ 1 หมายถึง ค่าทส่ี ืบค้นไมอ่ ยใู่ นชว่ งรายการท่สี ืบคน้ ทัง้ น้อี ัตราส่วนจะมากกว่า 1 กต็ อ่ เมอ่ื
x - A[left] มากกว่า A[right] - A[left] แสดงว า่ x มากกวา่ A[right] นั่นคือข อ้ มลู อยเู่ กนิ ข อบขวา ในทางก ลบั ก นั
อัตราสว่ นจะนอ้ ยกว่า 0 ก็ตอ่ เม่ือ x - A[left] นอ้ ยกวา่ 0 แสดงวา่ x นอ้ ยกว่า A[left] แสดงวา่ ขอ้ มูลอยู่ตา่ํ กวา่
ขอบซ า้ ย
2. interpolation_search มขี อ้ สมมติฐานว่าขอ้ มลู ม ีการเพม่ิ ขนึ้ แ บบเชิงเส้น
เรือ่ งท ี่ 15.2.3
การค น้ หาข อ้ ม ูลแ บบฟ ิโบนักซี
โดยป กติการค ้นหาส ารสนเทศในร ายการท ี่เรียงล�ำดับ สามารถส ืบค้นเรียงต ามร ายการ หรือข ้ามไปย ังต�ำแหน่ง
ที่ป ระมาณว ่าน า่ จะพบข้อมลู ซง่ึ ก ารขา้ มนั้นไมจ่ �ำเป็นต ้องหาแบบแ บง่ ค ร่ึงเสมอไป การค ้นหาแ บบฟิโบนักซี (Fibonacci
search) นี้แทนท่ีจะใช้การค้นหาแบบแบ่งคร่ึงท่ีเร่ิมต้นตรงกลางแล้วตรวจสอบข้อมูลว่าอยู่ช่วงทางซ้ายหรือช่วง
ท างขวา ก็เปล่ียนมาใช้การแบ่งโดยก�ำหนดช่วงจ ากตัวเลขฟิโบนักซี (Fibonacci Number) ซึ่งม ีรูปแ บบก ารหาตัวเลข
ถัดไปจ ากส มการต ่อไปน ี้
F0 = F1 = 1 ส�ำหรับ n > 2
Fn = Fn-1 + Fn-2
ตัวอย่างต ัวเลขท ี่ได้จ ากสมการข้างต้นเป็นด ังนี้
0, 1, 1, 2, 3, 5, 8, 13, …
ซึ่งตัวเลขเหล่าน ี้จ ะน �ำมาใช้ในการก �ำหนดช ่วงในการหาข ้อมูล
