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

Vấn đề tìm kiếm và sắp xếp dữ liệu đề kiế và xế dữ liệuNội dung Nội 1 2 3 4 Đệ 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. 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ộ...
Nội dung trích xuất từ tài liệu:
Chương 3 Các phương pháp tìm kiếm và sắp xếp Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Vấn đề tìm kiếm và sắp xếp dữ liệu đề kiế và xế dữ liệ Tìm kiếm và sắp xếp dữ liệu là hai thao tác Nội dung Nội thường xuyên được thực hiện trong khai thác thông tin 1 Đệ qui Tùy thuộc vào cấu trúc lưu trữ của dữ liệu các 2 Tìm kiếm đệ qui thuật toán được xây dựng có mức độ hiệu quả 3 khác nhau Các phương pháp tìm kiếm Có thể chia thành hai nhóm: các thuật toán thao 4 Các phương pháp sắp xếp tác trên bộ nhớ chính (RAM) và trên bộ nhớ ngoài (các ổ đĩa) 3/11/2010 www.lhu.edu.vnChương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Đệ qui Đệ qui Khái niệm Khá niệ Khái niệm Khá niệ Một đối tượng X gọi là được định nghĩa đệ qui nếu nghĩ đệ trong phát biểu của X có dùng chính đối tượng X Một chương trình đệ qui là chương trình gọi đến Ví dụ: “Người giàu là người có nhiều tài sản hoặc có cha chính nó trong các câu lệnh, chương trình đệ qui mẹ là người giàu” – trực tiếp bắt buộc phải có điều kiện dừng “Gà Trứng Gà” – gián tiếp Nhược điểm của đệ qui Định nghĩa bằng đệ quy có ưu điểm: Không phải bài toán nào cũng dùng đệ qui được Sáng sủa Sử dụng nhiều bộ nhớ để lưu trữ tạm thời các biến Dễ hiểu trong lúc chạy đệ qui Nêu bật được vấn đề 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vnChương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Hàm đệ qui đệ Đệ qui Một hàm đệ quy về căn bản luôn gồm 2 phần. Khái niệm Khá niệ 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ố Một định nghĩa đệ qui thường có 2 thành phần Phần hạ bậc: Chứa lời gọi thực hiện hàm với tham số Thành phần cố định (điều kiện dừng) : không có lời có phạm vi nhỏ hơn. gọi đệ qui Ví dụ: Xây dựng hàm tính n! theo đệ Ví dụ: Tính UCLN(x,y) theo thuật toán Ví dụ: 0! = 1! = 1 qui. Euclide Thành phần đệ qui : ứng với tham số có lời gọi đệ long giaithua(int n) int ucln(int x, int y) ...