Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
(cid:67)(cid:104)(cid:432)(cid:417)(cid:110)(cid:103) (cid:51)
VVấấn đn đềề ttììm kim kiếếm vm vàà ssắắp xp xếếp dp dữữ liliệệuu
(cid:67)(cid:225)(cid:99)(cid:32)(cid:112)(cid:104)(cid:432)(cid:417)(cid:110)(cid:103) (cid:112)(cid:104)(cid:225)(cid:112)(cid:32)(cid:115)(cid:7855)(cid:112)(cid:32)(cid:120)(cid:7871)(cid:112) (cid:67)(cid:225)(cid:99)(cid:32)(cid:112)(cid:104)(cid:432)(cid:417)(cid:110)(cid:103) (cid:112)(cid:104)(cid:225)(cid:112)(cid:32)(cid:115)(cid:7855)(cid:112)(cid:32)(cid:120)(cid:7871)(cid:112) (cid:118)(cid:224)(cid:32)(cid:116)(cid:236)(cid:109)(cid:32)(cid:107)(cid:105)(cid:7871)(cid:109) (cid:118)(cid:224)(cid:32)(cid:116)(cid:236)(cid:109)(cid:32)(cid:107)(cid:105)(cid:7871)(cid:109)
i dung NNộội dung Nội dung
(cid:61607) 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
1 Đệ qui
2 Tìm kiếm đệ qui
(cid:61607) 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
3 Các phương pháp tìm kiếm
4 Các phương pháp sắp xếp
(cid:61607) 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)
3/11/2010
www.lhu.edu.vn
Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
ĐĐệệ quiqui ĐĐệệ quiqui
KhKháái ni
i niệệmm
KhKháái ni
i niệệmm
(cid:61607) Một đối tượng X gọi là được đđịịnh ngh nh nghĩĩa đa đệệ quiqui 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
(cid:61607) 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
(cid:61607) Nhược điểm của đệ qui
“Gà (cid:61664) Trứng (cid:61664) Gà” – gián tiếp (cid:61607) Định nghĩa bằng đệ quy có ưu điểm:
3/11/2010
3/11/2010
www.lhu.edu.vn
www.lhu.edu.vn
(cid:61607) Không phải bài toán nào cũng dùng đệ qui được (cid:61607) Sử dụng nhiều bộ nhớ để lưu trữ tạm thời các biến trong lúc chạy đệ qui (cid:61607) Sáng sủa (cid:61607) Dễ hiểu (cid:61607) Nêu bật được vấn đề
Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
HHààm đm đệệ quiqui ĐĐệệ quiqui
(cid:61607) Một hàm đệ quy về căn bản luôn gồm 2 phần.
(cid:61607) Phần dừng: Chứa các tác động của hàm ứng với 1 số
KhKháái ni
i niệệmm
giá trị ban đầu của tham số
(cid:61607) Phần hạ bậc: Chứa lời gọi thực hiện hàm với tham số
(cid:61607) Một định nghĩa đệ qui thường có 2 thành phần (cid:61607) 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ụ: 0! = 1! = 1 (cid:61607) Thành phần đệ qui : ứng với tham số có lời gọi đệ
Ví dụ: Xây dựng hàm tính n! theo đệ qui. long giaithua(int n) {
Ví dụ: Tính UCLN(x,y) theo thuật toán Euclide int ucln(int x, int y) {
if (n == 0 || n == 1) return 1; else return (n * giaithua(n-1));
if (y == 0) return x; else return (ucln(y, x % y));
}
}
3/11/2010
3/11/2010
www.lhu.edu.vn
www.lhu.edu.vn
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
Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
HHààm tm tììm kim kiếếm đm đệệ quiqui TTììm kim kiếếm đm đệệ quiqui
nh phầần cn củủa ma mộột lt lờời gi i giảải hay m i hay mộột ct cấấuu
/* Xác định thành phần xi bằng đệ quy */ void Try( int i ) { int j;
Xây dựựng dng dầần cn cáác thc thàành ph Xây d hhìình bnh bằằng cng cáách th năng.. ch thửử ttấất ct cảả ccáác khc khảả năng
If (i > N) < ghi nhận 1 cấu hình>; else {
VVíí ddụụ: li: liệệt kê c t kê cáác dãy nh c dãy nhịị phân c i n bit phân cóó đ độộ ddàài n bit
Bit 2 Bit 1 Bit 0
0
0
0
for (j thuộc tập khả năng đề cử ) if < chấp nhận khả năng ( j )> then {
3 bit ~ 8 khả năng
0
0
1
0
1
0
0
1
1
Một “cấu hình”
1
0
0
< Xác định xi theo khả năng ( j ) >
1
0
1
}
}
1
1
0
}
1
1
1
3/11/2010
3/11/2010
www.lhu.edu.vn
www.lhu.edu.vn
i n=3 (cid:61664)(cid:61664) VVớới n=3
Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
(cid:61607) CTDL: Mảng byte: char X[20]; chứa dãy nhị phân tối đa 20 bit (cid:61607) Khả năng đề cử cho 1 thành phần (1 bit) X[i] là: 0 và 1
(cid:61607) Ví dụ: Liệt kê các dãy nhị phân có độ dài n. MMộột st sốố vvíí ddụụ cơ b cơ bảản vn vềề đ đệệ quiqui
void Try(int i) {
(cid:61607) Bài toán Tháp Hà Nội (cid:61607) Bài toán liệt kê hoán vị (cid:61607) Bài toán 8 quân Hậu (cid:61607) Bài toán Mã đi tuần
3/11/2010
3/11/2010
www.lhu.edu.vn
www.lhu.edu.vn
int j; if ( i > n ) InKetqua; else for (j =0; j<2; j++) { X[i] = j; Try( i + 1 ); } }
Chương 3 C3 Cáác phương Chương
c phương phápháp tp tììm kim kiếếm vm vàà ssắắp xp xếếpp
c thuậật tot toáán tn tììm kim kiếếm vm vàà ssắắp xp xếếpp
CCáác thu (cid:61607) Sinh viên chia nhóm thực hiện: mỗi nhóm từ 3-5
người
(cid:61607) Bốc thăm 2 trong số các thuật toán để tìm hiểu
và Seminar
(cid:61607) Yêu cầu tìm hiểu
(cid:61607) Yêu cầu Seminar
3/11/2010
www.lhu.edu.vn
(cid:61607) Tạo Slide PowerPoint (cid:61607) Trình bày trong 15 phút (cid:61607) Trao đổi thảo luận (cid:61607) Trả lời thắc mắc (cid:61607) Ý tưởng thuật toán (cid:61607) Ví dụ minh họa (cid:61607) Cài đặt chương trình (cid:61607) Nhận xét đánh giá (cid:61607) Tài liệu tham khảo
