intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 3: Tìm kiếm

Chia sẻ: Vdgv Vdgv | Ngày: | Loại File: PDF | Số trang:33

Thêm vào BST
Báo xấu
119
lượt xem 15
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chính của chương 3 Tìm kiếm nằm trong bài giảng cấu trúc dữ liệu và thuật toán nhằm trình bày về các nội dung chính như sau: khái quát về tìm kiếm, tìm tuyến tính (Linear Search), tìm nhị phân (Binary Search)...Cùng tìm hiểu bài giảng để hiểu sâu hơn về thuật 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 giảng Cấu trúc dữ liệu và thuật toán - Chương 3: Tìm kiếm

  1. Chương 4: TÌM KIẾM (SEARCHING)
  2. Nội dung 2 1. Khái quát về tìm kiếm 2. Tìm tuyến tính (Linear Search) 3. Tìm nhị phân (Binary Search) Chương 3: Tìm kiếm
  3. Khái quát về tìm kiếm 3  Tìm kiếm là một yêu cầu rất thường xuyên trong đời sống hàng ngày cũng như trong tin học  Ví dụ:  Tìm kiếm một sinh viên trong lớp  Tìm kiếm một tập tin, thư mục trong máy  Để đơn giản ta xét bài toán tìm kiếm như sau:  Cho một dãy số gồm các phần tử a1, a2, ..., an. Cho biết trong dãy này có phần tử nào có giá trị bằng X (cho trước) hay không? Chương 3: Tìm kiếm
  4. Khái quát về tìm kiếm 4  Xét hai cách tìm kiếm:  Tìm kiếm tuyến tính (Linear Search) hay còn gọi là tìm kiếm tuần tự (Sequential Search)  Tìm kiếm nhị phân (Binary Search) Chương 3: Tìm kiếm
  5. Nội dung 5 1. Khái quát về tìm kiếm 2. Tìm tuyến tính (Linear Search) 3. Tìm nhị phân (Binary Search) Chương 3: Tìm kiếm
  6. 2. Tìm tuyến tính (Linear Seach) 6 Ý tưởng:  Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần lượt từng phần tử của danh sách với giá trị X cần tìm  Nếu có phần tử bằng X, thuật toán dừng lại (thành công)  Nếu đến cuối danh sách mà không có phần tử nào bằng X, thuật toán dừng lại (không thành công)  If we find a match, the search terminates successfully by returning the index of the element  If the end of the list is encountered without a match, the search terminates unsuccessfully Chương 3: Tìm kiếm
  7. 2. Tìm tuyến tính (Linear Seach) 7 Thuật toán: B1: i = 0 ; // bắt đầu từ phần tử đầu tiên B2: so sánh A[i] với X, có 2 khả năng :  A[i] = X : Tìm thấy. Dừng  A[i] ≠ X : Sang B3 B3: i=i+1 // Xét phần tử tiếp theo trong mảng Nếu i=n : Hết mảng, không tìm thấy. Dừng Ngược lại: lặp lại B2 Chương 3: Tìm kiếm
  8. 2. Tìm tuyến tính (Linear Seach) 8 Ví dụ: 12 2 8 5 1 X=8 X=8 i=0 12 2 8 5 1 X=8 i=1 12 2 8 5 1 X=8 i=2 12 2 8 5 1 Dừng Chương 3: Tìm kiếm
  9. 2. Tìm tuyến tính (Linear Seach) 9 5 Vị trí = 2 Khóa tìm 0 1 2 3 4 5 6 7 7 13 5 21 6 2 8 15 Tìm thành công Số lần so sánh: 3 Chương 3: Tìm kiếm
  10. 2. Tìm tuyến tính (Linear Seach) 10 9 Khóa tìm 0 1 2 3 4 5 6 7 7 13 5 21 6 2 8 15 Không tìm thấy Số lần so sánh: 8 Chương 3: Tìm kiếm
  11. 2. Tìm tuyến tính (Linear Seach) 11 void lsearch (int list[], int n, int key) { int flag = 0; // giả sử lúc đầu chưa tìm thấy for(int i=0; i
  12. 2. Tìm tuyến tính (Linear Seach) 12 int lsearch(int list[], int n, int key) { int find= -1; for(int i=0; i
  13. 13  Phân tích, đánh giá thuật toán Trường hợp Số lần so sánh Giải thích Tốt nhất 1 Phần tử đầu tiên có giá trị x Xấu nhất n+1 Phần tử cuối cùng có giá trị x Giả sử xác suất các phần tử trong mảng Trung bình (n+1)/2 nhận giá trị x là như nhau.  Vậy giải thuật tìm tuyến tính có độ phức tạp tính toán cấp n: T(n) = O(n) Chương 3: Tìm kiếm
  14. Tìm tuyến tính (Linear Seach) 14 Phân tích, đánh giá thuật toán: Trường hợp Số lần so sánh Giải thích Tốt nhất 1 Phần tử đầu tiên có giá trị x Xấu nhất n+1 Phần tử cuối cùng có giá trị x Giả sử xác suất các phần tử trong mảng Trung bình (n+1)/2 nhận giá trị x là như nhau. Chương 3: Tìm kiếm
  15. Nội dung 15 1. Khái quát về tìm kiếm 2. Tìm tuyến tính (Linear Search) 3. Tìm nhị phân (Binary Search) Chương 3: Tìm kiếm
  16. 3. Tìm nhị phân (Binary Seach) 16  Điều kiện:  Danh sách phải được sắp xếp trước  Ý tưởng:  So sánh giá trị muốn tìm X với phần tử nằm ở vị trí giữa của danh sách:  Nếu bằng, tìm kiếm dừng lại (thành công)  Nếu X lớn hơn thì tiếp tục tìm kiếm ở phần danh sách bên phải phần tử giữa  Nếu X nhỏ hơn thì tiếp tục tìm kiếm ở phần danh sách bên trái phần tử giữa  We compare the element with the element placed approximately in the middle of the list  If a match is found, the search terminates successfully  Otherwise, we continue the search for the key in a similar manner either in the upper half or the lower half Chương 3: Tìm kiếm
  17. 3. Tìm nhị phân (Binary Seach) 17 Thuật toán: B1: Left = 0, Right = n-1 B2: Mid = (Left + Right)/2 // lấy vị trí cận giữa B3: So sánh X với A[Mid], có 3 khả năng xảy ra:  A[Mid] = X // tìm thấy. Dừng thuật toán  A[Mid] > X Right = Mid-1 // Tiếp tục tìm trong dãy A[0]… A[Mid-1]  A[Mid] < X Left = Mid+1 // Tiếp tục tìm trong dãy A[Mid+1]… A[Right] B4: Nếu (Left
  18. 3. Tìm nhị phân (Binary Seach) 18 10 Vi trí = 3 Khóa tìm Khóa cần tìm nhỏ hơn hoặc bằng bằng lớn hơn 0 1 2 3 4 5 6 7 8 9 2 5 8 10 12 13 15 18 21 24 left mid right Tìm thấy Số lần so sánh: 4 Chương 3: Tìm kiếm
  19. 3. Tìm nhị phân (Binary Seach) 19 0 1 2 3 4 5 6 7 Ví dụ: 1 2 4 5 6 8 12 15 X=8 X=8 Left=0, Right=7, Mid=3 1 2 4 5 6 8 12 15 Left=4, Right=7, Mid=5 X=8 1 2 4 5 6 8 12 15 Dừng Chương 3: Tìm kiếm
  20. 3. Tìm nhị phân (Binary Seach) 20 void BSearch (int list[], int n, int key) Không đệ quy { int left, right, mid, flag = 0; left = 0; right = n-1; while (left
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2