Thuật toán Tìm kiếm nhị phân
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (326.27 KB, 22 trang )
TRƯỜNG THPT ĐỨC TRỌNG
TỔ TIN HỌC
Giáo viên thực hiện
Âu Trường Sơn
Bài dạy:
Tiết 14: Bài toán & thuật tóan
Thuật tóan tìm kiếm nhị phân
(Tin học 10)
Kiểm tra bài cũ
Cho dãy số nguyên A gồm N số nguyên khác
nhau a1, …, aN và một số nguyên k. Hãy cho biết
có hay không chỉ số i (1 ≤ i ≤ N) sao cho ai = k,
nếu có cho biết chỉ số đó.
•
•
•
Xác định bài toán
Nêu ý tưởng của thuật tóan tìm kiếm tuần tự?
Viết thuật tóan dạng liệt kê theo ý tưởng trên.
Trả lời
Bài tóan tìm kiếm:
• Input: Dãy A gồm N số hạng khác nhau a1,
a2, …, aN và khóa k
Output: Thông báo vị trí của số hạng bằng
k trong dãy A hoặc thông báo không tìm
thấy
• Ý tưởng: So sánh tuần tự ai với khóa k
(với 1≤ i ≤ N), nếu ai = k thì đưa ra i hoặc
thông báo không tìm thấy.
Thuật tóan
B1: Nhập số N, dãy A: a1 aN và khóa k
B2: i ← 1
B3: Nếu ai = k thì thông báo i rồi kết thúc
B4: i ← i + 1
B5: Nếu i > N thì thông báo dãy A không có
số hạng nào có giá trị bằng k rồi kết thúc
B6: Quay lại bước 3.
Bài tóan trên có dãy A là một
dãy số bất kỳ, vậy nếu cho dãy
A là dãy đã sắp xếp (tăng hoặc
giảm) thì nên tìm kiếm như thế
nào cho nhanh?
Ví dụ: Cho dãy không giảm a1, …, a1000
(a1
Câu hỏi:
• Với thuật tóan tìm kiếm tuần tự, phải thực
hiện bao nhiêu phép so sánh mới xác định
được vị trí số cần tìm?
• Có cách nào tìm kiếm nhanh hơn không?
(lợi dụng tính không giảm của dãy số).
Ý tưởng: thu hẹp phạm vi tìm kiếm bằng
cách so sánh k với số hạng ở giữa dãy
a1, a2, …, a(N+1)/2, … aN-1, aN
Tìm kiếm trong phạm vi này
Tìm kiếm trong phạm vi này
Nếu k < a(N+1)/2
Nếu k > a(N+1)/2
Nếu k = a[(N+1)/2] thì thông báo chỉ số (N+1)/2
Cho dãy A tăng a1, a2, …, a10 và k = 55
a1
a2
a3
a4
a5
a6
a7
22
a8
40
a9
a10
55
Làm thế nào để tìm ra vị trí của số hạng có giá trị bằng 55 nhanh nhất?
Xác định vị trí ở giữa – gọi là aGiua, nếu aGiua < k thì tìm trong
đọan a1 aGiua, ngược lại tìm trong đọan aGiua a10
Xác định aGiua như thế nào?
aGiua = a[(1+10)/2] = a5
vì a5 < k nên tìm k trong đọan a6 a10
VÍ DỤ MINH HỌA Ý TƯỞNG
Tiếp tục: Xác định lại vị trí đầu, giữa, cuối trong dãy mới:
Dau = 6; Cuoi = 10
aGiua = a[(6+10)/2] = a8, vì a8 < k nên tiếp tục tìm k trong đọan a9, a10
Tiếp tục: Xác định lại vị trí đầu, giữa, cuối trong dãy mới:
Dau = 9; Cuoi = 10; aGiua = a[(9+10)/2] = a9
vì a9 = k nên thông báo chỉ số Giua (=9), kết thúc.
Ý tưởng trên gọi là tìm kiếm nhị
phân (hay chia để trị) giúp giảm
bớt thao tác so sánh
Tiết 14: Bài toán & thuật tóan (t5)
Thuật tóan tìm kiếm nhị phân
Xét bài tóan :
Cho dãy số A gồm N số nguyên tăng khác
nhau a1, a2, …, aN và số nguyên k, nếu có
ai = k (1 ≤ k ≤ N) thì thông báo chỉ số i.
Tiết 14: Bài toán & thuật tóan (t5)
Thuật tóan tìm kiếm nhị phân
• Xác định bài tóan:
- Input: Dãy A là dãy tăng gồm N số nguyên
đôi một khác nhau a1, a2,..., aN và một số
nguyên k;
- Output: Chỉ số i mà ai = k hoặc thông báo
không có số hạng nào của dãy A có giá trị
bằng k.
• Ý tưởng:
Ý tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách
thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh
khoá với số hạng được chọn. Để làm điều đó, ta chọn số
hạng aGiua ở "giữa dãy" để so sánh với k;
Khi đó, chỉ xảy ra một trong ba trường hợp sau:
Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết
thúc.
Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên
việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2,..., aGiua–1
(phạm vi tìm kiếm mới bằng khoảng một nửa phạm vi
tìm kiếm trước đó).
Nếu aGiua < k thì thực hiện tìm kiếm trên dãy aGiua+1, aGiua+2,...,
aN.
Quá trình trên sẽ được lặp lại một số lần cho đến khi
hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm
kiếm bằng rỗng.
•Thuật toán tìm kiếm nhị phân (Cách liệt kê)
B1: Nhập N, các số hạng a1, a2,..., aN và khoá k;
B2: Dau ← 1, Cuoi ← N;
B3: Giua ← [(Dau+Cuoi)/2] ;
B4: Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết
thúc;
B5: Nếu aGiua > k thì đặt Cuoi = Giua – 1 rồi chuyển
đến bước 7;
B6: Dau ← Giua + 1;
B7: Nếu Dau > Cuoi thì thông báo dãy A không có
số hạng có giá trị bằng k, rồi kết thúc;
B8: Quay lại B3.
?
• Ở bước 7 có thể thay Dau>Cuoi bằng
Dau=Cuoi được không? Giải thích?
Không thể được, hãy xem:
Cuối
Đầu
Nếu [đầu] = [cuối] thì vẫn còn một số hạng nữa
phải so sánh với khoá k
Sơ đồ khối (SGK)
Nhập vào a1, a2,..., aN; k
Dau
Giua
←
←
1; Cuoi
←
N
[(Dau + Cuoi)/2]
aGiua = k?
Đúng
Đưa ra
Giua rồi kết
thúc
Sai
aGiua > k ?
Đúng
Cuoi
←
Giua – 1
Sai
Dau
←
Sai
Giua + 1
Dau>Cuoi?
Đúng
Thông báo dãy A không
có số hạng có giá trị
bằng k rồi kết thúc
• Hãy diễn đạt ý tưởng của thuật
tóan tìm kiếm nhị phân?
• Ý tưởng này có ý nghĩa thực tế
không? Cho ví dụ?
Bài tập nhóm
Trong thuật tóan tìm kiếm nhị phân ở SGK:
a) Có thể hóan vị B4 và B5 được không?
Giải thích?
b) Có thể thay phép gán ở B6 bằng
Dau←Giua được không? Hãy giải thích?
(gợi ý: Cho một dãy cụ thể và một giá trị
k>aN rồi mô phỏng lại thuật tóan để kiểm
tra).
Trả lời
a. Có thể hóan vị B4 và B5
b. Không thể thay phép gán ở B6 bằng
Dau←Giua được, nếu không sẽ tạo ra vòng
lặp vô tận khi không có số hạng nào bằng k.
Ví dụ: Cho dãy 0, 1, 2, 3, 5 và k = 4
Có aGiua =2, nếu cho Dau = Giua thì tìm kiếm tiếp
trên đọan [2, 3, 5]
aGiua = 3 < k, tìm kiếm tiếp trên đọan [3, 5]
Có aGiua = 3, lại tiếp tục tìm kiếm trên đọan [3, 5]
Như vậy tạo ra vòng lặp vô hạn
Cách giải quyết: thay Dau = Giua + 1
BTVN
• Học theo SGK
• Bài tập 1.47, 1.48/SBT
• Hướng dẫn bài 1.48:
Nhập điểm TBM của N học sinh
Tính điểm TBM cả lớp = (tổng điểm TBM)/N
Đếm các học sinh có điểm TBM < TBM cả
lớp.
HẾT
