Bài toán lit kê
Lê Minh Hoàng
{ 1z
MC LC
§
0. GI
I THIU
...................................................................................................................................... 2
§
1. NH
C LI MT S KIN THC I S T HP
....................................................................... 3
I. CH
NH HP LP
...........................................................................................................................................3
II. CH
NH HP KHÔNG LP
...........................................................................................................................3
III. HOÁN V

......................................................................................................................................................3
IV. T
 HP
.........................................................................................................................................................3
§
2. PH
NG PHÁP SINH (GENERATE)
............................................................................................ 5
I. SINH CÁC DÃY NH

.............................................................................................................. 22
I. BÀI TOÁN T
I U
......................................................................................................................................22
II. S
 BÙNG N T HP
...............................................................................................................................22
III. MÔ HÌNH K
 THUT NHÁNH CN
.....................................................................................................22
IV. BÀI TOÁN NG
I DU LCH
...................................................................................................................23
V. DÃY ABC ....................................................................................................................................................25
Bài toán lit kê
Lê Minh Hoàng
{ 2z
§
0. GII THIU
Trong thc t, có mt s bài toán yêu cu ch rõ: trong mt tp các đi tng cho trc có bao
nhiêu đi tng tho mãn nhng điu kin nht đnh. Bài toán đó gi là bài toán đm cu hình t
hp.
Trong lp các bài toán đm, có nhng bài toán còn yêu cu ch rõ nhng cu hình tìm đc tho
mãn điu kin đã cho là nhng cu hình nào. Bài toán yêu cu đa ra danh sách các cu hình có th
có gi là bài toán lit kê t hp.
 gii bài toán lit kê, cn phi xác đnh đc mt thut toán đ có th theo đó ln lt xây dng
đc tt c các cu hình đang quan tâm. Có nhiu phng pháp lit kê, nhng chúng cn phi đáp
ng đc hai yêu cu di đây:
• Không đc lp li mt cu hình
• Không đc b sót mt cu hình

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:
k
k
n
nA =
II. 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 123
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:
)!kn(
!n
)1kn)...(2n)(1n(nA
k
n
−
=+−−−=
III. HOÁN V
Khi k = n. Mt chnh hp không lp chp n ca S đc gi là mt hoán v các phn t ca S.
Ví d: mt hoán v: (A, D, C, E, B, F) ca S = {A, B, C, D, E, F}
i123456
f(i) A D C E B F
 ý rng khi k = n thì s phn t ca tp X = {1, 2, .., n} đúng bng s phn t ca S. Do tính cht
đôi mt khác nhau nên dãy f(1), f(2), ..., f(n) s lit kê đc ht các phn t trong S. Nh vy f là
toàn ánh. Mt khác do gi thit f là chnh hp không lp nên f là đn ánh. Ta có tng ng 1-1 gia
các phn t ca X và S, do đó f là song ánh. Vy nên ta có th đnh ngha mt hoán v ca S là mt

1
n
0
n
2)11(C...CC
=+=+++
Bài toán lit kê
Lê Minh Hoàng
{ 5z
§
2. PHNG PHÁP SINH (GENERATE)
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:
1. 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 xác
đnh đc cu hình đu tiên và cu hình cui cùng trong th t đã xác đnh
2. Xây dng đc thut toán 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>;
until <ht cu hình>;
Th t t đin
Trên các kiu d liu đn gin chun, ngi ta thng nói ti khái nim th t. Ví d trên kiu s
thì có quan h: 1 < 2; 2 < 3; 3 < 10; ..., trên kiu ký t Char thì cng có quan h 'A' < 'B'; 'C' < 'c'...
Xét quan h th t toàn phn "nh hn hoc bng" ký hiu "≤" trên mt tp hp S, là quan h hai
ngôi tho mãn bn tính cht:
Vi ∀a, b, c ∈ S
• Tính ph bin: Hoc là a ≤ b, hoc b ≤ a;

• Hoc a
i
= b
i
vi ∀i: 1 ≤ i ≤ n.
• Hoc tn ti mt s nguyên dng k: 1 ≤ k < n đ:
a
1
= b
1
a
2
= b
2
...
a
k-1
= b
k-1
a
k
= b
k
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

-1.
Ví d: Khi n = 3, các dãy nh phân đ dài 3 đc lit kê nh sau:
p(x)01234567
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 = (x
1
, x
2
, ...,
x
n
) là dãy đang có và không phi dãy cui cùng thì dãy k tip s nhn đc bng cách cng thêm 1
( theo c s 2 có nh) vào dãy hin ti.
Ví d khi n = 8:
Dãy đang có:
10010000 Dãy đang có: 10010111
cng thêm 1: + 1 cng thêm 1: + 1
 
Dãy mi: 10010001 Dãy mi: 10011000
Nh vy k thut sinh cu hình k tip t cu hình hin ti có th mô t nh sau: Xét t cui
dãy v đu (xét t hàng đn v lên), gp s 0 đu tiên thì thay nó bng s 1 và đt tt c các phn
t phía sau v trí đó bng 0.
i := n;
while (i > 0) and (x
i
= 1) do i := i - 1;
if i > 0 then
begin
x
i

ReadLn(n);
FillChar(x, SizeOf(x), 0);
{C
u hình ban đu x
1
= x
2
= ... = x
n
:= 0}
repeat
{Thu
t toán sinh}
for i := 1 to n do Write(x[i]);
{In ra c
u hình hin ti}
WriteLn;
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}
begin
x[i] := 1;
{Thay x
i

< x
2
< ... < x
k
thì gii hn trên (giá tr ln nht có
th nhn) ca x
k
là n, ca x
k-1
là n - 1, ca x
k-2
là n - 2...
C th: gii hn trên ca x
i
= n - k + i;
Còn tt nhiên, gii hn di ca x
i
(giá tr nh nht x
i
có th nhn) là x
i-1
+ 1.
Nh vy nu ta đang có mt dãy x đi din cho mt tp con, nu x là cu hình kt thúc có ngha là
tt c các phn t trong x đu đã đt ti gii hn trên thì quá trình sinh kt thúc, nu không thì ta
phi sinh ra mt dãy x mi tng dn tho mãn va đ ln hn dãy c theo ngha không có mt tp
con k phn t nào chen gia chúng khi sp th t t đin.
Ví d: n = 9, k = 6. Cu hình đang có x = {1, 2, 6, 7, 8, 9}. Các phn t x
3
đn x
6

• 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:
Bài toán lit kê
Lê Minh Hoàng
{ 8z
• 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.
i := n;
while (i > 0) and (x

{1, 3, 4}
{1, 3, 5}
{1, 4, 5}
{2, 3, 4}
{2, 3, 5}
{2, 4, 5}
{3, 4, 5}
PROG02_2.PAS * Thut toán sinh lit kê các tp con k phn t
program Combinations;
const
max = 30;
var
x: array[1..max] of Integer;
n, k, i, j: Integer;
begin
{nh ngha li thit b nhp/xut chun}
Assign(Input, 'SUBSET.INP'); Reset(Input);
Assign(Output, 'SUBSET.OUT'); Rewrite(Output);
ReadLn(n, k);
for i := 1 to k do x[i] := i;
{x
1
:= 1; x
2
:= 2; ... ; x
3
:= k (C
u hình khi to)}
Count := 0;
{Bi

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(Input); Close(Output);
end.
Bài toán lit kê
Lê Minh Hoàng
{ 9z
III. 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.
Gi s hoán v hin ti là x = (3, 2, 6, 5, 4, 1), xét 4 phn t cui cùng, ta thy chúng đc xp gim
dn, điu đó có ngha là cho dù ta có hoán v 4 phn t này th nào, ta cng đc mt hoán v bé
hn hoán v hin ti!. Nh vy ta phi xét đn x
2
= 2, thay nó bng mt giá tr khác. Ta s thay bng
giá tr nào?, không th là 1 bi nu vy s đc hoán v nh hn, không th là 3 vì đã có x
1
= 3 ri
(phn t sau không đc chn vào nhng giá tr mà phn t trc đã chn). Còn li các giá tr 4, 5,

2
thì ta s đc x
2
= 4 và đon cui vn đc sp xp gim dn. Khi đó mun biu din nh nht cho các giá tr
trong đon cui thì ta ch cn đo ngc đon cui.
Trong trng hp hoán v hin ti là (2, 1, 3, 4) thì hoán v k tip s là (2, 1, 4, 3). Ta cng có th
coi hoán v (2, 1, 3, 4) có đon cui gim dn, đon cui này ch gm 1 phn t (4)
Vy k thut sinh hoán v k tip t hoán v hin ti có th xây dng nh sau:
• Xác đnh đon cui gim dn dài nht, tìm ch s i ca phn t x
i
đng lin trc đon cui đó.
iu này đng ngha vi vic tìm t v trí sát cui dãy lên đu, gp ch s i đu tiên tha mãn x
i
< x
i+1
. Nu toàn dãy đã là gim dn, thì đó là cu hình cui.
i := n - 1;
while (i > 0) and (x
i
> x
i+1
) do i := i - 1;
• Trong đon cui gim dn, tìm phn t x
k
nh nht tho mãn điu kin x
k
> x
i
. Do đon cui
gim dn, điu này thc hin bng cách tìm t cui dãy lên đu gp ch s k đu tiên tho mãn

Lê Minh Hoàng
{ 10z
PROG02_3.PAS * Thut toán sinh lit kê hoán v
program Permute;
const
max = 12;
var
n, i, k, a, b: Integer;
x: array[1..max] of Integer;
procedure Swap(var X, Y: Integer);
{Th
 tc đo giá tr hai tham bin X, Y}
var
Temp: Integer;
begin
Temp := X; X := Y; Y := Temp;
end;
begin
Assign(Input, 'PERMUTE.INP'); Reset(Input);
Assign(Output, 'PERMUTE.OUT'); Rewrite(Output);
ReadLn(n);
for i := 1 to n do x[i] := i;―
{Kh
i to cu hình đu: x
1
:= 1; x
2
:= 2; ..., x
n
:= n}

t ngc đon cui gim dn, a: đu đon, b: cui đon}
―― while a < b do
begin
Swap(x[a], x[b]); {i ch x
a
và x
b
}
Inc(a);
{Ti
n a và lùi b, đi ch tip cho ti khi a, b chm nhau}
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(Input); Close(Output);
end.
Bài tp:
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 đó.
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}.
Gi ý: thay h c s 2 bng h c s n.
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 tp:
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

Bài toán lit kê
Lê Minh Hoàng
{ 12z
§
3. THUT TOÁN QUAY LUI
Thut toán quay lui dùng đ gii bài toán lit kê các cu hình. Mi cu hình đc xây dng
bng cách xây dng tng phn t, mi phn t đc chn bng cách th tt c các kh nng.
Gi thit cu hình cn lit kê có dng (x
1
, x
2
,..., x
n
). Khi đó thut toán quay lui thc hin qua các
bc sau:
1) Xét tt c các giá tr x
1
có th nhn, th cho x
1
nhn ln lt các giá tr đó. Vi mi giá tr th
gán cho x
1
ta s:
2) Xét tt c các giá tr x
2
có th nhn, li th cho x
2
nhn ln lt các giá tr đó. Vi mi giá tr
th gán cho x
2

3
, ..., x
n
).
Mô hình ca thut toán quay lui có th mô t nh sau:
{Th
 tc này th cho x
i
nh
n ln lt các giá tr mà nó có th nhn}
procedure Try(i: Integer);
begin
for (mi giá tr V có th gán cho x
i
) do
begin
<Th cho x
i
:= V>;
if (x
i
là phn t cui cùng trong cu hình) then
<Thông báo cu hình tìm đc>
else
begin
<Ghi nhn vic cho x
i
nhn giá tr V (Nu cn)>;
Try(i + 1);
{G

. Vi mi giá tr th gán cho x
i
li th các giá tr có th gán cho
x
i+1
.Chng trình lit kê bng thut toán quay lui có th vit:
PROG03_1.PAS * Thut toán quay lui lit kê các dãy nh phân đ dài n
program BinaryStrings;
const
max = 30;
var
x: array[1..max] of Integer;
n: Integer;
procedure PrintResult;
{In c
u hình tìm đc, do th tc tìm đ quy
Try g
i khi tìm ra mt cu hì nh}
var
i: Integer;
begin
for i := 1 to n do Write(x[i]);
WriteLn;
end;
procedure Try(i: Integer);
{Th
 các cách chn x
i
}
var

Try(1);
{Th
 các cách chn giá tr x
1
}
Close(Input);
Close(Output);
end.
Ví d: Khi n = 3, cây tìm kim quay lui nh sau:
Try(3)
Try(2)
Try(3) Try(3) Try(3)
Try(2)
Try(1)
x
1
:= 0
x
1
:= 1
x
2
:= 0
x
2
:= 1
x
2
:= 0
x

100
101
110
111
result
Hình 2: Cây tìm kim quay lui trong bài toán lit kê dãy nh phân
Bài toán lit kê
Lê Minh Hoàng
{ 14z
II. LIT KÊ CÁC TP CON K PHN T
Input/Output có khuôn dng nh trong PROG02_2.PAS
 lit kê các tp con k phn t ca tp S = {1, 2, ..., n} ta có th đa v lit kê các cu hình (x
1
, x
2
,
..., x
k
)  đây các x
i
∈ S và x
1
< x
2
< ... < x
k
. Ta có nhn xét:
• x
k
≤ n

k
thì ta có mt cu
hình cn lit kê. Chng trình lit kê bng thut toán quay lui nh sau:
PROG03_2.PAS * Thut toán quay lui lit kê các tp con k phn t
program Combinations;
const
max = 30;
var
x: array[0..max] of Integer;
n, k: Integer;
procedure PrintResult;
(*In ra t
p con {x
1
, x
2
, ..., x
k
}*)
var
i: Integer;
begin
Write('{');
for i := 1 to k - 1 do Write(x[i], ', ');
WriteLn(x[k], '}');
end;
procedure Try(i: Integer);
{Th
 các cách chn giá tr cho x[i]}
var

quay lui: mô hình cài đt có th thích hp cho nhiu bài toán, khác vi phng pháp sinh tun t,
vi mi bài toán li phi có mt thut toán sinh k tip riêng làm cho vic cài đt mi bài mt khác,
bên cnh đó, không phi thut toán sinh k tip nào cng d cài đt.
III. LIT KÊ CÁC CHNH HP KHÔNG LP CHP K
 lit kê các chnh hp không lp chp k ca tp S = {1, 2, ..., n} ta có th đa v lit kê các cu
hình (x
1
, x
2
, ..., x
k
)  đây các x
i
∈ S và khác nhau đôi mt.
Nh vy th tc Try(i) - xét tt c các kh nng chn x
i
- s th ht các giá tr t 1 đn n, mà các giá
tr này cha b các phn t đng trc chn. Mun xem các giá tr nào cha đc chn ta s dng
k thut dùng mng đánh du:
• Khi to mt mng c
1
, c
2
, ..., c
n
mang kiu logic.  đây c
i
cho bit giá tr i có còn t do hay đã
b chn ri. Ban đu khi to tt c các phn t mng c là TRUE có ngha là các phn t t 1
đn n đu t do.

1
có n cách chn, x
2
có n - 1 cách chn, ...Lu ý rng khi
th tc Try(i) có i = k thì ta không cn phi đánh du gì c vì tip theo ch có in kt qu ch
không cn phi chn thêm phn t nào na.
Input: file vn bn ARRANGES.INP cha hai s nguyên dng n, k (1 ≤ k ≤ n ≤ 20) cách nhau ít
nht mt du cách
Output: file vn bn ARRANGES.OUT ghi các chnh hp không lp chp k ca tp {1, 2, ..., n}
ARRANGES.INP ARRANGES.OUT
3 2 1 2
1 3
2 1
2 3
3 1
3 2
PROG03_3.PAS * Thut toán quay lui lit kê các chnh hp không lp chp k
program Arranges;
const
max = 20;
var
x: array[1..max] of Integer;
c: array[1..max] of Boolean;
n, k: Integer;
procedure PrintResult;
{Th
 tc in cu hình tìm đc}
Bài toán lit kê
Lê Minh Hoàng
{ 16z

, t
c là s không chn phi j}
―― c[j] := True;
{B
 đánh du: j li là t do, bi sp ti s th mt cách chn khác ca x
i
}
―――――――― end;
end;
end;
begin
Assign(Input, 'ARRANGES.INP'); Reset(Input);
Assign(Output, 'ARRANGES.OUT'); Rewrite(Output);
ReadLn(n, k);
FillChar(c, SizeOf(c), True);
{T
t c các s đu cha b chn}
Try(1);
{Th
 các cách chn giá tr ca x
1
}
Close(Input); Close(Output);
end.
Nhn xét: khi k = n thì đây là chng trình lit kê hoán v
IV. BÀI TOÁN PHÂN TÍCH S
Bài toán
Cho mt s nguyên dng n ≤ 30, hãy tìm tt c các cách phân tích s n thành tng ca các s
nguyên dng, các cách phân tích là hoán v ca nhau ch tính là 1 cách.
Cách làm:

)
5. Khi nào thì in kt qu và khi nào thì gi đ quy tìm tip ?
Lu ý rng t
i - 1
là tng ca tt c các phn t t x
1
đn x
i-1
do đó
• Khi t
i
= n tc là (x
i
= n - t
i - 1
) thì in kt qu
• Khi tìm tip, x
i+1
s phi ln hn hoc bng x
i
. Mt khác t
i+1
là tng ca các s t x
1
ti x
i+1
không đc vt quá n. Vy ta có t
i+1
≤ n ⇔ t
i-1

6. Vy th tc Try(i) th các giá tr cho x
i
có th mô t nh sau: (đ tng quát cho i = 1, ta đt x
0
=
1 và t
0
= 0).
• Xét các giá tr ca x
i
t x
i - 1
đn (n - t
i-1
) div 2, cp nht t
i
:= t
i - 1
+ x
i
và gi đ quy tìm tip.
• Cui cùng xét giá tr x
i
= n - t
i-1
và in kt qu t x
1
đn x
i
.

procedure PrintResult(k: Integer);
var
i: Integer;
begin
Write(n,' = ');
for i := 1 to k - 1 do Write(x[i], '+');
WriteLn(x[k]);
end;
procedure Try(i: Integer);
var
j: Integer;
begin
for j := x[i - 1] to (n - T[i - 1]) div 2 do
{Tr
ng hp còn chn tip x
i+1
}
begin
x[i] := j;
Bài toán lit kê
Lê Minh Hoàng
{ 18z
t[i] := t[i - 1] + j;
Try(i + 1);
end;
x[i] := n - T[i - 1];
{N
u x
i
là ph

vi mt hng s C: 1 - n ≤ C ≤ n - 1 xác đnh duy nht 1 đng chéo N-TB vì vy ta có th
đánh ch s cho các đng chéo N- TB t 1 - n đn n - 1.
Bài toán lit kê
Lê Minh Hoàng
{ 19z
12345678
1
2
3
4
5
6
7
N
S
EW
8
Hình 4: ng chéo B-TN mang ch s 10 và đng chéo N-TB mang ch s 0, ô chung (5, 5)
Cài đt:
1. Ta có 3 mng logic đ đánh du:
•
Mng a[1..n]. a
i
= TRUE nu nh ct i còn t do, a
i
= FALSE nu nh ct i đã b mt quân hu
khng ch
• Mng b[2..2n]. b
i
= TRUE nu nh đng chéo B-TN th i còn t do, b

i-j
:= FALSE) đ các ln gi đ quy tip sau chn cách đt
các quân hu k tip s không chn vào nhng ô nm trên ct j và nhng đng chéo này na.
•
Sau khi gi đ quy tìm cách đt quân hu th i + 1, có ngha là sp ti ta li th mt cách đt
khác cho quân hu th i, ta b đánh du ct và 2 đng chéo b quân hu va th đt khng ch
(a
j
= b
i+j
= c
i-j
:= TRUE) tc là ct và 2 đng chéo đó li thành t do, bi khi đã đt quân hu i
sang v trí khác ri thì ct và 2 đng chéo đó hoàn toàn có th gán cho mt quân hu khác
Hãy xem li trong các chng trình lit kê chnh hp không lp và hoán v v k thut đánh du. 
đây ch khác vi lit kê hoán v là: lit kê hoán v ch cn mt mng đánh du xem giá tr có t do
không, còn bài toán xp hu thì cn phi đánh du c 3 thành phn: Ct, đng chéo B-TN,
đng chéo N- TB. Trng hp đn gin hn: Yêu cu lit kê các cách đt n quân xe lên bàn c
nxn sao cho không quân nào n quân nào chính là bài toán lit kê hoán v
Input: file vn bn QUEENS.INP cha s nguyên dng n ≤ 12
Output: file vn bn QUEENS.OUT, mi dòng ghi mt cách đt n quân hu
Bài toán lit kê
Lê Minh Hoàng
{ 20z
QUEENS.INP QUEENS.OUT
5 (1, 1); (2, 3); (3, 5); (4, 2); (5, 4);
(1, 1); (2, 4); (3, 2); (4, 5); (5, 3);
(1, 2); (2, 4); (3, 1); (4, 3); (5, 5);
(1, 2); (2, 5); (3, 3); (4, 1); (5, 4);
(1, 3); (2, 1); (3, 4); (4, 2); (5, 5);

i: Integer;
begin
for i := 1 to n do Write('(', i, ', ', x[i], '); ');
WriteLn;
end;
procedure Try(i: Integer);
{Th
 các cách đt quân hu th i vào hàng i}
var
j: Integer;
begin
for j := 1 to n do
if a[j] and b[i + j] and c[i - j] then
{Ch
 xét nhng ct j mà ô (i, j)
ch
a
b
 khng ch}
――――――begin
x[i] := j;
{Th
 đt quân hu i vào ct j}
――――――――if i = n then PrintResult
else
begin
a[j] := False; b[i + j] := False; c[i - j] := False; {ánh du}
―― Try(i + 1);
{Tìm các cách
đt quân hu th i + 1}

1. Mt s chng trình trên x lý không tt trong trng hp tm thng (n = 0 hoc k = 0), hãy
khc phc các li đó
2. Vit chng trình lit kê các chnh hp lp chp k ca n phn t
3. Cho hai s nguyên dng l, n. Hãy lit kê các xâu nh phân đ dài n có tính cht, bt k hai xâu
con nào đ dài l lin nhau đu khác nhau.
4. Vi n = 5, k = 3, v cây tìm kim quay lui ca chng trình lit kê t hp chp k ca tp {1, 2, ...,
n}
5. Lit kê tt c các tp con ca tp S gm n s nguyên {S
1
, S
2
, ..., S
n
} nhp vào t bàn phím
6. Tng t nh bài 5 nhng ch lit kê các tp con có max - min ≤ T (T cho trc).
7. Mt dãy (x
1
, x
2
, ..., x
n
) gi là mt hoán v hoàn toàn ca tp {1, 2,..., n} nu nó là mt hoán v và
tho mãn x
i
≠ i vi ∀i: 1 ≤ i ≤ n. Hãy vit chng trình lit kê tt c các hoán v hoàn toàn ca tp
trên (n vào t bàn phím).
8. Sa li th tc in kt qu (PrintResult) trong bài xp hu đ có th v hình bàn c và các cách đt
hu ra màn hình.
9. Bài toán mã đi tun: Cho bàn c tng quát kích thc nxn và mt quân Mã, hãy ch ra mt hành
trình ca quân Mã xut phát t ô đang đng đi qua tt c các ô còn li ca bàn c, mi ô đúng 1 ln.

i
thì s phi tr giá rt ln v chi phí
thc thi thut toán bi quá trình tìm kim lòng vòng vô ngha trong các bc chn k tip x
i+1
, x
i+2
,
... Khi đó, mt vn đ đt ra là trong quá trình lit kê li gii ta cn tn dng nhng thông tin đã tìm
đc đ loi b sm nhng phng án chc chn không phi ti u. K thut đó gi là k thut
đánh giá nhánh cn trong tin trình quay lui.
III. MÔ HÌNH K THUT NHÁNH CN
Da trên mô hình thut toán quay lui, ta xây dng mô hình sau:
procedure Init;
begin
<Khi to mt cu hình bt k BESTCONFIG>;
end;
{Th tc này th chn cho x
i
tt c các giá tr nó có th nhn}
procedure Try(i: Integer);
begin
for (Mi giá tr V có th gán cho x
i
) do
begin
<Th cho x
i
:= V>;
if (Vic th trên vn còn hi vng tìm ra cu hình tt hn BESTCONFIG) then
if (x

không có hi vng tìm thy cu hình tt hn cu hình
BESTCONFIG thì th giá tr khác ngay mà không cn phi gi đ quy tìm tip hay ghi nhn kt
qu làm gì. Nghim ca bài toán s đc làm tt dn, bi khi tìm ra mt cu hình mi (tt hn
BESTCONFIG - tt nhiên), ta không in kt qu ngay mà s cp nht BESTCONFIG bng cu hình
mi va tìm đc
IV. BÀI TOÁN NGI DU LCH
Bài toán
Cho n thành ph đánh s t 1 đn n và m tuyn đng giao thông hai chiu gia chúng, mng li
giao thông này đc cho bi bng C cp nxn,  đây C
ij
= C
ji
= Chi phí đi đon đng trc tip t
thành ph i đn thành ph j. Gi thit rng C
ii
= 0 vi ∀i, C
ij
= +∞ nu không có đng trc tip t
thành ph i đn thành ph j.
Mt ngi du lch xut phát t thành ph 1, mun đi thm tt c các thành ph còn li mi thành
ph đúng 1 ln và cui cùng quay li thành ph 1. Hãy ch ra cho ngi đó hành trình vi chi phí ít
nht. Bài toán đó gi là bài toán ngi du lch hay bài toán hành trình ca mt thng gia
(Traveling Salesman)
Cách gii
1) Hành trình cn tìm có dng (x
1
= 1, x
2
, ..., x
n

1
). Tng quát: x
i
có th chn 1 trong các thành ph cha đi qua mà t x
i-1
có đng đi
trc tip ti.(1 ≤
i ≤ n)
3) Nhánh cn: Khi to cu hình BestConfig có chi phí = +∞. Vi mi bc th chn x
i
xem chi
phí đng đi cho ti lúc đó có < Chi phí ca cu hình BestConfig?, nu không nh hn thì th
giá tr khác ngay bi có đi tip cng ch tn thêm. Khi th đc mt giá tr x
n
ta kim tra xem x
n
có đng đi trc tip v 1 không ? Nu có đánh giá chi phí đi t thành ph 1 đn thành ph x
n
cng vi chi phí t x
n
đi trc tip v 1, nu nh hn chi phí ca đng đi BestConfig thì cp
nht li BestConfig bng cách đi mi.
4) Sau th tc tìm kim quay lui mà chi phí ca BestConfig vn bng +∞ thì có ngha là nó không
tìm thy mt hành trình nào tho mãn điu kin đ bài đ cp nht BestConfig, bài toán không
có li gii, còn nu chi phí ca BestConfig < +∞ thì in ra cu hình BestConfig - đó là hành trình
ít tn kém nht tìm đc
Input: file vn bn TOURISM.INP
• Dòng 1: Cha s thành ph n (1 ≤ n ≤ 20) và s tuyn đng m trong mng li giao thông
• m dòng tip theo, mi dòng ghi s hiu hai thành ph có đng đi trc tip và chi phí đi trên
quãng đng đó (chi phí này là s nguyên dng ≤ 100)