Chương 3: Các phương pháp sắp xếp và tìm kiếm
lượt xem 152
download
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
Bình luận(0) Đăng nhập để gửi bình luận!
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 và 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 và 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 và 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 và 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 và 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 và 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 và 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 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
- Chương 3 Cac phương phap tim kiêm và 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 và 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Chương 2 - Tổng hợp thống kê
49 p | 112 | 11
-
Cấu trúc dữ liệu và giải thuật II - Chương 3
28 p | 80 | 11
-
Tài liệu môn học Hệ thống thông tin quản lý
178 p | 63 | 10
-
Bài giảng Phân tích và thiết kế giải thuật: Chương 3 - PGS.TS. Dương Tuấn Anh
47 p | 99 | 7
-
Giáo trình Cấu trúc dữ liệu và thuật toán: Phần 2 (In năm 2013)
179 p | 9 | 5
-
Chương 3 Các phương pháp tìm kiếm và sắp xếp
3 p | 87 | 4
-
Bài giảng môn Cấu trúc dữ liệu - Chương 3: Kỹ thuật sắp xếp
29 p | 62 | 3
-
Bài giảng Phân tích thiết kế và giải thuật - Chương 3: Sắp xếp ngoại
27 p | 78 | 1
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