Các phương pháp sắp xếp
và tìm kiếm
Các phương pháp sắp xếp
và tìm kiếm
Chương 3
Các phương pháp sắp xếp
4
Đệ qui
1
Tìm kiếm đệ qui
2
Các phương pháp tìm kiếm
3
Nội dung
N
N
ộ
ộ
i dung
i dung
3/11/2010
www.lhu.edu.vn
Chương
Chương
3 C
3 C
á
á
c phương
c phương
phá

tác trên bộ nhớ chính (RAM) và trên bộ nhớ
ngoài (các ổ đĩa)
V
V
ấ
ấ
n đ
n đ
ề
ề
t
t
ì
ì
m ki
m ki
ế
ế
m v
m v
à
à
s
s
ắ
ắ
p x
p x
ế
ế

m v
m v
à
à
s
s
ắ
ắ
p x
p x
ế
ế
p
p
Kh
Kh
á
á
i ni
i ni
ệ
ệ
m
m
 Một đối tượng X gọi là được
đ
đ
ị
ị
nh ngh

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

phá
phá
p t
p t
ì
ì
m ki
m ki
ế
ế
m v
m v
à
à
s
s
ắ
ắ
p x
p x
ế
ế
p
p
Kh
Kh
á
á
i ni
i ni

p t
ì
ì
m ki
m ki
ế
ế
m v
m v
à
à
s
s
ắ
ắ
p x
p x
ế
ế
p
p
 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.
H
H
à
à

phá
phá
p t
p t
ì
ì
m ki
m ki
ế
ế
m v
m v
à
à
s
s
ắ
ắ
p x
p x
ế
ế
p
p
Xây d
Xây d
ự
ự
ng d
ng d

i hay m
i hay m
ộ
ộ
t c
t c
ấ
ấ
u
u
h
h
ì
ì
nh b
nh b
ằ
ằ
ng c
ng c
á
á
ch th
ch th
ử
ử
t
t
ấ
ấ

á
á
c dãy nh
c dãy nh
ị
ị
phân c
phân c
ó
ó
đ
đ
ộ
ộ
d
d
à
à
i n bit
i n bit
V
V
ớ
ớ
i n=3
i n=3


T
T

á
c phương
c phương
phá
phá
p t
p t
ì
ì
m ki
m ki
ế
ế
m v
m v
à
à
s
s
ắ
ắ
p x
p x
ế
ế
p
p
/* Xác định thành phần xi bằng đệ quy */
void Try( int i )
{ int j;

qui
3/11/2010
www.lhu.edu.vn
Chương
Chương
3 C
3 C
á
á
c phương
c phương
phá
phá
p t
p t
ì
ì
m ki
m ki
ế
ế
m v
m v
à
à
s
s
ắ
ắ
p x

p t
ì
ì
m ki
m ki
ế
ế
m v
m v
à
à
s
s
ắ
ắ
p x
p x
ế
ế
p
p
 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
M
M
ộ
ộ
t s

3 C
á
á
c phương
c phương
phá
phá
p t
p t
ì
ì
m ki
m ki
ế
ế
m v
m v
à
à
s
s
ắ
ắ
p x
p x
ế
ế
p
p
 Sinh viên chia nhóm thực hiện: mỗi nhóm từ 3-5

ắ
p x
p x
ế
ế
p
p
 Yêu cầu tìm hiểu
 Ý tưởng thuật toán
 Ví dụ minh họa
 Cài đặt chương trình
 Nhận xét đánh giá
 Tài liệu tham khảo
 Yêu cầu Seminar
 Tạo Slide PowerPoint
 Trình bày trong 15 phút
 Trao đổi thảo luận
 Trả lời thắc mắc