BÀI 6: TÌM KIẾM

Chia sẻ: Tran Huu Nghi | Ngày: | Loại File: PPT | Số trang:18

Thêm vào BST

Báo xấu

267
lượt xem 82
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: BÀI 6: TÌM KIẾM

1 BÀI 6: TÌM KIẾM 6.1. Tìm kiếm tuần tự 6.2. Tìm kiếm nhị phân 6.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ếm 6.1.2. Nguyên tắc tìm kiếm 6.1.3. Giải thuật 6.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á ấy 2. 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 = 2 B3: 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ân 6.2.1. Nguyên tắc tìm kiếm 6.2.2. Giải thuật 6.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ếu X < ki tìm kiếm được thực hiện tiếp với kL, …, ki-1. – Nếu X > ki tìm kiếm được thực hiện tiếp với ki+1, …, kR. – Với bảng khoá sau, sử dụng kỹ thuật tương tự. – Quá trình tìm kiếm bắt đầu với L = 1 và R = n đến khi tìm thấy X hoặc bảng khoá đang xét rỗng (không tìm thấy).
12 6.2.2. Giải thuật • Cho bảng khoá k gồm n phần tử (0 ≤ n ≤ 250) đã được sắp xếp theo thứ tự tăng dần, 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 nhị phân 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á ấy. 2. Nếu không nó sẽ đưa ra giá trị 0. • Có thể thể hiện tìm kiếm nhị phân bằng: 1. Giải thuật lặp 2. Giải thuật đệ quy
13 GT lặp tìm kiếm nhị phân Function Nhiphan(X : Integer): Byte; Var L, R, m, vitri: Byte; Begin L := 1; R := n; vitri := 0; While L k[m] then L := m + 1; Else begin vitri := m; break; end; End;
14 GT đệ quy tìm kiếm nhị phân Function Nhiphan(L, R: Byte; X : Integer): Byte; Var m, vitri: Byte; Begin If L > R then vitri := 0 Else Begin m := (L + R) div 2; If X < k[m] then vitri := Nhiphan(L, m – 1, X) Else If X > k[m] then vitri := Nhiphan(m + 1, R, X); Else vitri := m; End;
15 6.2.3. Phân tích đánh giá • Tìm kiếm nhị phân (Nhiphan): B1: Xác định phép toán tích cực – Là phép so sánh: L
16 Phân tích đánh giá • Số lượng phép so sánh phụ thuộc vào X. • So với tìm kiếm tuần tự, chi phí tìm kiếm nhị phân ít hơn khá nhiều. Sau này ta sẽ thấy: Không có 1 phương pháp tìm kiếm nào dựa trên so sánh giá trị khoá lại có thể đạt được kết quả tốt hơn tìm kiếm nhị phân. • Tuy nhiên, trước khi sử dụng tìm kiếm nhị phân bảng khoá đã phải được sắp xếp, nghĩa là thời gian chi phí cho sắp xếp cũng phải kể đến. • Nhược điểm: Nếu bảng khoá luôn biến động (bổ sung hay loại bỏ) thì chi phí cho sắp xếp lại rất nhiều. Đây chính là nhược điểm của phương pháp tìm kiếm nhị phân.
17 6.3 Câu hỏi ôn tập • Lý thuyết 1. Trình bày bài toán tìm kiếm và phát biểu bài toán dạng đơn giản nhất. 2. Trình bày nguyên tắc của phương pháp tìm kiếm tuần tự. Độ phức tạp của GT tương ứng? 3. Trình bày nguyên tắc của phương pháp tìm kiếm nhị phân. Độ phức tạp của GT tương ứng? • Thực hành – Cho bảng khoá cần tìm kiếm: 42 23 74 11 65 58 94 36 99 87 1. Minh hoạ quá trình tìm kiếm tuần tự với X1 = 50 và X2 = 23. 2. Viết chương trình sử dụng giải thuật tìm kiếm tuần tự với 1 bảng khoá sinh ngẫu nhiên và X nhập từ bàn phím.
18 Câu hỏi ôn tập – Cho bảng khoá cần tìm kiếm: 11 23 36 42 58 65 74 87 94 99 1. Minh hoạ quá trình tìm kiếm nhị phân với X1 = 50 và X2 = 23. 2. Viết chương trình sử dụng giải thuật tìm kiếm nhị phân với 1 bảng khoá sinh ngẫu nhiên và X nhập từ bàn phím, bằng: – Giải thuật lặp – Giải thuật đệ quy -----------------------