BÀI 6: TÌM KIẾM

Tìm kiếm là đòi hỏi rất thường xuyên trong xử lý tinhọc. Bài toán tìm kiếm:“ Cho 1 bảng chính gồm n bản ghi R1, R2, …, Rn. Mỗibản ghi Ri (1 ≤ i ≤ n) tương ứng với 1 khoá Ki. Hãy tìmbản ghi có giá trị khoá tương ứng bằng X cho trước.”– X được gọi là khoá tìm kiếm hay đối trị tìm kiếm.
Nội dung trích xuất từ tài liệu:
BÀI 6: TÌM KIẾM 1 BÀI 6: TÌM KIẾM6.1. Tìm kiếm tuần tự6.2. Tìm kiếm nhị phân6.3. Câu hỏi ôn tập 2 6.1. Tìm kiếm tuần tự6.1.1. Bài toán tìm kiếm6.1.2. Nguyên tắc tìm kiếm6.1.3. Giải thuật6.1.4. Phân tích đánh giá 3 6.1.1. Bài toán tìm kiếm• Tìm kiếm là đòi hỏi rất thường xuyên trong xử lý tin học.• Bài toán tìm kiếm:“ Cho 1 bảng chính gồm n bản ghi R1, R2, …, Rn. Mỗi bản ghi Ri (1 ≤ i ≤ n) tương ứng với 1 khoá Ki. Hãy tìm bản ghi có giá trị khoá tương ứng bằng X cho trước.” – X được gọi là khoá tìm kiếm hay đối trị tìm kiếm. – Công việc tìm kiếm sẽ hoàn thành khi xảy ra 1 trong 2 tình huống sau: 1. Tìm được bản ghi có giá trị khoá = X (thành công) 2. Không tìm được bản ghi có giá trị khoá = X (không thành công)• Chú ý: Khoá được coi như đại diện của bản ghi, vì vậy trong các GT và ví dụ, ta chỉ nói tới khoá. 4 Bài toán tìm kiếm• Bài toán tìm kiếm bản ghi có giá trị khoá bằng X trong bảng chính chứa các bản ghi R1, R2, …, Rn coi như được đặt ra 1 cách đơn giản với bảng khoá chứa các khoá K1, K2, …, Kn và Ki ≠ Kj nếu i ≠ j. Tìm kiếm khoá X trong 1 bảng các khoá K1, K2, …, Kn (Ki ≠ Kj nếu i ≠ j)• Sau 1 phép tìm kiếm không thành công, có thể xuất hiện yêu cầu bổ sung thêm bản ghi mới, GT như vậy được gọi là GT tìm kiếm có bổ sung.• Giá trị của khoá có thể là số, ký tự, xâu ký tự,… nhưng để cho tiện ta coi khoá là các số nguyên. 5 6.1.2. Nguyên tắc tìm kiếm• Tìm kiếm tuần tự (sequential searching) là kỹ thuật tìm kiếm rất đơn giản và cổ điển.• Nội dung có thể tóm tắt như sau:• Nguyên tắc tìm kiếm: – Lần lượt so sánh X (khoá tìm kiếm) với các khoá K1, K2, …, Kn trong bảng cho tới khi tìm thấy X (X = Km) hoặc hết bảng khoá mà chưa tìm thấy X. – Kết quả: 1. Tìm được vị trí m của khoá (đầu tiên) có giá trị bằng X. 2. Không tìm được khoá có giá trị bằng X. 6 6.1.3. Giải thuật• Cho bảng khoá k gồm n phần tử (0 ≤ n ≤ 250), các khoá và X là các số nguyên Integer được nhập từ bàn phím hoặc sinh ngẫu nhiên (bằng random).• Giải thuật tìm kiếm tuần tự sẽ thực hiện tìm kiếm trong bảng xem có khoá nào bằng X không.1. Nếu có sẽ đưa ra chỉ số của khoá ấy2. Nếu không nó sẽ đưa ra giá trị 0.3. Trong giải thuật này có sử dụng 1 khoá phụ kn+1 mà giá trị của nó chính là X. 7 GT tìm kiếm tuần tựFunction Tuantu(X: Shortint) : Byte;Var i: Byte;Begin i := 1; k[n + 1] := X; {Tìm kiếm tuần tự} While k[i] X do i := i + 1; {Không tìm thấy} If i = n + 1 Then Tuantu := 0 {Tìm thấy} Else Tuantu := i; 8 6.1.4. Phân tích đánh giá• Tìm kiếm tuần tự (Tuantu): B1: Xác định phép toán tích cực – Là phép so sánh: k[i] X B2: Xác định số lần thực hiện của phép toán tích cực – Số lượng phép so sánh phụ thuộc vào tình trạng của bảng khoá (so với giá trị X). – T/h tốt nhất (min) xảy ra khi k[1] = X, số lần thực hiện phép X toán tích cực là: C min =1 – T/h xấu nhất (max) xảy ra khi k[n + 1] = X, nghĩa là không tìm X thấy X, số lần thực hiện phép toán tích cực là: Cmax = n + 1 9 Phân tích đánh giá– T/h trung bình (tb) xảy ra khi việc tìm thấy X ở mọi vị trí là đồng khả năng. Số lần thực hiện phép toán tích cực trong t/h trung bình có thể coi là: n +1 Ctb = 2B3: Kết luận độ phức tạp của GT tìm kiếm tuần tự– T/h tốt nhất: Tmin (n) = O(1)– T/h xấu nhất và trung bình: Tmax (n) = Ttb (n) = O(n) 10 6.2. Tìm kiếm nhị phân6.2.1. Nguyên tắc tìm kiếm6.2.2. Giải thuật6.2.3. Phân tích đánh giá 11 6.2.1. Nguyên tắc tìm kiếm• Phép tìm kiếm nhị phân luôn chọn khoá “ở giữa” bảng khoá đang xét để thực hiện so sánh với khoá tìm kiếm X.• Nguyên tắc tìm kiếm nhị phân: – ng  L + R  Giả sử bải = khoá đang xét là kL, …, kR thì khoá ở giữa bảng sẽ là ki với:  2    – Tìm kiếm sẽ kết thúc nếu X = ki. – N ...