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

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

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
-
Đề tài môn xử lý tín hiệu số - Các phương pháp tính tích chập
6 p |
986 |
185
-
Giáo trình Kỹ thuật lập trình - NXB Bưu Điện
421 p |
240 |
132
-
Giáo trình giải thuật - tìm kiếm và sắp xếp
0 p |
315 |
130
-
Phân tích và thiết kế giải thuật: Phân tích độ phức tạp của một số giải thuật sắp thự tự và tìm kiếm - Chương 2
0 p |
223 |
105
-
Bài giảng cách giải thuật sắp xếp
63 p |
251 |
91
-
Bài toán sắp xếp
7 p |
268 |
78
-
BÀI TẬP LẬP TRÌNH - DEMO CÁC PHƯƠNG PHÁP SẮP XẾP
37 p |
254 |
72
-
Bài toán về sắp xếp
22 p |
119 |
54
-
Ebook Bài tập kỹ thuật lập trình - TS. Nguyễn Duy Phương (chủ biên)
172 p |
82 |
45
-
GIÁO TRÌNH TRÍ TUỆ NHÂN TẠO - CHƯƠNG 2:CÁC PHƯƠNG PHÁP TÌM KIẾM LỜI GIẢI TRONG KHÔNG GIAN TRẠNG THÁI
68 p |
129 |
37
-
Bài giảng Trí tuệ nhân tạo - Chương 3: Các kỹ thuật tìm kiếm Heuristics
35 p |
79 |
23
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Các thuật toán sắp xếp
54 p |
44 |
21
-
Bài giảng Phân tích thiết kế giải thuật: Chương 2 - Trịnh Huy Hoàng
98 p |
27 |
8
-
Bài giảng Phân tích và thiết kế thuật toán: Các phương pháp giải quyết bài toán trên máy tính - Phạm Thế Bảo
10 p |
28 |
8
-
Bài giảng Các thuật toán sắp xếp
40 p |
23 |
6
-
Bài giảng Thiết bị ngoại vi và kỹ thuật ghép nối: Chương 3 - Bùi Quốc Anh
34 p |
16 |
5
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Châu Thị Bảo Hà
67 p |
17 |
2