Cấu trúc dữ liệu - Chương 3: Các phương pháp sắp xếp và tìm kiếm

Các phương pháp sắp xếp và tìm kiếm Chương 3 Các phương pháp sắp xếp4 Đệ qui1 Tìm kiếm đệ qui2 Các phương pháp tìm kiếm3 Nội dung 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp  Tìm kiếm và sắp xếp dữ liệu là hai thao tác thường xuyên được thực hiện trong khai thác thông tin  Tùy thuộc vào cấu trúc lưu trữ của dữ liệu các thuật toán được xây dựng có mức độ hiệu quả khác nhau  Có thể chia thành hai nhóm: các thuật toán thao tác trên bộ nhớ chính (RAM) và trên bộ nhớ ngoài (các ổ đĩa) Vấn đề tìm kiếm và sắp xếp dữ liệu 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp Khái niệm  Một đối tượng X gọi là được định nghĩa đệ qui nếu trong phát biểu của X có dùng chính đối tượng X Ví dụ: “Người giàu là người có nhiều tài sản hoặc có cha mẹ là người giàu” – trực tiếp “Gà  Trứng  Gà” – gián tiếp  Định nghĩa bằng đệ quy có ưu điểm:  Sáng sủa  Dễ hiểu  Nêu bật được vấn đề Đệ qui 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp Khái niệm  Một chương trình đệ qui là chương trình gọi đến chính nó trong các câu lệnh, chương trình đệ qui bắt buộc phải có điều kiện dừng  Nhược điểm của đệ qui  Không phải bài toán nào cũng dùng đệ qui được  Sử dụng nhiều bộ nhớ để lưu trữ tạm thời các biến trong lúc chạy đệ qui Đệ qui 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp Khái niệm  Một định nghĩa đệ qui thường có 2 thành phần  Thành phần cố định (điều kiện dừng) : không có lời gọi đệ qui Ví dụ: 0! = 1! = 1  Thành phần đệ qui : ứng với tham số có lời gọi đệ qui đến tham số khác, dần tiến về thành phần cố định Ví dụ: n! = n*(n-1)! Nếu n > 1 Đệ qui 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp  Một hàm đệ quy về căn bản luôn gồm 2 phần.  Phần dừng: Chứa các tác động của hàm ứng với 1 số giá trị ban đầu của tham số  Phần hạ bậc: Chứa lời gọi thực hiện hàm với tham số có phạm vi nhỏ hơn. Hàm đệ qui Ví dụ: Xây dựng hàm tính n! theo đệ qui. long giaithua(int n) { if (n == 0 || n == 1) return 1; else return (n * giaithua(n-1)); } Ví dụ: Tính UCLN(x,y) theo thuật toán Euclide int ucln(int x, int y) { if (y == 0) return x; else return (ucln(y, x % y)); } 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp Xây dựng dần các thành phần của một lời giải hay một cấu hình bằng cách thử tất cả các khả năng. Ví dụ: liệt kê các dãy nhị phân có độ dài n bit Với n=3  Tìm kiếm đệ qui Bit 2 Bit 1 Bit 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Một “cấu hình” 3 bit ~ 8 khả năng 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp /* Xác định thành phần xi bằng đệ quy */ void Try( int i ) { int j; If (i > N) ; else { for (j thuộc tập khả năng đề cử ) if then { ; Try( i+1); ; } } } Hàm tìm kiếm đệ qui 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp  Ví dụ: Liệt kê các dãy nhị phân có độ dài n.  CTDL: Mảng byte: char X[20]; chứa dãy nhị phân tối đa 20 bit  Khả năng đề cử cho 1 thành phần (1 bit) X[i] là: 0 và 1 void Try(int i) { int j; if ( i > n ) InKetqua; else for (j =0; j<2; j++) { X[i] = j; Try( i + 1 ); } } 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp  Bài toán Tháp Hà Nội  Bài toán liệt kê hoán vị  Bài toán 8 quân Hậu  Bài toán Mã đi tuần Một số ví dụ cơ bản về đệ qui 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp  Sinh viên chia nhóm thực hiện: mỗi nhóm từ 3-5 người  Bốc thăm 2 trong số các thuật toán để tìm hiểu và Seminar Các thuật toán tìm kiếm và sắp xếp  Yêu cầu tìm hiểu  Ý tưởng thuật toán  Ví dụ minh họa  Cài đặt chương trình  Nhận xét đánh giá  Tài liệu tham khảo  Yêu cầu Seminar  Tạo Slide PowerPoint  Trình bày trong 15 phút  Trao đổi thảo luận  Trả lời thắc mắc