Chương 3: Các phương pháp sắp xếp và tìm kiếm

Chia sẻ: Le Trang | Ngày: | Loại File: PPT | Số trang:11

Thêm vào BST

Báo xấu

553
lượt xem 152
download

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

Nội dung: - Đệ qui - Tìm kiếm đệ qui - Các phương pháp tìm kiếm - Các phương pháp sắp xếp

Chủ đề:

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

Lưu

Nội dung Text: Chương 3: Các phương pháp sắp xếp và tìm kiếm

Chương 3 Cac phương phap săp xêp va ́ ́ ́ ́ ̀ tim kiêm ̀ ́ Nội dung 1 Đệ qui 2 Tim kiêm đệ qui ̀ ́ 3 Cac phương phap tim kiêm ́ ́ ̀ ́ 4 Cac phương phap săp xêp ́ ́ ́ ́
Chương 3 Cac phương phap tim kiêm và săp xêp ́ ́ ̀ ́ ́ ́ Vấn đề tìm kiếm và sắp xếp dữ liệu  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) 12/04/09 www.lhu.edu.vn
Chương 3 Cac phương phap tim kiêm và săp xêp ́ ́ ̀ ́ ́ ́ Đệ qui 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 A có cha mẹ là người” – 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 đề 12/04/09 www.lhu.edu.vn
Chương 3 Cac phương phap tim kiêm và săp xêp ́ ́ ̀ ́ ́ ́ Đệ qui 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 12/04/09 www.lhu.edu.vn
Chương 3 Cac phương phap tim kiêm và săp xêp ́ ́ ̀ ́ ́ ́ Đệ qui 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 12/04/09 www.lhu.edu.vn
Chương 3 Cac phương phap tim kiêm và săp xêp ́ ́ ̀ ́ ́ ́ Hàm đệ qui  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. Ví dụ: Xây dựng hàm tính n! theo đệ Ví dụ: Tính UCLN(x,y) theo thuật toán qui. Euclide long giaithua(int n) int ucln(int x, int y) { { if (n == 0 || n == 1) return 1; if (y == 0) return x; else return (n * giaithua(n-1)); else return (ucln(y, x % y)); } } 12/04/09 www.lhu.edu.vn
Chương 3 Cac phương phap tim kiêm và săp xêp ́ ́ ̀ ́ ́ ́ Tìm kiếm đệ qui 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  Bit 2 Bit 1 Bit 0 0 0 0 0 0 1 3 bit ~ 8 khả năng 0 1 0 0 1 1 Một “cấu hình” 1 0 0 1 0 1 1 1 0 1 1 1 12/04/09 www.lhu.edu.vn
Chương 3 Cac phương phap tim kiêm và săp xêp ́ ́ ̀ ́ ́ ́ Hàm tìm kiếm đệ qui /* Xác định thành phần xi bằng đệ quy */ void Try( int i ) { int j; If (i > N) < ghi nhận 1 cấu hình>; else { for (j thuộc tập khả năng đề cử ) if < chấp nhận khả năng ( j )> then { < Xác định xi theo khả năng ( j ) > ; Try( i+1); < bỏ việc ghi nhận khả năng ( j ) đã chọn cho xi >; } } } 12/04/09 www.lhu.edu.vn
Chương 3 Cac phương phap tim kiêm và 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
Chương 3 Cac phương phap tim kiêm và săp xêp ́ ́ ̀ ́ ́ ́ Một số ví dụ cơ bản về đệ qui  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 12/04/09 www.lhu.edu.vn
Chương 3 Cac phương phap tim kiêm và săp xêp ́ ́ ̀ ́ ́ ́ Các thuật toán 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  Yêu cầu tìm hiểu  Yêu cầu Seminar  Ý tưởng thuật toán  Tạo Slide PowerPoint  Ví dụ minh họa  Trình bày trong 15 phút  Cài đặt chương trình  Trao đổi thảo luận  Nhận xét đánh giá  Trả lời thắc mắc  Tài liệu tham khảo 12/04/09 www.lhu.edu.vn