Bài giảng về Thuật toán đệ quy | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội
Bài giảng về Thuật toán đệ quy | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội. Tài liệu được biên soạn giúp các bạn tham khảo, củng cố kiến thức, ôn tập và đạt kết quả cao kết thúc học phần. Mời các bạn đọc đón xem!
Môn: Cấu trúc dữ liệu và giải thuật (ET2100)
Trường: Đại học Bách Khoa Hà Nội
Thông tin:
Tác giả:
Preview text:
1/10/2011 REVIEW
Xácđịnhmốiquanhệ g
iữacáccặphàm và sau đây
a . 3 1, 6
b 3 1,
c 2. , THUẬTTOÁNĐÊQUY Nộidung Địnhnghĩađệquy
Đốitượngbaogồmchínhnó
Địnhnghĩađệquy
hoặcđượcđịnhnghĩadư i ớ
dạngchínhnó.
Thuậttoánđệquy VD.Đ nh ị
nghĩamộtcôngthứchợp
Phântíchthuậttoánđệquy phéptoán Đệquycónhớ
làcôngthứchợplệnếu là biếnhoặcsố
Thuậttoánquaylui(backtrackingalgorithm)
Nếu, làcôngthứchợplệthì
, , ∗ ,/,
^ cũnglàcôngthứchợplệ CuuDuongThanCong.com
https://fb.com/tailieudientucntt 1 1/10/2011
Hàmđượcđịnhnghĩađệquy Địnhnghĩađệquy
Mọiđịnhnghĩađệquyđềugồm2phần
! 1 ế 0
ườnghợpcơsở(nhỏnhất)cóthể x
ửlýtrựctiếpmàkhông
1 ! ế 0 Một tr cầnđệquy,và
Mộtphươngthứctổngquátmàbiếnđổimộttrườnghợpcụthể v ề
cáctrườnghợpnhỏhơn.Dođóbiếnđổicáctrườnghợpchođến
1 ế 1, 2
1 2 ế 2 khivề t
rườnghợpcơsở.
0 ế 0 ð
1 ế 1
2 1 2 ế 1
Danh sách banđầu Thuậttoánđệquy Chia lần 1
Thuậttoáncóchứalờigọiđệquyđếnchínhnóvớiđầu
vàokíchthướcnhỏ h ơn. Chia lần 2
VD.Sắpxếptrộn– MergeSort
MergeSort(intA[],intstart,intend) { Chia lần 3 if(start{ intmid=(start+end)/2; khi chia MergeSort(A,start,mid);
Trộn lần 1 MergeSort(A,mid+1,end); Merge(A,start,mid,end);
Trộn lần 2 } }
Trộn lần 3 CuuDuongThanCong.com
https://fb.com/tailieudientucntt 2 1/10/2011 Thuậttoánđệquy
Phântíchthuậttoánđệquy
Môtảthờigianthựchiệncủathuậttoánđệquybằng côngthứcđệ quy
GiảicôngthứcđệquyđểtìmΘ hoặcΟ bằng: VD.MergeSortcó
Ο 1 ế 1 Phư ng ơ phápthaythế 2 ươ đệ
2 Ο ế 1 Ph ng pháp cây quy
Dùngđịnhlýthợ
Bỏqua vớicácgiátrịnnhỏ(coilàhằng).Tacóthể v iếtlại là 2 2 Ο Phư ng ơ phápthaythế Gồm2bước:
Đoándạngcủalờigiải
Sửdụngquynạptoánhọcđểtìmracáchằngvàchứngminh lờigiải
côngthứcđệquy Phư ng ơ phápthaythế 2 2
Đoán Οlog
Cầnchứngminh log vớihằngsố 0 đượcchọn phùhợp CuuDuongThanCong.com
https://fb.com/tailieudientucntt 3 1/10/2011 Phư ng ơ phápthaythế Phư ng ơ phápthaythế
Giảsử log đúngvới ⁄ tứclà
Giảsửtrườnghợpcơsở 1 1 nhưng1log1 . 0 ⁄ ⁄ log ⁄ .Thayvào
Kếtquảquynạpsaitrongtrườnghợpcơsở. Tacóthể g
iảiquyếtvấnđềnàykhisửdụngcáckýhiệu 2 ệ ậ ⁄ log ⁄ ti m c n(Ο, Ω, Θ) log
log với
⁄ log log2 log Chọn v m
saocho ới ọi thìkếtquảluônđúng
VDvới 2 thì 2 2 1 2 4 2log2 với
hằngsố tachọnđủlớn(VD 5). Đúngvới 1
Vậy Οlog với 5 và 2 Tacầnchỉ r
akếtquảquynạpnàyđúngtrongmọitrường
hợp(đúngcảtrongtrườnghợpcơsở). Phư ng ơ phápthaythế Phư ng ơ phápthaythế
Đoándạnglờigiảitốt:
Tránhlỗihaymắc
Thêmbớt1hằngsố k
hônglàmthayđổidạngkếtquả
2 2 Ο
2 12 3 vẫncódạngΟlog
Saidotakhôngchứngminh Thayđổibiến
Banđầunớilỏngcậntrên,dướiđể giảmdần. 2 log
đặt log tacó 2 2 2 " ⁄
VD.Với trongvídụbanđầutacóthể c
họnΩ và
đặt 2 tacó 2 ⁄
Ο rồisau ó
đ giảmgiớihạntrên,tănggiớihạndướicho
Ο log Οlogloglog tớikhihộitụ v
ềgiátrịchínhxác CuuDuongThanCong.com
https://fb.com/tailieudientucntt 4 1/10/2011
Mộtsốtínhchấtcủahàmmũ,loga,giaithừa Ta có các công thức:
a = blogb a ; log a = 1/(log b) b a
Do đó, trong ký hiệu tiệm cận cơ số của log là không quan trọng: O(lg n n
) = O(ln ) = O(log n)
Vídụ.Chứngminhrằng Công thức Stirling:
2 1 làΟlog ö ön n ö ö 1 ö ö n ! 2 n 1 ÷ ÷ ÷ ÷ ÷ ÷ ø e ø ø ø n ø ø Giai thừa và hàm mũ:
2n < n! < nn với n > 5 ;
log n! = (n log n).
Vấnđềvớiphươngphápthaythế Vídụ 2 (tiếp) T(n) = 1 n=1 Dự đoán (chặt hơn!): T(n) = 1 n=1 T(n) = 4ôT(n/2) + n n>1 T(n) côn2 n>n0 T(n) = 4ôT(n/2) + n n>1 ụ đ Chuyển qui nạp:
Sử d ng dự oán chính xác hơn.
Giả sử T(k) côk2, k tăng chậm (là một kỹ thuật hay dùng). T(n)=4ôT(n/2)+n Dự đoán: 4ôcô(n/2)2 +n
T(n) côn2 - dôn n>n =côn2 +n 0 Không côn2 !
Giả sử T(k) côk2 - dôn, kCuuDuongThanCong.com
https://fb.com/tailieudientucntt 5 1/10/2011 Vídụ 2 (tiếp) Vídụ 2 (tiếp) T(n) = 1 n=1 Dự đoán: T(n) = 1 n=1 Dự đoán: T(n) = 4ôT(n/2) + n
n>1 T(n) côn2 - dôn n>n 0 T(n) = 4ôT(n/2) + n
n>1 T(n) côn2 - dôn n>n0
Giả sử T(k) côk2 - dôn, kGiả sử T(k) côk2 - dôn, kKhin=1:
Chuyểnquinạp,n>1: ô T(n)=1 Theođ nh ị nghĩa. T(n)=4 T(n/2)+n (địnhnghĩa)
4ô(cô(n/2)2 ‐ dô(n/2))+n (quinạp) 1 c‐d
Cóthểchọnc,dthíchhợpđểcóbấtđẳngthứcnày =côn2 ‐ 2ôdôn+n (biếnđổi)
=côn2 ‐ dôn‐ (dôn‐ n) (biếnđổi) côn2 ‐ d*n (Chọndó1) Vídụ 2 (tiếp) T(n) = 1 n=1 T(n) = 4ôT(n/2) + n n>1 Đã chứng min
T(n) 2ôn2 – 1ôn n>0 Phư ng ơ phápcâyđệquy Vậy, T(n) = O(n2). CuuDuongThanCong.com
https://fb.com/tailieudientucntt 6 1/10/2011 Phư ng ơ phápcâyđệquy Phư ng ơ phápcâyđệquy
Xétcôngthứcđệquy Ο
CâyđệquychomergeSort
1 ế 1
2 ế 1 Phư ng ơ phápcâyđệquy Phư ng ơ phápcâyđệquy
Dùngphươngphápthaythếđểchứngminhlờigiảicông
thứcđệquytìmđược.
VD. Ο Οlog
Bàitập:Xácđịnhmộtcậntrêntốtchocôngthứcđệquy
log log 3
dùngphươngphápthếđểxácnhậnlạikếtquả. 2 2
3 log 3 log 3 3 log 2 3 log 3 2
log log 3 3 log2 log Với """ " (chúýlog 2 1) CuuDuongThanCong.com
https://fb.com/tailieudientucntt 7 1/10/2011 Dùngđịnhlýthợ
Dùngđểgiảicáccôngthứcđệquydạng
,
đó 1, 1, ààệậươ
mộtcáchhiệuquả.
Bàitoánbanđầuđượcchiathành bàitoánconcókích
thướcmỗibàilà để ổ hợp bài Địnhlýthợ ⁄ ,chiphí t ng các toán con là Mastertheorem
VD.Thuậttoánsắpxếptrộn
chiathành2bàitoáncon,kíchthước/2.Chiphítổnghợp2bài
toánconlàΟ Dùngđịnhlýthợ Dùngđịnhlýthợ
Ápdụngđịnhlýthợ:
Địnhlýthợ(MasterTheorem)
1, 1 làcáchằngsố, làmộthàm. địnhnghĩađệ
9 .
quytrêncácthamsốkhôngâm
9, 3à tacó"""
≡ """ .Đây
⁄ ,trongđó
⁄ cóthểhiểulà ⁄ hoặc
làtrườnghợp1(với 1)dođó Θ
⁄ .Thì cóthểbị gi
ớihạnmộtcáchtiệmcậnnhư s au:
1. 1 tacó"""/" 1.Đâylà
Nếu Ο"""
,vớihằng 0 thì Θ
trườnghợp2,dođó Θlog
Nếu Ο""" thì Θ""" log
3 log
Nếu Ω"""
,vớihằng 0,vànếu
3, 4 và log tacó""" ≡ """
⁄ vớihằng 1 vàvớimọinđủ lớnthì
Θ
Ο., Ω""" với 0.2, ⁄
≡ 3 log với dovậy Θ log (TH3) g CuuDuongThanCong.com
https://fb.com/tailieudientucntt 8 1/10/2011 Dùngđịnhlýthợ
Chúý:Khôngphảitrườnghợpnàocũngápdụngđược địnhlýthợ!
VD. 2 log
2, 2 và log """
≡ """ " dođócóvẻ á
pdụngtrườnghợp3.
Tuynhiên log tiệmcậnlớnhơn2 với Đệquycónhớ
mọihằngsố dođókhôngthể á pdụngđược. Đệquycónhớ
Trongthuậttoánđệquy,nhữngbàitoánconcóthểđược
giảiđigiảilạinhiềulần!
VD.TínhsốFibonacci
1 ế 0,1
1 2 ế 2 Tính5
Ghinhậnlờigiải:dùngmảng Thuậttoánquaylui
Khigặpbàitoánconcầngiải:Kiểmtraxembàitoáncon Back‐trackingalgorithm
đãđượcgiảichưa:
Nếuđãgiải:lấykếtquả
Ngượclại,giảibàitoánconvàcậpnhậtlờigiảivàobảng CuuDuongThanCong.com
https://fb.com/tailieudientucntt 9 1/10/2011 Thuậttoánquaylui Thuậttoánquaylui
Bàitoán8conhậu:“Hãyxếp8conhậutrênbàncờ 8 x8
Thuậttoánxếphậu:đặtlầnlượtcácquânhậulênbàncờ
saochochúngkhôngthểănlẫnnhau”
(theo1cáchnàođó)saochoquânhậuđặtsaukhôngăn
đượcquânđãđặttrướcđó. Thuậttoánquaylui Thuậttoánquaylui
solve_from (Current_config)
Deadend:trạngtháichưakếtthúc,nhưngtakhôngthể
ifCurrent_configđãchứađủ8hậu
đặtthêmđược1quânhậunàonữa. printCurrent_config
Khirơivàotrạngtháideadendtaphảitiếnhànhquaylui else
(backtrack)lạilựachọngầnnhấtđểthửmộtkhảnăngcó
VớitậppcácôtrênbàncờmàchưabịảnhhưởngbởiCurrent_config thểkhác. {
Thêm1quânhậuvàop;
CậpnhậtlạiCurrent_config
solve_from(Current_config);
LoạibỏquânhậukhỏipcủaCurrent_config; } CuuDuongThanCong.com
https://fb.com/tailieudientucntt 10 1/10/2011 Thuậttoánquaylui Bàitoán8conhậu
Thuậttoánquaylui– backtrackingalgorithm:
Thửtìmkiếmlờigiảiđầyđủchobàitoántừviệcxâydựng Nhậnxét: lờigiảibộ ph
ận,trongđólờigiảibộ ph
ậnphảiluônphù
ộtphảicó1conhậu
hợpvớiyêucầubàitoán. Mỗi c
Conhậu1nằmtrêncột1
Trongquátrìnhthựchiện,thuậttoánmở r
ộngdầnlờigiải …
bộphận.Nếuviệcmởrộngkhiếnlờigiảibộphậnviphạm
yêucầubàitoánthìtiếnhànhquaylui,loạibỏsửađổi
Conhậujnằmtrêncộtj
gầnnhấtvàthửmộtkhảnăngxâydựnglờigiảibộphận … cóthể ( hợplệ)khác.
Conhậu8nằmtrêncột8
Cácconhậuphảikhôngcùnghàng
Cácconhậuphảikhôngnằmtrênđườngchéocủanhau Giảithuật ể function Try(column){
Thử lần lượt từng vị trí hàng Ki mtra An toàn
for (row=1;row<=8;row++){
if ([row,column]làantoàn){
Đặtconhậuvàovị t rí[row,column];
Nếu vị trí thử không bị mn==8) Con hậu thứ 8 là an toàn
con hậu nào tấn công Inkếtquả; else Đ Try(column+1);
Xóaconhậukhỏivị t rí[row,column]; } }
Xóa để tiếp tục thử vị trí } [row+1, column] CuuDuongThanCong.com
https://fb.com/tailieudientucntt 11 1/10/2011 CuuDuongThanCong.com
https://fb.com/tailieudientucntt 12