L
L
Ê
ÊM
M
I
I
N
N
H
HHOÀ
HOÀ
N
N
G
G



Albert Einstein

 i 

MC LC
PHN 1. BÀI TOÁN LIT KÊ 1
§1. NHC LI MT S KIN THC I S T HP 2
1.1. CHNH HP LP 2
1.2. CHNH HP KHÔNG LP 2
1.3. HOÁN V 2
1.4. T HP 3
§2. PHNG PHÁP SINH (GENERATION) 4
2.1. SINH CÁC DÃY NH PHÂN  DÀI N 5
2.2. LIT KÊ CÁC TP CON K PHN T 6
2.3. LIT KÊ CÁC HOÁN V 8
§3. THUT TOÁN QUAY LUI 12
3.1. LIT KÊ CÁC DÃY NH PHÂN  DÀI N 12
3.2. LIT KÊ CÁC TP CON K PHN T 13
3.3. LIT KÊ CÁC CHNH HP KHÔNG LP CHP K 15
3.4. BÀI TOÁN PHÂN TÍCH S 17
3.5. BÀI TOÁN XP HU 19
§4. K THUT NHÁNH CN 24
4.1. BÀI TOÁN TI U 24
4.2. S BÙNG N T HP 24
4.3. MÔ HÌNH K THUT NHÁNH CN 24
4.4. BÀI TOÁN NGI DU LCH 25
4.5. DÃY ABC 27
PHN 2. CU TRÚC D LIU VÀ GII THUT 33
§1. CÁC BC C BN KHI TIN HÀNH GII CÁC BÀI TOÁN TIN HC 34
1.1. XÁC NH BÀI TOÁN 34

6.6. CÂY TNG QUÁT 77
§7. KÝ PHÁP TIN T, TRUNG T VÀ HU T 79
7.1. BIU THC DI DNG CÂY NH PHÂN 79
7.2. CÁC KÝ PHÁP CHO CÙNG MT BIU THC 79
7.3. CÁCH TÍNH GIÁ TR BIU THC 79
7.4. CHUYN T DNG TRUNG T SANG DNG HU T 83
7.5. XÂY DNG CÂY NH PHÂN BIU DIN BIU THC 86
§8. SP XP (SORTING) 88
8.1. BÀI TOÁN SP XP 88
8.2. THUT TOÁN SP XP KIU CHN (SELECTIONSORT) 90
8.3. THUT TOÁN SP XP NI BT (BUBBLESORT) 91
8.4. THUT TOÁN SP XP KIU CHÈN (INSERTIONSORT) 91
8.5. SP XP CHÈN VI  DÀI BC GIM DN (SHELLSORT) 93
8.6. THUT TOÁN SP XP KIU PHÂN ON (QUICKSORT) 94
8.7. THUT TOÁN SP XP KIU VUN NG (HEAPSORT) 101
8.8. SP XP BNG PHÉP M PHÂN PHI (DISTRIBUTION COUNTING) 104
8.9. TÍNH N NH CA THUT TOÁN SP XP (STABILITY) 105
8.10. THUT TOÁN SP XP BNG C S (RADIX SORT) 106
8.11. THUT TOÁN SP XP TRN (MERGESORT) 111
8.12. CÀI T 114
8.13. ÁNH GIÁ, NHN XÉT 122
§9. TÌM KIM (SEARCHING) 126
9.1. BÀI TOÁN TÌM KIM 126
9.2. TÌM KIM TUN T (SEQUENTIAL SEARCH) 126
9.3. TÌM KIM NH PHÂN (BINARY SEARCH) 126
9.4. CÂY NH PHÂN TÌM KIM (BINARY SEARCH TREE - BST) 127
 iii 

9.5. PHÉP BM (HASH) 132
9.6. KHOÁ S VI BÀI TOÁN TÌM KIM 132

3.2. THUT TOÁN TÌM KIM THEO CHIU SÂU (DEPTH FIRST SEARCH) 187
3.3. THUT TOÁN TÌM KIM THEO CHIU RNG (BREADTH FIRST SEARCH) 189
3.4.  PHC TP TÍNH TOÁN CA BFS VÀ DFS 192
§4. TÍNH LIÊN THÔNG CA  TH 193
4.1. NH NGHA 193
4.2. TÍNH LIÊN THÔNG TRONG  TH VÔ HNG 194
 iv 

4.3.  TH Y  VÀ THUT TOÁN WARSHALL 194
4.4. CÁC THÀNH PHN LIÊN THÔNG MNH 197
§5. VÀI NG DNG CA DFS và BFS 208
5.1. XÂY DNG CÂY KHUNG CA  TH 208
5.2. TP CÁC CHU TRÌNH C S CA  TH 211
5.3. BÀI TOÁN NH CHIU  TH 211
5.4. LIT KÊ CÁC KHP VÀ CU CA  TH 215
§6. CHU TRÌNH EULER, NG I EULER,  TH EULER 219
6.1. BÀI TOÁN 7 CÁI CU 219
6.2. NH NGHA 219
6.3. NH LÝ 219
6.4. THUT TOÁN FLEURY TÌM CHU TRÌNH EULER 220
6.5. CÀI T 221
6.6. THUT TOÁN TT HN 223
§7. CHU TRÌNH HAMILTON, NG I HAMILTON,  TH HAMILTON 226
7.1. NH NGHA 226
7.2. NH LÝ 226
7.3. CÀI T 227
§8. BÀI TOÁN NG I NGN NHT 231
8.1.  TH CÓ TRNG S 231
8.2. BÀI TOÁN NG I NGN NHT 231
8.3. TRNG HP  TH KHÔNG CÓ CHU TRÌNH ÂM - THUT TOÁN FORD BELLMAN 233

13.1. CÁC KHÁI NIM 307
13.2. THUT TOÁN EDMONDS (1965) 308
13.3. THUT TOÁN LAWLER (1973) 310
13.4. CÀI T 312
13.5.  PHC TP TÍNH TOÁN 316
TÀI LIU C THÊM 319  vi 

HÌNH V
Hình 1: Cây tìm kim quay lui trong bài toán lit kê dãy nh phân 13
Hình 2: Xp 8 quân hu trên bàn c 8x8 19
Hình 3: ng chéo B-TN mang ch s 10 và đng chéo N-TB mang ch s 0 20
Hình 4: Lu đ thut gii (Flowchart) 36
Hình 5: Ký pháp Θ ln, Ο ln và Ω ln 41
Hình 6: Tháp Hà Ni 54
Hình 7: Cu trúc nút ca danh sách ni đn 59
Hình 8: Danh sách ni đn 59
Hình 9: Cu trúc nút ca danh sách ni kép 61
Hình 10: Danh sách ni kép 61
Hình 11: Danh sách ni vòng mt hng 61
Hình 12: Danh sách ni vòng hai hng 62
Hình 13: Dùng danh sách vòng mô t Queue 67
Hình 14: Di chuyn toa tàu 69
Hình 15: Di chuyn toa tàu (2) 69
Hình 16: Cây 70
Hình 17: Mc ca các nút trên cây 71
Hình 18: Cây biu din biu thc 71
Hình 19: Các dng cây nh phân suy bin 72

Hình 43: ánh s các bit 133
Hình 44: Cây tìm kim s hc 133
Hình 45: Cây tìm kim c s 136
Hình 46: Vi đ dài dãy bit z = 3, cây tìm kim c s gm các khoá 2, 4, 5 và sau khi thêm giá tr 7 137
Hình 47: RST cha các khoá 2, 4, 5, 7 và RST sau khi loi b giá tr 7 138
Hình 48: Cây tìm kim c s a) và Trie tìm kim c s b) 140
Hình 49: Hàm đ quy tính s Fibonacci 151
Hình 50: Tính toán và truy vt 154
Hình 51: Truy vt 163
Hình 52: Ví d v mô hình đ th 178
Hình 53: Phân loi đ th 179
Hình 54 182
Hình 55 183
Hình 56:  th và đng đi 186
Hình 57: Cây DFS 189
Hình 58: Cây BFS 192
Hình 59:  th G và các thành phn liên thông G1, G2, G3 ca nó 193
Hình 60: Khp và cu 193
Hình 61: Liên thông mnh và liên thông yu 194
Hình 62:  th đy đ 195
Hình 63: n đ th vô hng và bao đóng ca nó 195
Hình 64: Ba dng cung ngoài cây DFS 199
Hình 65: Thut toán Tarjan “b” cây DFS 201
Hình 66: ánh s li, đo chiu các cung và duyt BFS vi cách chn các đnh xut phát ngc li vi th t
duyt xong (th t 11, 10… 3, 2, 1) 206
Hình 67:  th G và mt s ví d cây khung T1, T2, T3 ca nó 210
Hình 68: Cây khung DFS (a) và cây khung BFS (b) (Mi tên ch chiu đi thm các đnh) 210
Hình 69: Phép đnh chiu DFS 213
Hình 70: Phép đánh s và ghi nhn cung ngc lên cao nht 215
Hình 71: Mô hình đ th ca bài toán by cái cu 219

Hình 89: Cây pha “mc” ln hn sau mi ln xoay trng s cnh và tìm đng 302
Hình 90:  th G và mt b ghép M 307
Hình 91: Phép chp Blossom 309
Hình 92: N Blossom đ dò đng xuyên qua Blossom 309

 ix 

CHNG TRÌNH
P_1_02_1.PAS * Thut toán sinh lit kê các dãy nh phân đ dài n 6
P_1_02_2.PAS * Thut toán sinh lit kê các tp con k phn t 8
P_1_02_3.PAS * Thut toán sinh lit kê hoán v 9
P_1_03_1.PAS * Thut toán quay lui lit kê các dãy nh phân đ dài n 12
P_1_03_2.PAS * Thut toán quay lui lit kê các tp con k phn t 14
P_1_03_3.PAS * Thut toán quay lui lit kê các chnh hp không lp chp k 16
P_1_03_4.PAS * Thut toán quay lui lit kê các cách phân tích s 18
P_1_03_5.PAS * Thut toán quay lui gii bài toán xp hu 21
P_1_04_1.PAS * K thut nhánh cn dùng cho bài toán ngi du lch 26
P_1_04_2.PAS * Dãy ABC 28
P_2_07_1.PAS * Tính giá tr biu thc RPN 81
P_2_07_2.PAS * Chuyn biu thc trung t sang dng RPN 84
P_2_08_1.PAS * Các thut toán sp xp 114
P_3_01_1.PAS * m s cách phân tích s n 145
P_3_01_2.PAS * m s cách phân tích s n 146
P_3_01_3.PAS * m s cách phân tích s n 146
P_3_01_4.PAS * m s cách phân tích s n 147
P_3_01_5.PAS * m s cách phân tích s n dùng đ quy 147
P_3_01_6.PAS * m s cách phân tích s n dùng đ quy 148
P_3_03_1.PAS * Tìm dãy con đn điu tng dài nht 154
P_3_03_2.PAS * Ci tin thut toán tìm dãy con đn điu tng dài nht 156
P_3_03_3.PAS * Bài toán cái túi 159
BNG CÁC KÝ HIU C S DNG

x
⎢⎥
⎣⎦

Floor of x: S nguyên ln nht ≤ x
x
⎡⎤
⎢⎥

Ceiling of x: S nguyên nh nht ≥ x
nk
P
S chnh hp không lp chp k ca n phn t =
n!
(n k)!−

n
k
⎛⎞
⎜⎟
⎝⎠

Binomial coefficient: H s ca hng t
k
x trong đa thc
()

b
a
ab↑↑
m
a

a
b
copies of a
a
a
log x
Logarithm to base a of x: Logarithm c s a ca x (
b
a
log a b
=
)
lg x

Logarithm nh phân (c s 2) ca x
ln x
Logarithm t nhiên (c s e) ca x
*
a
log x S ln ly logarithm c s a đ thu đc s ≤ 1 t x (
*
a
log (a b) b↑↑ = )
*

À
À
I
IT
T
O
O
Á
Á
N
NL
L
I
I


T
TK
K
Ê
Ê

NHC LI MT S KIN THC I S T HP
Cho S là mt tp hu hn gm n phn t và k là mt s t nhiên.
Gi X là tp các s nguyên dng t 1 đn k: X = {1, 2, …, k}
1.1.

CHNH HP LP
Mi ánh x f: X → S. Cho tng ng vi mi i ∈ X, mt và ch mt phn t f(i) ∈ S.
c gi là mt chnh hp lp chp k ca S.
Nhng do X là tp hu hn (k phn t) nên ánh x f có th xác đnh qua bng các giá tr f(1),
f(2), …, f(k).
Ví d: S = {A, B, C, D, E, F}; k = 3. Mt ánh x f có th cho nh sau:
i 1 2 3
f(i) E C E
Vy có th đng nht f vi dãy giá tr (f(1), f(2), …, f(k)) và coi dãy giá tr này cng là mt
chnh hp lp chp k ca S. Nh ví d trên (E, C, E) là mt chnh hp lp chp 3 ca S. D
dàng chng minh đc kt qu sau bng quy np hoc bng phng pháp đánh giá kh nng
la chn:
S chnh hp lp chp k ca tp gm n phn t là
k
n
1.2.

CHNH HP KHÔNG LP
Khi f là đn ánh có ngha là vi ∀i, j ∈ X ta có f(i) = f(j) ⇔ i = j. Nói mt cách d hiu, khi
dãy giá tr f(1), f(2), …, f(k) gm các phn t thuc S khác nhau đôi mt thì f đc gi là mt
chnh hp không lp chp k ca S. Ví d mt chnh hp không lp (C, A, E):
i 1 2 3
f(i) C A E
S chnh hp không lp chp k ca tp gm n phn t là:
nk

đc tính k! ln. Vy s t hp chp k ca tp gm n phn t là
n
n!
k
k!(n k)!
⎛⎞
=
⎜⎟
−
⎝⎠

 4  Chuyên đ

HSPHN 1999-2004
§2.

PHNG PHÁP SINH (GENERATION)
Phng pháp sinh có th áp dng đ gii bài toán lit kê t hp đt ra nu nh hai điu kin
sau tho mãn:
 Có th xác đnh đc mt th t trên tp các cu hình t hp cn lit kê. T đó có th bit
đccu hình đu tiên và cu hình cui cùng trong th t đó.
 Xây dng đc thut toán t mt cu hình cha phi cu hình cui, sinh ra đc cu hình
k tip nó.
Phng pháp sinh có th mô t nh sau:
〈Xây dng cu hình đu tiên〉;
repeat
〈
a ra cu hình đang có〉;
〈
T cu hình đang có sinh ra cu hình k tip nu còn〉;

a[k+1] < b[k+1]
Trong trng hp này, ta có th vit a < b.
Th t đó gi là th t t đin trên các dãy đ dài n.
Khi đ dài hai dãy a và b không bng nhau, ngi ta cng xác đnh đc th t t đin. Bng
cách thêm vào cui dãy a hoc dãy b nhng phn t đc bit gi là phn t ∅ đ đ dài ca a
và b bng nhau, và coi nhng phn t ∅ này nh hn tt c các phn t khác, ta li đa v xác
đnh th t t đin ca hai dãy cùng đ dài. Ví d:
〈1, 2, 3, 4〉 < 〈5, 6〉
〈a, b, c〉 < 〈a, b, c, d〉
'calculator' < 'computer'
2.1.

SINH CÁC DÃY NH PHÂN  DÀI N
Mt dãy nh phân đ dài n là mt dãy x[1 n] trong đó x[i] ∈ {0, 1} (∀i : 1 ≤ i ≤ n).
D thy: mt dãy nh phân x đ dài n là biu din nh phân ca mt giá tr nguyên p(x) nào đó
nm trong đon [0, 2
n
- 1]. S các dãy nh phân đ dài n = s các s t nhiên ∈ [0, 2
n
- 1] = 2
n
.
Ta s lp chng trình lit kê các dãy nh phân theo th t t đin có ngha là s lit kê ln
lt các dãy nh phân biu din các s nguyên theo th t 0, 1, …, 2
n
-1.
Ví d: Khi n = 3, các dãy nh phân đ dài 3 đc lit kê nh sau:
p(x) 0 1 2 3 4 5 6 7
x 000 001 010 011 100 101 110 111
Nh vy dãy đu tiên s là 00…0 và dãy cui cùng s là 11…1. Nhn xét rng nu dãy x =

110
111

P_1_02_1.PAS * Thut toán sinh lit kê các dãy nh phân đ dài n
{$MODE DELPHI} (*This program uses 32-bit Integer [-2
31
2
31
- 1]*)
program Binary_Strings;
const
InputFile = 'BSTR.INP';
OutputFile = 'BSTR.OUT';
max = 100;
var
x: array[1 max] of Integer;
n, i: Integer;
f: Text;
begin
Assign(f, InputFile); Reset(f);
ReadLn(f, n);
Close(f);
Assign(f, OutputFile); Rewrite(f);
FillChar(x, SizeOf(x), 0); {Cu hình ban đu x=00 0}
repeat {Thut toán sinh}
for i := 1 to n do Write(f, x[i]); {In ra cu hình hin ti}
WriteLn(f);
i := n; {x[i] là phn t cui dãy, lùi dn i cho ti khi gp s 0 hoc khi i = 0 thì dng}
while (i > 0) and (x[i] = 1) do Dec(i);
if i > 0 then {Cha gp phi cu hình 11…1}

gii hn trên nên đ sinh cu hình mi ta không th sinh bng cách tng mt phn t trong s
các x[6], x[5], x[4], x[3] lên đc, ta phi tng x[2] = 2 lên thành x[2] = 3. c cu hình mi
là x = 〈1, 3, 6, 7, 8, 9〉. Cu hình này đã tho mãn ln hn cu hình trc nhng cha tho
mãn tính cht va đ ln mun vy ta li thay x[3], x[4], x[5], x[6] bng các gii hn di
ca nó. Tc là:
x[3] := x[2] + 1 = 4
x[4] := x[3] + 1 = 5
x[5] := x[4] + 1 = 6
x[6] := x[5] + 1 = 7
Ta đc cu hình mi x = 〈1, 3, 4, 5, 6, 7
〉 là cu hình k tip. Nu mun tìm tip, ta li nhn
thy rng x[6] = 7 cha đt gii hn trên, nh vy ch cn tng x[6] lên 1 là đc x = 〈1, 3, 4,
5, 6, 8〉.
Vy k thut sinh tp con k tip t tp đã có x có th xây dng nh sau:
Tìm t cui dãy lên đu cho ti khi gp mt phn t x[i] cha đt gii hn trên n - k + i.
 Nu tìm thy:
Tng x[i] đó lên 1.
t tt c các phn t phía sau x[i] bng gii hn di.
 Nu không tìm thy tc là mi phn t đã đt gii hn trên, đây là cu hình cui cùng
Input: file vn bn SUBSET.INP cha hai s nguyên dng n, k (1 ≤ k ≤ n ≤ 100) cách nhau
ít nht mt du cách
Output: file vn bn SUBSET.OUT các tp con k phn t ca tp {1, 2, …, n}
SUBSET.INP
5 3

SUBSET.OUT
{1, 2, 3}
{1, 2, 4}
{1, 2, 5}
{1, 3, 4}

for i := 1 to k do x[i] := i; {Khi to x := (1, 2, …, k)}
repeat
{In ra cu hình hin ti}
Write(f, '{');
for i := 1 to k - 1 do Write(f, x[i], ', ');
WriteLn(f, x[k], '}');
{Sinh tip}
i := k; {Xét t cui dãy lên tìm x[i] cha đt gii hn trên n - k + i}
while (i > 0) and (x[i] = n - k + i) do Dec(i);
if i > 0 then {Nu cha lùi đn 0 có ngha là cha phi cu hình kt thúc}
begin
Inc(x[i]); {Tng x[i] lên 1, t các phn t đng sau x[i] bng gii hn di ca nó}
for j := i + 1 to k do x[j] := x[j - 1] + 1;
end;
until i = 0; {Lùi đn tn 0 có ngha là tt c các ph
n t đã đt gii hn trên - ht cu hình}
Close(f);
end.
2.3.

LIT KÊ CÁC HOÁN V
Ta s lp chng trình lit kê các hoán v ca {1, 2, …, n} theo th t t đin.
Ví d vi n = 4, ta phi lit kê đ 24 hoán v:
1.1234 2.1243 3.1324 4.1342 5.1423 6.1432
7.2134 8.2143 9.2314 10.2341 11.2413 12.2431
13.3124 14.3142 15.3214 16.3241 17.3412 18.3421
19.4123 20.4132 21.4213 22.4231 23.4312 24.4321
Nh vy hoán v đu tiên s là 〈1, 2, …, n〉. Hoán v cui cùng là 〈n, n-1, …, 1〉.
Hoán v s sinh ra phi ln hn hoán v hin ti, hn th na phi là hoán v va đ ln hn
hoán v hin ti theo ngha không th có mt hoán v nào khác chen gia chúng khi sp th t.

Input: file vn bn PERMUTE.INP cha s nguyên dng n ≤ 100
Output: file vn bn PERMUTE.OUT các hoán v ca dãy (1, 2, …, n)
PERMUTE.INP
3

PERMUTE.OUT
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

P_1_02_3.PAS * Thut toán sinh lit kê hoán v
{$MODE DELPHI} (*This program uses 32-bit Integer [-2
31
2
31
- 1]*)
program Permutation;
const
InputFile = 'PERMUTE.INP';
OutputFile = 'PERMUTE.OUT';
max = 100;
var
n, i, k, a, b: Integer;
x: array[1 max] of Integer;
f: Text;

procedure Swap(var X, Y: Integer); {Th tc đo giá tr hai tham bin X, Y}

Dec(b);
end;
end;
until i = 0; {Toàn dãy là dãy gim dn - không sinh tip đc - ht cu hình}
Close(f);
end.
Bài tp:
Bài 1
Các chng trình trên x lý không tt trong trng hp tm thng, đó là trng hp n = 0
đi vi chng trình lit kê dãy nh phân cng nh trong chng trình lit kê hoán v, trng
hp k = 0 đi vi chng trình lit kê t hp, hãy khc phc điu đó.
Bài 2
Lit kê các dãy nh phân đ dài n có th coi là lit kê các chnh hp lp chp n ca tp 2 phn
t {0, 1}. Hãy lp chng trình:
Nhp vào hai s n và k, lit kê các chnh hp lp chp k ca {0, 1, …, n -1}.
Hng dn: thay h c s 2 bng h c s n.
Bài 3
Hãy lit kê các dãy nh phân đ dài n mà trong đó cm ch s “01” xut hin đúng 2 ln.
Bài 4.
Nhp vào mt danh sách n tên ngi. Lit kê tt c các cách chn ra đúng k ngi trong s n
ngi đó.
Bài 5
Lit kê tt c các tp con ca tp {1, 2, …, n}. Có th dùng phng pháp lit kê tp con nh
trên hoc dùng phng pháp lit kê tt c các dãy nh phân. Mi s 1 trong dãy nh phân
tng ng vi mt phn t đc chn trong tp. Ví d vi tp {1, 2, 3, 4} thì dãy nh phân
Bài toán lit kê  11 

Lê Minh Hoàng
1010 s tng ng vi tp con {1, 3}. Hãy lp chng trình in ra tt c các tp con ca {1,
2, …, n} theo hai phng pháp.