Đ QUY VÀ Gi I Ệ Ả
THU T Đ QUYẬ Ệ
CH NG 2ƯƠ
Khái ni m đ quyệ ệ
Ta nói m t đ i t ng là đ quy n u nó bao g m ộ ố ượ ệ ế ồ
chính nó nh m t b ph n ho c nó đ c đ nh ư ộ ộ ậ ặ ượ ị
nghĩa d i d ng c a chính nó.ướ ạ ủ
Ví dụ: Trong toán h c ta g p các đ nh nghĩa đ quy ọ ặ ị ệ
sau:
S t nhiên:ố ự
1 là s t nhiên.ố ự
n là s t nhiên n u n-1 là s t nhiên.ố ự ế ố ự
Hàm n giai th a: n!ừ
0! = 1
N u n>0 thì n! = n(n-1)!ế
Gi i thu t đ quyả ậ ệ
Gi i thu t đ quyả ậ ệ
N u l i gi i c a c a bài toán T đ c gi i b ng l i gi i c a ế ờ ả ủ ủ ượ ả ằ ờ ả ủ
m t bài toán T1, có d ng gi ng nh T, thì l i gi i đó đ c ộ ạ ố ư ờ ả ượ
g i là l i gi i đ quy.ọ ờ ả ệ
Gi i thu t t ng ng v i l i gi i đ quy g i là gi i thu t đ ả ậ ươ ứ ớ ờ ả ệ ọ ả ậ ệ
quy.
đây T1 có d ng gi ng T nh ng theo m t nghĩa nào đó T1 Ở ạ ố ư ộ
ph i “nh ” h n T.ả ỏ ơ
Ch ng h n, v i bài toán tính n!, thì tính n! là bài toán T còn ẳ ạ ớ
tính (n-1)! là bài toán T1 ta th y T1 cùng d ng v i T nh ng ấ ạ ớ ư
nh h n (n-1 < n).ỏ ơ
Gi i thu t đ quyả ậ ệ
Gi i thu t c a bài toán tìm t trong t đi nả ậ ủ ừ ừ ể
if (t đi n là m t trangừ ể ộ )
tìm t trong trang nàyừ
else
{M t đi n vào trang “gi a”;ở ừ ể ữ
Xác đ nh xem n a nào c a t đi n ch a t c n tìm;ị ử ủ ừ ể ứ ừ ầ
if (t đó n m n a tr cừ ằ ở ử ướ )
tìm t đó n a tr c;ừ ở ử ướ
else tìm t đó n a sau;ừ ở ử
}
Gi i thu t này đ c g i là gi i thu t đ quyả ậ ượ ọ ả ậ ệ
Gi i thu t đ quyả ậ ệ
Nh n xét:ậ
Sau m i l n t đi n đ c tách làm đôi thì m t n a thích ỗ ầ ừ ể ượ ộ ử
h p s l i đ c tìm b ng m t chi n thu t nh đã dùng ợ ẽ ạ ượ ằ ộ ế ậ ư
tr c đó (n a này l i đ c tách đôi).ướ ử ạ ượ
Có m t tr ng h p đ c bi t, đó là sau nhi u l n tách đôi, ộ ườ ợ ặ ệ ề ầ
t đi n ch còn m t trang. Khi đó vi c tách đôi ng ng l i và ừ ể ỉ ộ ệ ừ ạ
bài toán tr thành đ nh đ ta có th tìm t mong mu n ở ủ ỏ ể ể ừ ố
b ng cách tìm tu n t . Tr ng h p này g i là ằ ầ ự ườ ợ ọ tr ng h p ườ ợ
suy bi nế.