›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Giải thuật tìm kiếm - Trần Minh Thái

pptx 32 trang huongle 3610
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Giải thuật tìm kiếm - Trần Minh Thái", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_2_giai_thuat.pptx

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Giải thuật tìm kiếm - Trần Minh Thái

  1. Chương 2.1. Giải thuật tìm kiếm Trần Minh Thái Email: minhthai@itc.edu.vn Website: www.minhthai.edu.vn 1
  2. Mục tiêu ▪Xác định được vai trò của tìm kiếm và sắp xếp trong hệ thống thông tin ▪Nắm vững và minh họa được giải thuật tìm kiếm tuyến tính và tìm kiếm nhị phân trên mảng một chiều ▪Cài đặt được giải thuật tìm kiếm bằng ngôn ngữ C/C++ 2
  3. Suy nghĩ ? Tại sao hầu hết phần mềm phải có chức năng tìm kiếm và sắp xếp, mối quan hệ giữa tìm kiếm và sắp xếp? 3
  4. Nhu cầu tìm kiếm và sắp xếp ▪Tìm kiếm: Có trong hầu hết trong các hệ thống thông tin ▪Muốn tìm kiếm nhanh và hiệu quả → dữ liệu có thứ tự → sắp xếp 4
  5. Các giải thuật tìm kiếm ▪Có 2 giải thuật thường được áp dụng: Tìm tuyến tính và tìm nhị phân. ▪Đặc tả: a1 a2 a3 a4 a5 an-1 aN ▪Tập dữ liệu được lưu trữ là dãy số a1, a2, ,aN. ▪Khai báo: int a[N]; ▪Khóa cần tìm: int x; 5
  6. Tìm kiếm tuyến tính (Linear Search) Ý tưởng Lần lượt so sánh x với phần tử thứ nhất, thứ hai, của mảng a cho đến khi gặp được phần tử cần tìm, hoặc hết mảng 6
  7. Tìm kiếm tuyến tính ▪Minh họa tìm x =10 10 ĐãChưa tìm thấyhết tại 7 5 12 41 10 32 13 9 15 3 vịmảng trí 5 1 2 3 4 5 6 7 8 9 10 ▪Minh họa tìm x =25 Chưa hết 25 Đã hết mảngmảng 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 7
  8. Giải thuật Bước 1: i = 1; // bắt đầu từ phần tử đầu tiên của dãy Bước 2: 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 Bước 3. Bước 3: ▪ i = i+1; // xét tiếp phần tử kế 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 Bước 2. 8
  9. Nguyên tắc cài đặt hàm tìm kiếm ▪Nếu có xuất hiện phần tử có giá trị x thì trả về vị trí tìm được ▪Ngược lại thì trả về -1 9
  10. Cài đặt int LinearSearch(int a[], int N, int x) { int i=0; while ((i<N) && (a[i]!=x )) i++; if(i==N) return -1; //tìm hết mảng else return i; //a[i] là phần tử có khoá x } 10
  11. Cải tiến Dùng lính canh giúp giảm bớt phép so sánh ▪Minh họa tìm x =10 10 7 5 12 41 10 32 13 9 15 3 10 1 2 3 4 5 6 7 8 9 10 11 ▪Minh họa tìm x = 25 25 7 5 12 41 10 32 13 9 15 3 2525 1 2 3 4 5 6 7 8 9 10 11 11
  12. Cài đặt int LinearSearch2(int a[],int N,int x) { int i=0; a[N] = x; // thêm phần tử x sau mảng while (a[i]!=x ) i++; if (i==N) return -1; // tìm hết mảng else return i; // tìm thấy x tại vị trí i } Độ phức tạp tính toán cấp n: T(n)=O(n) 12
  13. Q & A 13
  14. Tìm kiếm nhị phân (Binary Search) Ý tưởng ▪Áp dụng đối với dãy số đã có thứ tự ▪Mỗi bước tiến hành so sánh x với phần tử ở giữa của dãy hiện hành để quyết định phạm vi tìm kế tiếp 14
  15. Minh họa tìm x = 41 x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 Tìm thấy x tại vị trí 6 l m m r m 15
  16. Minh họa tìm x = 45 x x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 l m m r l > r: Kết thúc: Không tìm thấy m m 16
  17. Giải thuật Bước 1: left = 1; right = N; //tìm kiếm tất cả các phần tử Bước 2: mid = (left+right)/2; // lấy mốc so sánh So sánh a[mid] với x, có 3 khả năng : ▪ a[mid] = x: Tìm thấy. Dừng ▪ a[mid] > x: //tìm tiếp x trong dãy con aleft amid -1 right =mid - 1; ▪ a[mid] < x: //tìm tiếp x trong dãy con amid +1 aright left = mid + 1; Bước 3: Nếu left <= right //còn phần tử chưa xét tìm tiếp. Lặp lại Bước 2. Ngược lại: Dừng //Ðã xét hết tất cả các phần tử. 17
  18. int BinarySearch(int a[],int N,int x ) { int left =0; right = N-1; int mid; while (left <= right) { mid = (left + right)/2; if (x == a[mid]) return mid;//Thấy x tại mid if (x < a[mid]) right = mid -1; else left = mid +1; } return -1; // Tìm hết dãy mà không có x } Độ phức tạp tính toán cấp n: T(n)=O(log n) 2 18
  19. Q & A 19
  20. Code minh họa #include #include #include #define MAX 1000 void TaoMang(int a[], int N); void XuatMang(int a[], int N); int LinearSearch(int a[], int N, int x); 20
  21. void main() { srand((usigned int) time (NULL)); int a[MAX], N = 20, x, kq; TaoMang(a, N); XuatMang(a, N); cout >x; kq=LinearSearch(a, N, x); if(kq==-1) cout<<“Khong co phan tu can tim”; else cout<<“Phan tu can tim tai vi tri: ”<<kq; } 21
  22. void TaoMang(int a[], int N) { for(int i=0; i<N; i++) a[i]=rand()%N; } void XuatMang(int a[], int N) { for(int i=0; i<N; i++) cout<<a[i]<<“ “; } 22
  23. int LinearSearch(int a[], int N, int x) { int i=0; while ((i<N) && (a[i]!=x )) i++; if(i==N) return -1; else return i; } 23
  24. Bài tập áp dụng Viết chương trình tự động phát sinh ra mảng có giá trị ngẫu nhiên có thứ tự tăng dần; nhập vào giá trị cần tìm x; in ra vị trí xuất hiện của x (nếu có) và số lần so sánh với mỗi phương pháp tìm kiếm: tuyến tính và nhị phân 24
  25. Bài tập lý thuyết ▪LT1_1: Cho dãy số sau: 3 4 6 6 12 16 21 34 41 80 1 2 3 4 5 6 7 8 9 10 Cho biết vị trí tìm thấy và số lần so sánh để tìm được phần tử có giá trị x = 6 khi áp dụng giải thuật tìm kiếm: tuyến tính và nhị phân. ▪LT1_2: Xây dựng giải thuật tìm kiếm phần tử có giá trị nhỏ nhất trong dãy số: Dùng mã tự nhiên, mã giả và lưu đồ. 25
  26. Bài tập lý thuyết – Hướng dẫn ▪LT1_1: Tìm x = 6 3 4 6 6 12 16 21 34 41 80 1 2 3 4 5 6 7 8 9 10 Tìm x theo phương pháp tuyến tính Vị trí So sánh với x Kết quả i=1 (a[i]=3) x Tăng vị trí i i=2 (a[i]=4) x Tăng vị trí i i=3 (a[i]=6) = x Dừng, trả về vị trí i (3) 26
  27. Bài tập lý thuyết – Hướng dẫn ▪LT1_1: Tìm x = 6 3 4 6 6 12 16 21 34 41 80 1 2 3 4 5 6 7 8 9 10 Tìm x theo phương pháp nhị phân Xét đoạn Vị trí So sánh Kết quả giữa đoạn với x l=1, r=10 m=(l+r)/2=5 (a[m]=12) x Cập nhật r=m-1=4 (a[m]>x → xét trái) l=1, r=4 m=(l+r)/2=2 (a[m]=4) x Cập nhật l=m+1=3 (a[m]<x → xét phải) l=3, r=4 m=(l+r)/2=3 (a[m]=6) = x Dừng, trả về vị trí m (3) 27
  28. Q & A 28
  29. Bài tập lý thuyết – Hướng dẫn LT1_2 ▪Input: Mảng số nguyên a, kích thước n ▪Output: vt: vị trí phần tử có giá trị nhỏ nhất ▪Mã tự nhiên: Bước 1: i=2, vt=1; Bước 2: Nếu i>N thì trả về giá trị vt, kết thúc; Bước 3: Nếu a[i]<a[vt] thì vt=i; i=i+1; Lặp lại Bước 2; 29
  30. Bài tập lý thuyết – Hướng dẫn LT1_2 ▪Input: Mảng số nguyên a, kích thước n ▪Output: vt: vị trí phần tử có giá trị nhỏ nhất ▪Pseudocode: i=2, vt=1; WHILE i ≤ N DO IF a[i]<a[vt] THEN vt=i; i=i+1; END WHILE RETURN vt; 30
  31. Bài tập lý thuyết – Hướng dẫn LT1_2 ▪Flow Chart: 31
  32. Q & A 32