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!

1/10/2011
REVIEW
Xácđịnh m gi các c iquanhệ a phàm󰇛󰇜󰇛󰇜sau
đây
a󰇜
.
3󰇛1󰇜, 6
b󰇜
3 1󰇜,
c󰇜
2
.
,
THUTTOÁN QUYĐÊ
Nidung
Địnhnghĩađệquy
Thu toán quyt đệ
Phân thu toán quytích t đệ
Đệquy nh
Thu toán quay luit (backtrackingalgorithm)
Địnhnghĩađệquy
Đối tượngbaogm chính
hocđượcđịnhngh a d iĩ ướ
d ng chính .
VD. nh ngh a m tĐị ĩ công th c hp
toánphép
công th c l h p ệnếu
bi ho c sến
Nếu, công th c l hp ệthì
󰇛󰇜 󰇛󰇜, ,󰇛󰇜,󰇛/󰇜,
󰇛^󰇜c ng công th cũ h p lệ
1
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
Hàmđược nh nghđị ĩađệquy
!
1ế0
1!ế0

1ế1,2
1 2ế2
ð
0ế0
1ế1
21 2ế1
Địnhnghĩađệquy
M i nh ngh đị ĩađệquy g m ph nđều 2
Mt tr ường chp ơsở(nhỏnh t) th x tr c ti ể ử ếp không
c quy, nđệ
Mt ph ương th c t ng quát bi ếnđổi m t tr ng c th v ườ h p ụ ể ề
các tr ng nh n. Do bi i các tr ng ườ h p ỏhơ đó ếnđổ ườ h p chođến
khiv tr ng cề ườ h p ơs.
Thu t toán quy đệ
Thu t toán ch a l i giđệquyđếnchínhv i đu
vào kích th nh h n ước ỏ ơ .
VD. S x p ế p tr n MergeSort
MergeSort(intA[], int start, int end)
{
if(start<end)
{
int mid = (start+end)/2;
MergeSort(A, start, mid);
MergeSort(A, mid+1, end);
Merge(A,start,mid,end);
}
}
khi chia
Trn l n 1
Trn l n 2
Trn l n 3
Danh sách ban uđầ
Chia ln 1
Chia ln 2
Chia ln 3
2
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
Thu t toán quy đệ
t th i gian th hi thu ả c nca ttoánđệquybng
công th quy cđệ
VD. MergeSort
Ο1ế1
2
2
Οế1
B qua v iỏ 󰇛󰇜 cácgiátrịnnhỏ(coi ng). Ta th vi t l ih ể ế
󰇛󰇜
2
2
Ο
Phân tích thu t toán quy đệ
Gi i công th cđệquyđểtìmΘhocΟb ng:
Ph ng pháp thay thươ ế
Ph ng pháp câyươ đệquy
Dùng nhđ th
Ph ng pháp thay thươ ế
Ph ng pháp thay thươ ế
Gm2bước:
Đ oánd ng caligi i
Sửd n hng quy ptoán cđểtìm ra các ng h ch ng minh
l i gi i
công thcđệquy
2
2
Đoán Ο󰇛log󰇜
Cnch ng minh 󰇛󰇜logv i ng s h ố0đượcchn
phù ph
3
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
Ph ng pháp thay thươ ế
Gi úng vảsử󰇛󰇜logđ i
tc
󰇛
󰇜
log
. Thay vào
2
log
log
loglog2
log
Đúngvi1
Ta c ch ra k n ỉ ếtquảquy np nàyđúngtrong m i tr ng ườ
hp( úng cđ ảtrong tr ng c ườ hp ơs).
Ph ng pháp thay thươ ế
Gi tr ng cảsử ườ hp ơsở1 1nh ng .ư 1log10
Kếtqu quy trongả n p sai trườngh pcơs .
Ta th gi i quy ể ếtvnđềnàykhisửd ung các hi
ti m c ( ) n Ο,Ω,Θ
logv i
Ch v mn
saocho i i
thì k ếtquảluônđúng
VD v i 2thì 2 21 242log2vi
h nngsốta ch đủln(VD5).
V y Ο󰇛log󰇜v i 52
Ph ng pháp thay thươ ế
Đ oánd ngl igi itt:
Thêm ng không thaybt1h số làm đổidng k ế tqu
2
12 3v ngn d Ο󰇛log󰇜
Ban i ng c trên,đầun l n dướiđể
gi m n. d
VD. V i󰇛󰇜trong ta th ch dụbanđầu ể nΩ󰇛󰇜
Ο󰇛
󰇜r i ó gi m gi trên, t ng gi i i sauđ ihn ă h n dướ cho
t i khi v hitụ ề ịgiátr chínhxác
Ph ng pháp thay thươ ế
Tránh i hay m cl
2
2
Ο󰇛󰇜
Sai do ta không ch ng minh 󰇛󰇜
Thay biđi ến
2 log
đặtlogta 2
22
"
đặt 󰇛2
󰇜ta 2
Οlog Ο󰇛logloglog󰇜
4
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
. Ch ng minh rd ng
2
1Ο󰇛log󰇜
M s tính ch ct ố t a hàm mũ, loga, giai th a
Ta có các công thc:
a
= b
log
b
a
; log
b
a = 1/(log
a
b)
Do đó, trong ký hiu tim cn cơ s c ng: a log là không quan tr
O(lg n n) = O(ln ) = O(log )n
Công thc Stirling:
Giai th :a và hàm mũ
2
n
< n! < n
n
vi n > 5 ;
log log n! = (n n).
ö ö
ö ö ö ö
÷ ÷÷ ÷ ÷ ÷
ø ø ø ø
ø ø
1
! 2 1
n
n
n n
e n
Vnđềviphươngphápthay th ế
T(n) = T(n/2) + n 4ô
4ô ôc (n/2)
2
+ n
= c ôn
2
+ n
T(n) = 1 n=1
T(n) = 4ôT(n/2) + n n>1
D đoán (cht hơn!):
T(n) côn
2
n>n
0
Gi s , T(k) côk
2
k<n. Chng minh T(n) . côn
Chuy p:n qui n
Không c n !ô
2
d 2 (ti p) ụ ế
T(n) = 1 n=1
T(n) = 4ôT(n/2) + n n>1
D đoán:
T(n) côn
2
- dôn n>n
0
Gi n. s n, T(k) côk
2
- dô k<n. Cn CM T(n) côn
2
- dô
S d ng d đoán chính xác hơn.
tăng ch m (là mt k thu t hay dùng).
5
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
d 2 (ti p) ụ ế
Khi n=1:
T(n) nh ngh a.=1 Theođị ĩ
1 c th ch n d ể c, d thích h p để đẳ b t ng th c này
T(n) = 1 n=1
T(n) = 4ôT(n/2) + n n>1
D đoán:
T(n) côn
2
- dôn n>n
0
Gi n. s n, T(k) côk
2
- dô k<n. CM T(n) côn
2
- dô
d 2 (ti p) ụ ế
Chuy qui p,n n n>1:
T(n) 4 T(n/2) nh a)= ô +n (đị nghĩ
4ô ô ô(c (n/2)
2
d (n/2))+n (qui p)n
= +c 2ôn
2
ôd nô n (biếnđổi)
=côn d
2
ôn‐ (dôn‐ n) (biếnđổi)
côn
2
d*n (Ch n dó1)
T(n) = 1 n=1
T(n) = 4ôT(n/2) + n n>1
D đoán:
T(n) n côn
2
- dô n>n
0
Gi n. s T(k) côk
2
- dôn, k<n. CM T(n) côn
2
- dô
d 2 (ti p) ụ ế
T(n) = 1 n=1
T(n) = 4ôT(n/2) + n n>1
Đã chng min
T(n) 2ôn
2
1ôn n>0
Vy, T(n) = O(n
2
).
Ph ng pháp cây quyươ đệ
6
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
Ph ng pháp cây quyươ đệ
Cây quy mergeSortđệ cho 
1ế1
2
ế1
Ph ng pháp cây quyươ đệ
Xét công th quy cđệ

Ο󰇛󰇜
Ph ng pháp cây quyươ đệ
Dùng ph ng thay th ch ng minh l i gi công ươ pháp ếđể i
th quy tìmcđệ được.
VD.

Ο Ο󰇛log󰇜


log

log



3
log

3
log3
2
3
log2
2
3
log3
loglog3
2
3
log2
log
V
i
"""
"
Ph ng pháp cây quyươ đệ
Bài t p :Xác nh m cđị t ntrênttchocôngthcđệquy
3
dùng ph ng pháp th xác nh k ươ ếđể nl i ếtqu.
7
(chú ý ) log21
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
Định th
Mastertheorem
Dùng nh thđị
Dùngđểgi các công th quy ngi cđệ d

,
đó1,1,ààệậươ
m cách hi qu .t u
Bài toán toán con kích ban bàiđầuđượcchiathành
th m
ước ibài
,chiphí t ng các toán conđể hp bài
󰇛󰇜
VD. Thu t toán s p x ếptrn
chia toán con, kích th cthành2bài ướ /2. phí t ngChi h p 2bài
toán con Ο󰇛󰇜
Dùng nh thđị
Định th ợ(Master Theorem)
1,1 các h ng s , 󰇛󰇜mthàm.󰇛󰇜định ngh ĩađệ
quy trên các thamsốkhôngâm

󰇛󰇜, trong đó
th ểhi u
ho c
. Thì 󰇛󰇜th b gi i h nể ị mt cách ti mc n nh sau: ư
N uế Ο󰇛
""" 
󰇜, v i h ng 0thì Θ󰇛 󰇜
N uế Ο󰇛
"""
󰇜thì Θ󰇛
"""
log󰇜
N uế Ω󰇛
""" 
󰇜, v i h ng 0, n uế

󰇛󰇜v i h ng 1 v i mi n l n đủ thì
Θ󰇛󰇛󰇜󰇜
Dùng nh thđị
Áp d ng định th :
9
.
9,3à ta
"""
"""
. âyĐ
tr ng (v ườ hp1 i1) do ó đ Θ󰇛
󰇜

1.
1ta
"""
/"
1. ây Đ
tr ng 2, do óườ hp đ Θ󰇛log󰇜
3
log
3,4 logta
"""
"""
Ο󰇛
.
󰇜, Ω󰇛
"""

󰇜vi0.2,

3
󰇛log󰇜vi
do v y
Θ󰇛log󰇜(TH3)
8
󰇛 g 󰇜
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
Dùng nh thđị
Chúý:Không ph i tr ng ườ hpnàoc cũng áp ng d đượ
định thợ!
VD. 2
log
2,2 log
"""
"""
"
do ó v áp ng tr ngđ ẻ d ườ h p3.
Tuy nhiên
logti m c nlnhơn2
v i
m i ng do ó không th áp ng c. h số đ ể d đượ
Đệquynh
Đệquynh
Trong thu ttoánđệquy, nh ng toán con th bài ểđược
gi i gi i nhi n! đi il ul
VD. Tính sốFibonacci
1ế0,1
1 2ế2
Tính󰇛5󰇜
Ghi nh n l i gi i: dùng ng m
Khi g toán con c gi i: Ki m tra xem toán con pbài n bài
đãđượcgiichưa:
Nếuđã gi i: l y k ế tqu
Ng c l i, gi i toán con cượ bài pnh tligi ivào ngb
Thu toán quay luit
Back tracking algorithm
9
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
Thu t toán quay lui
Bài toán con u: “Hãy x 8 h ế p8 conhutrên c 8x8bàn ờ
sao cho chúngkhông th l ểăn nnhau”
Thu t toán quay lui
Thuttoán x ế ph u:đặt tlnlượ các quân lên c hu bàn ờ
(theo cách ó) quân1 nàođ sao cho huđặtsaukhôngăn
đượcquânđãđặttrướcđó.
Thu t toán quay lui
solve_from (Current_config)
if Current_config đã ach đủ8hu
printCurrent_config
else
Vi t p p các trên bàn c ô ờ ch b nh ưa ịả h ng b iưở Current_config
{
Thêm 1 quân hu vào p;
Cp nh tl i Current_config
solve_from(Current_config);
Lo i b quân h u kh i p c ỏ aCurrent_config;
}
Thu t toán quay lui
Deadend: tr ngtháichưakế tthúc, nh ng ta không thư ể
đặt thêmđược 1quân hu nào na.
Khi r vào tr ơi ngtháideadendta ph i ti quay lui ếnhành
(backtrack) l i ch g la n nnhtđểthửmt khảnăng
thểkhác.
10
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
Thu t toán quay lui
Thuttoán quay lui backtrackingalgorithm:
Th tìm ki m giử ế li iđầy toán vi xây ngđủchobài từ c d
l i gi ph n, trong ibộ đó l gi ph ph i luôn phù i ibộ n
hpv i yêu c toán. ubài
Trong quá trình th chi n, thu toán m r t ở ngdnl igii
b u nộph n. Nế vi mc ởr ng khi i gi i ếnl bộph vi ph m
yêu c toán thì ti quay lui, lo i i ubài ếnhành bỏsađổ
g nhn t t th m ử kh ng xây ngnă d li gi ibộph n
th (h ) ể pl khác.
Bài toán 8 con h u
Nh n xét:
Mi c tph i 1 con h u
Con h u 1 n mtrên c t1
Con h u n j mtrên c tj
Con h u 8 n mtrên c t8
Cáccon ph ihu khôngcùngng
Cáccon ph i m trên ng chéo c a nhauhu khôngn đườ
Gi thu ti
function Try (column) {
for (row = 1; row <= 8; row++) {
if ([row, column] an toàn ){
Đặtcon h u vào v trí [row, column]; ị
mn == 8)
In k ế t qu ;
else
Try (column + 1);
Xóa con h u kh i v trí [row, column]; ị
}
}
}
Con hu th 8 là an toàn
Xóa vđể tiếp tc th trí
[row+1, column]
Th ln lượt tng v trí hàng
Nếu v trí th không b
con h u nào t n công
Đ
Ki tra An toànm
11
CuuDuongThanCong.com https://fb.com/tailieudientucntt
1/10/2011
12
CuuDuongThanCong.com https://fb.com/tailieudientucntt
| 1/24

Preview text:

1/10/2011 REVIEW
 Xácđịnhmốiquanhệ g
 iữacáccặphàm󰇛󰇜 và󰇛󰇜 sau đây
a󰇜    .  3󰇛  1󰇜,   6
b󰇜      3   1󰇜,   
c󰇜    2.  ,    THUẬTTOÁNĐÊQUY Nộidung Địnhnghĩađệquy
 Đốitượngbaogmchính
 Địnhnghĩađệquy
hocđượcđịnhnghĩadư i ớ 
dngchính.
 Thuậttoánđệquy VD.Đ nh ị
nghĩamộtcôngthchp
 Phântíchthuậttoánđệquy phéptoán  Đệquycónhớ
  làcôngthứchợplệnếu là biếnhoặcsố
 Thuậttoánquaylui(backtrackingalgorithm)
 Nếu,  làcôngthứchợplệthì
󰇛  󰇜,󰇛  󰇜,󰇛 ∗ 󰇜,󰇛/󰇜,
󰇛^󰇜 cũnglàcôngthứchợplệ CuuDuongThanCong.com
https://fb.com/tailieudientucntt 1 1/10/2011
Hàmđượcđịnhnghĩađệquy Địnhnghĩađệquy
 Mọiđịnhnghĩađệquyđềugồm2phần
 !  1               ế  0
 ườnghợpcơsở(nhỏnhất)cóthể x
 ửlýtrựctiếpmàkhông
    1 !     ế  0  Một tr cầnđệquy,và
 Mộtphươngthứctổngquátmàbiếnđổimộttrườnghợpcụthể v  ề
cáctrườnghợpnhỏhơn.Dođóbiếnđổicáctrườnghợpchođến     
1          ế  1, 2
   1     2      ế  2 khivề t
 rườnghợpcơsở.
0          ế  0     ð
1          ế  1
2   1     2  ế  1
Danh sách banđầu Thuậttoánđệquy Chia ln 1
Thuttoánchaligiđệquyđếnchínhviđầu
vàokíchthướcnhh  ơn. Chia ln 2
 VD.Sắpxếptrộn– MergeSort
MergeSort(intA[],intstart,intend) { Chia ln 3 if(start{ intmid=(start+end)/2; khi chia MergeSort(A,start,mid);
Trn ln 1 MergeSort(A,mid+1,end); Merge(A,start,mid,end);
Trn ln 2 } }
Trn ln 3 CuuDuongThanCong.com
https://fb.com/tailieudientucntt 2 1/10/2011 Thuậttoánđệquy
Phântíchthuậttoánđệquy
 Môtảthờigianthựchiệncủathuậttoánđệquybằng côngthứcđệ quy 
 GiảicôngthứcđệquyđểtìmΘ hoặcΟ bằng:  VD.MergeSortcó
Ο 1     ế  1  Phư ng ơ phápthaythế      2 ươ   đệ
2  Ο     ế  1  Ph ng pháp cây quy
 Dùngđịnhlýthợ
Bỏqua󰇛󰇜 vớicácgiátrịnnhỏ(coilàhằng).Tacóthể v  iếtlại 󰇛󰇜 là     2 2  Ο  Phư ng ơ phápthaythế  Gồm2bước:
 Đoándạngcủalờigiải
 Sửdụngquynạptoánhọcđểtìmracáchằngvàchứngminh lờigiải
côngthứcđệquy Phư ng ơ phápthaythế    2  2   
Đoán   Ο󰇛log󰇜
Cầnchứngminh󰇛󰇜  log vớihằngsố  0 đượcchọn phùhợp CuuDuongThanCong.com
https://fb.com/tailieudientucntt 3 1/10/2011 Phư ng ơ phápthaythế Phư ng ơ phápthaythế
 Giảsử󰇛󰇜  log đúngvới   ⁄ tứclà
 Giảsửtrườnghợpcơsở 1  1 nhưng1log1  . 0  󰇛   ⁄ 󰇜     ⁄ log   ⁄ .Thayvào 
Kếtquảquynạpsaitrongtrườnghợpcơsở.  Tacóthể g
 iảiquyếtvấnđềnàykhisửdụngcáckýhiệu    2   ệ  ậ  ⁄ log   ⁄   ti m c n(Ο, Ω, Θ)  log 
   log với   
⁄    log  log2     log  Chọn v m
 saocho ới ọi   thìkếtquảluônđúng
VDvới  2 thì 2  2 1  2  4  2log2 với
hằngsố tachọnđủlớn(VD  5). Đúngvới  1
 Vậy   Ο󰇛log󰇜 với  5 và  2 Tacầnchỉ r
 akếtquảquynạpnàyđúngtrongmọitrường
hợp(đúngcảtrongtrườnghợpcơsở). Phư ng ơ phápthaythế Phư ng ơ phápthaythế
Đoándngligiitt:
 Tránhlỗihaymắc
 Thêmbớt1hằngsố k
 hônglàmthayđổidạngkếtquả
   2   2        Ο󰇛󰇜
   2   12  3 vẫncódạngΟ󰇛log󰇜
Saidotakhôngchứngminh󰇛󰇜    Thayđổibiến
 Banđầunớilỏngcậntrên,dướiđể giảmdần.  2   log
đặt  log tacó 2  2 2 " ⁄  
VD.Với󰇛󰇜 trongvídụbanđầutacóthể c
 họnΩ󰇛󰇜 và
đặt   󰇛2󰇜 tacó   2   ⁄   
Ο󰇛󰇜 rồisau ó
đ giảmgiớihạntrên,tănggiớihạndướicho
Ο log  Ο󰇛logloglog󰇜 tớikhihộitụ v
 ềgiátrịchínhxác CuuDuongThanCong.com
https://fb.com/tailieudientucntt 4 1/10/2011
Mtsốtínhchtcahàmmũ,loga,giaitha  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ứngminhrằ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ớiphươngphápthaythế 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, kKhin=1:
Chuyểnquinạp,n>1: ô T(n)=1 Theođ nh ị nghĩa. T(n)=4 T(n/2)+n (địnhnghĩa)
 4ô(cô(n/2)2 ‐ dô(n/2))+n (quinạp) 1 c‐d
Cóthểchọnc,dthíchhợpđểcóbấtđẳngthứcnà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ọndó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ápcâyđệquy Vậy, T(n) = O(n2). CuuDuongThanCong.com
https://fb.com/tailieudientucntt 6 1/10/2011 Phư ng ơ phápcâyđệquy Phư ng ơ phápcâyđệquy
 Xétcôngthứcđệquy         Ο󰇛󰇜  
 CâyđệquychomergeSort
 1     ế  1
   2        ế   1  Phư ng ơ phápcâyđệquy Phư ng ơ phápcâyđệquy
 Dùngphươngphápthaythếđểchứngminhlờigiảicông
thứcđệquytìmđược.
VD.         Ο   Ο󰇛log󰇜  
Bàitp:Xácđịnhmộtcậntrêntốtchocôngthứcđệquy
            
  log    log      3         
dùngphươngphápthếđểxácnhậnlạikếtquả.   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địnhlýthợ
 Dùngđểgiảicáccôngthứcđệquydạng 
        ,
đó  1,   1,   ààệậươ
mộtcáchhiệuquả.
 Bàitoánbanđầuđượcchiathành bàitoánconcókích
thướcmỗibàilà để ổ hợp bài   Địnhlýthợ  ⁄ ,chiphí t ng các toán con là󰇛󰇜 Mastertheorem
VD.Thuttoánspxếptrn
chiathành2bàitoáncon,kíchthước/2.Chiphítổnghợp2bài
toánconlàΟ󰇛󰇜 Dùngđịnhlýthợ Dùngđịnhlýthợ
Ápdngđịnhthợ:
Địnhthợ(MasterTheorem)
  1,   1 làcáchằngsố,󰇛󰇜 làmộthàm.󰇛󰇜 địnhnghĩađệ
    9   . 
quytrêncácthamsốkhôngâm
  9,   3à    tacó""" 
 ≡ """   .Đây      
⁄  󰇛󰇜,trongđó 
⁄ cóthểhiểulà   ⁄ hoặc
làtrườnghợp1(với  1)dođó   Θ󰇛󰇜  
⁄ .Thì󰇛󰇜 cóthểbị gi
 ớihạnmộtcáchtiệmcậnnhư s  au:
       1.   1 tacó"""/"    1.Đâylà
 Nếu   Ο󰇛"""  
󰇜,vớihằng  0 thì    Θ󰇛 󰇜
trườnghợp2,dođó   Θ󰇛log 󰇜
 Nếu   Ο󰇛""" 󰇜 thì   Θ󰇛""" log 󰇜
    3    log  
 Nếu   Ω󰇛"""  
󰇜,vớihằng  0,vànếu   
  3,   4 và    log  tacó"""   ≡ """   
⁄  󰇛󰇜 vớihằng  1 vàvớimọinđủ lớnthì  
   Θ󰇛󰇛󰇜󰇜
Ο󰇛.󰇜,   Ω󰇛"""  󰇜 với  0.2,   ⁄ 
  ≡ 3   󰇛 log 󰇜 với   dovậy     Θ󰇛 log󰇜 (TH3) 󰇛 g 󰇜 CuuDuongThanCong.com
https://fb.com/tailieudientucntt 8 1/10/2011 Dùngđịnhlýthợ
Chúý:Khôngphảitrườnghợpnàocũngápdụngđược địnhlýthợ!
 VD.   2    log  
  2,   2 và    log """ 
 ≡ """ "   dođócóvẻ á
 pdụngtrườnghợp3.
Tuynhiên    log  tiệmcậnlớnhơn2  với Đệquycónhớ 
mọihằngsố dođókhôngthể á  pdụngđược. Đệquycónhớ
 Trongthuậttoánđệquy,nhữngbàitoánconcóthểđược
giảiđigiảilạinhiềulần!
 VD.TínhsốFibonacci    
1           ế  0,1
   1     2  ế  2 Tính󰇛5󰇜
Ghinhnligii:dùngmng Thuậttoánquaylui
 Khigặpbàitoánconcầngiải:Kiểmtraxembàitoáncon Back‐trackingalgorithm
đãđượcgiảichưa:
 Nếuđãgiải:lấykếtquả
 Ngượclại,giảibàitoánconvàcậpnhậtlờigiảivàobảng CuuDuongThanCong.com
https://fb.com/tailieudientucntt 9 1/10/2011 Thuậttoánquaylui Thuậttoánquaylui
 Bàitoán8conhậu:“Hãyxếp8conhậutrênbàncờ 8  x8
Thuttoánxếphu:đặtlầnlượtcácquânhậulênbàncờ
saochochúngkhôngthểănlẫnnhau”
(theo1cáchnàođó)saochoquânhậuđặtsaukhôngăn
đượcquânđãđặttrướcđó.  Thuậttoánquaylui Thuậttoánquaylui
solve_from (Current_config)
 Deadend:trạngtháichưakếtthúc,nhưngtakhôngthể
ifCurrent_configđãchứađủ8hậu
đặtthêmđược1quânhậunàonữa. printCurrent_config
 Khirơivàotrạngtháideadendtaphảitiếnhànhquaylui else
(backtrack)lạilựachọngầnnhấtđểthửmộtkhảnăngcó
VớitậppcácôtrênbàncờmàchưabịảnhhưởngbởiCurrent_config thểkhác. {
Thêm1quânhậuvàop;
CậpnhậtlạiCurrent_config
solve_from(Current_config);
LoạibỏquânhậukhỏipcủaCurrent_config; } CuuDuongThanCong.com
https://fb.com/tailieudientucntt 10 1/10/2011 Thuậttoánquaylui Bàitoán8conhậu
Thuttoánquaylui– backtrackingalgorithm:
 Thửtìmkiếmlờigiảiđầyđủchobàitoántừviệcxâydựng  Nhậnxét: lờigiảibộ ph 
ận,trongđólờigiảibộ ph 
ậnphảiluônphù
 ộtphảicó1conhậu
hợpvớiyêucầubàitoán.  Mỗi c
 Conhậu1nằmtrêncột1
 Trongquátrìnhthựchiện,thuậttoánmở r
 ộngdầnlờigiải  …
bộphận.Nếuviệcmởrộngkhiếnlờigiảibộphậnviphạm
yêucầubàitoánthìtiếnhànhquaylui,loạibỏsửađổi
 Conhậujnằmtrêncộtj
gầnnhấtvàthửmộtkhảnăngxâydựnglờigiảibộphận  … cóthể (  hợplệ)khác.
 Conhậu8nằmtrêncột8
 Cácconhậuphảikhôngcùnghàng
 Cácconhậuphảikhôngnằmtrênđườngchéocủanhau Giảithuật ể   function Try(column){
Thử lần lượt từng vị trí hàng Ki mtra An toàn
for (row=1;row<=8;row++){
if ([row,column]làantoàn){
Đặtconhậuvàovị 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 Inkếtquả; else Đ Try(column+1);
Xóaconhậukhỏivị 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