Trường Đi h c Khoa h c T nhiênạ ọ ọ ự
Khoa Công ngh thông tinệ
B môn Tin h c cộ ọ ơ sở
1
Đng Bình Phặ ương
dbphuong@fit.hcmus.edu.vn
NH P MÔN L P TRÌNHẬ Ậ
K THU T L P TRÌNHỸ Ậ Ậ
Đ QUYỆ
VC
VC
&
&
BB
BB
22
N i dungộ
K thu t l p trình đ quyỹ ậ ậ ệ
Tổng quan về đệ quy1
Các vấn đề đệ quy thông dụng2
Phân tích giải thuật & khử đệ quy3
Các bài toán kinh điển4
VC
VC
&
&
BB
BB
33
Bài toán
Cho S(n) = 1 + 2 + 3 + … + n
=>S(10)? S(11)?
K thu t l p trình đ quyỹ ậ ậ ệ
1
1 +
2
2 + … +
10
10
1
1 +
2
2 + … +
10
10
=
55
55
+
11
11 =
66
66
1
1+
2
2+ … +
10
10
=
=
S(10)
S(11)
1
1+
2
2+ … +
10
10
S(10)= +
11
11
= +
11
11
55
55 =
66
66
S(10)
+
11
11
55
55
+
11
11
VC
VC
&
&
BB
BB
44
2 bước gi i bài toánả
K thu t l p trình đ quyỹ ậ ậ ệ
=
S(n) +
n
nS(n-1)
=
S(n-1) +
n-1
n-1S(n-2)
=
…+
…
……
=
S(1) +
1
1S(0)
=
S(0)
0
0
Bước 1. Phân tích
hân tích thành bài toán đồng
d ng nhạ ưng đơn gi n hả ơn.
ng l i bài toán ừ ạ ở đồng d ng ạ
đơn gi n nh t có th xác ả ấ ể định
ngay k t qu .ế ả
Bước 2. Th ngế ược
ác định k t qu bài toán ế ả đồng
d ng t ạ ừ đơn gi n ảđến ph c t p ứ ạ
K t qu cu i cùng.ế ả ố
VC
VC
&
&
BB
BB
55
Khái ni m ệđệ quy
K thu t l p trình đ quyỹ ậ ậ ệ
Khái ni mệ
V n ấđề đệ quy là v n ấđề được
định nghĩa b ng chính nó.ằ
Ví dụ
T ng ổS(n) được tính thông qua
t ng ổS(n-1).
2 đi u ki n quan tr ngề ệ ọ
T n t i bồ ạ ước đệ quy.
Đi u ki n d ng.ề ệ ừ