Page 63 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 63
ขั้นตอนวิธีก ารค ้นหาข ้อมูล 15-53
ก�ำหนดค ่าเริ่มต้น
f1 = 1
f2 = 0
mid = 2
ก�ำหนดค ่าข อบบ นให้เป็นตัวเลขม ากท ี่สุดท่ีน้อยก ว่า n พร้อมท้ังก �ำหนดข อบล ่าง
รอบท่ี f1 < n f1 f2 mid
(f1 = f1 + f2) (f2 = f1 – f2) (mid = mid + 1)
1 true
(1 < 10) 1 1 3
(f1 = 1 + 0) (f2 = 1 – 0) (mid = 2 + 1)
2 true
(1 < 10) 2 1 4
(f1 = 1 + 1) (f2 = 2 – 1) (mid = 3 + 1)
3 true
(2 < 10) 3 2 5
(f1 = 2 + 1) (f2 = 3 – 1) (mid = 4 + 1)
4 true
(3 < 10) 5 3 5
(f1 = 3 + 2) (f2 = 5 – 2) (mid = 4 + 1)
5 true
(5 < 10) 8 5 6
(f1 = 5 + 3) (f2 = 8 – 3) (mid = 5 + 1)
6 true
(8 < 10) 13 8 7
(f1 = 8 + 5) (f2 = 13 – 5) (mid = 6 + 1)
7 false
(13 < 10)
ตารางข ้างต้นแ สดงค่าก ารท �ำงานขอ งลูป while (บรรทัดท่ี 5-10) ดังน้ี
รอบท่ี 1 บรรทัดที่ 5 ตรวจสอบว ่า f1 ซึ่งมีค ่าเร่ิมต้นเป็น 1 น้อยกว่า n ซึ่งม ีค่าเท่ากับ 10 จริง
บรรทัดท่ี 7 ก�ำหนดค ่า f1 = 1 ซึ่งมาจาก f1 ท่ีม ีค่าเดิมเป็น 1 บวกก ับ f2 ซึ่งม ีค ่าเป็น 0
บรรทัดที่ 8 ก�ำหนดค ่า f2 = 1 ซึ่งม าจาก f1 ท่ีม ีค ่าเป็น 1 ลบกับ f2 ซึ่งม ีค่าเป็น 0
บรรทัดที่ 9 ก�ำหนดค ่า mid = 3 ซ่ึงมาจาก mid ท่ีม ีค ่าเดิมเป็น 2 บวกกับ 1
รอบท ่ี 2 บรรทัดท ี่ 5 ตรวจส อบว ่า f1 ซึ่งมีค่าเป็น 1 น้อยกว่า n ซ่ึงมีค ่าเท่ากับ 10 จริง
บรรทัดท่ี 7 ก�ำหนดค่า f1 = 2 ซ่ึงมาจ าก f1 ท่ีม ีค่าเดิมเป็น 1 บวกกับ f2 ซึ่งมีค่าเป็น 1
บรรทัดท ี่ 8 ก�ำหนดค ่า f2 = 1 ซึ่งมาจาก f1 ที่มีค่าเป็น 2 ลบกับ f2 ซึ่งมีค่าเป็น 1
บรรทัดท ่ี 9 ก�ำหนดค ่า mid = 4 ซ่ึงมาจาก mid ท่ีมีค ่าเดิมเป็น 3 บวกกับ 1
รอบท่ี 3 บรรทัดท ่ี 5 ตรวจสอบว ่า f1 ซึ่งมีค ่าเป็น 2 น้อยก ว่า n ซ่ึงม ีค ่าเท่ากับ 10 จริง
บรรทัดที่ 7 ก�ำหนดค่า f1 = 3 ซึ่งม าจ าก f1 ท่ีม ีค ่าเดิมเป็น 2 บวกก ับ f2 ซึ่งมีค่าเป็น 1
บรรทัดที่ 8 ก�ำหนดค่า f2 = 2 ซ่ึงม าจ าก f1 ที่ม ีค ่าเป็น 3 ลบกับ f2 ซึ่งม ีค่าเป็น 1
บรรทัดที่ 9 ก�ำหนดค ่า mid = 5 ซ่ึงมาจ าก mid ท่ีม ีค่าเดิมเป็น 4 บวกก ับ 1
