SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HÓA
TRƯỜNG THPT TRIỆU SƠN 2

SÁNG KIẾN KINH NGHIỆM

GIẢI CÁC DẠNG BÀI TOÁN LIỆT KÊ BẰNG PHƯƠNG
PHÁP VÉT CẠN SỬ DỤNG THUẬT TOÁN QUAY LUI
TRONG ÔN LUYỆN HỌC SINH GIỎI MÔN TIN HỌC

Người thực hiện: Phạm Thị Biên
Chức vụ: Giáo viên
SKKN thuộc bộ môn: Tin học

THANH HÓA NĂM 2014


MỤC LỤC
A. ĐẶT VẤN ĐỀ............................................................................................3
I. Lý do chọn đề tài..........................................................................................3
II. Thực trạng của vấn đề.................................................................................3
III. Mục đích nghiên cứu.................................................................................4
IV. Đối tượng và phạm vi nghiên cứu.............................................................4
B. GIẢI QUYẾT VẤN ĐỀ............................................................................5
I. Cơ sở lý luận.................................................................................................5
II. Biện pháp giải quyết vấn đề........................................................................5
1. Một số khái niệm.........................................................................................5
2. Một số dạng bài toán liệt kê.........................................................................7
3. Một số bài toán tham khảo.........................................................................19
III. Kết quả thực nghiệm................................................................................19
C. KẾT LUẬN VÀ ĐỀ XUẤT....................................................................20
I. Kết luận.......................................................................................................20

vậy nên tôi chọn đề tài: “Giải các dạng các bài toán liệt kê bằng phương pháp
vét cạn sử dụng thuật toán quay lui trong ôn luyện học sinh giỏi môn Tin học”
II. THỰC TRẠNG CỦA VẤN ĐỀ
1. Thuận lợi
Do sự quan tâm và đầu tư của Bộ giáo dục và đào tạo nói chung và của trường
THPT Triệu Sơn 2 nói riêng, về cơ sở vật chất môn Tin học đã có 1 phòng thực
hành hoạt động tốt, ngoài ra còn có một số phòng máy chiếu projector hỗ trợ cho
giáo viên trong công tác giảng dạy.
Mặc dù môn Tin không phải là môn trọng điểm nhưng rất được Ban giám hiêu
quan tâm động viên và tạo mọi điều kiện trong công tác giảng dạy và ôn luyện đội
tuyển học sinh giỏi cũng như trong các công tác khác.
Trong quá trình thực hiện đề tài tôi đã được các giáo viên trong tổ bộ môn tư
vấn và hỗ trợ rất nhiều giúp tôi hoàn thành đề tài.
3


2. Khó khăn
Ngôn ngữ lập trình Pascal là một môn học mới, cách học cũng hoàn toàn mới,
vì vậy khi tiếp cận với môn học này đa số học sinh thấy rất bỡ ngỡ. Học các thao
tác sử dụng hay dùng phương pháp học thuộc lòng không còn phù hợp nữa. Lúc
này các em cần phải học cách tư duy logic, tìm thuật toán, và viết những dòng lệnh
trên máy tính chính xác đến từng đấu chấm, dấu phẩy.
Với tâm lí thông thường các em học sinh coi tin học là môn phụ không quan
trọng nên nhiều em chủ quan không dành đủ thời gian để học nên không hiểu bài
và dần bị mất căn bản. Đây cũng là lí do mà nhiều em bị điểm kém, thậm chí là thi
lại, học lại bộ môn tin học mặc dù có thể các em học rất giỏi các môn học khác.
Chính vì xem môn Tin là môn phụ nên khi lựa chọn đội tuyển ôn thi học sinh
giỏi giáo viên chúng tôi thường rất khó lựa chọn được những học sinh có năng
khiếu thực sự.
Các dạng bài toán liệt kê là những bài toán khó, nếu người học có tư duy chưa

những điều kiện nhất định và chỉ rõ những cấu hình tìm được thỏa mãn những điều
kiện trên.
Bài toán liệt kê gồm có 3 dạng: tổ hợp, chỉnh hợp lặp và chỉnh hợp không lặp.
Trong đó dạng bài toán chỉnh hợp không lặp thường hay xuất hiện nhiều nhất trong
các bài toán tin học
Sơ lược 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à số tự nhiên k. Gọi X là tập hợp
các số nguyên dương từ 1 đến k: X= {1, 2, …, k}
• Tổ hợp
Một tổ hợp chập k của n là một tập con k phần tử của tập n phần tử.
Chẳng hạn tập {1,2,3,4} có các tổ hợp chập 2 là: {1,2}, {1,3, {1,4}, {2,3},
{2,4}, {3,4}. Vì trong tập hợp các phần tử không phân biệt thứ tự nên tập {1,2}
cũng là tập {2,1} và do đó, ta coi chúng chỉ là một tổ hợp.
Vậy số tổ hợp chập k của S gồm n phần tử là:
• Chỉnh hợp lặp
Chỉnh hợp lặp chập k của n là một dãy k thành phần, mỗi thành phần là một
phần tử của tập n phần tử, có xét đến thứ tự và không yêu cầu các thành phần khác
nhau.
Số chỉnh hợp lặp chập k của n phần tử là nk
• Chỉnh hợp không lặp
Khác với chỉnh hợp lặp là các thành phần được phép lặp lại, tức là có thể
giống nhau, chỉnh hợp không lặp chập k của tập n phần tử cũng là một dãy k thành
phần lấy từ tập n phần tử có xét thứ tự nhưng các thành phần không được phép
giống nhau.
Chẳng hạn có n người, một cách chọn ra k người để xếp thành một hàng là
một chỉnh hợp không lặp chập k của n.
Số chỉnh hợp không lặp chập k của n phần tử là: n(n-1)(n-2)…(n-k+1)=

Để giải được bài toán liệt kê cần xác định được thuật toán tổng quan để trên cơ
sở đó xây dựng được tất cả các cầu hình liên quan.

Tìm mọi nghiệm (gọi là vét cạn) bằng cách tiến dần, tìm kiếm các khả năng có
thể chấp nhận được cho từng phần tử của một nghiệm và biết quay lui khi không
thể tiến được nữa. Khi mọi phần tử của một nghiệm đã được gán giá trị thì kết thúc
quá trình tìm một nghiệm, chuyển sang tìm nghiệm tiếp theo.
Do thuật toán quay lui xây dựng trên cơ sở tìm kiếm dần, kết quả sau hình
thành từ kết quả trước nên có thể sử dụng các hàm và các thủ tục đệ quy để thực
hiện.
Có thể so sánh các nghiệm tìm được để tìm nghiệm tối ưu.
1.3. Thuật toán quay lui
Mô hình giải thuật quay lui có thể mô tả như sau:
Procedure Try (i);
Begin
Vòng lặp đề của mọi khả năng của bước i
Begin
- Thử chọn một đề cử cho bước i
- Nếu đề cử này thỏa mãn điều kiện thì
6


Begin
+ Lưu trạng thái của bài toán
+ Xác nhận giá trị đề cử cho bước i
+ Xác nhận trạng thái mới của bài toán sau khi chấp nhận đề cử
+ Nếu là bước cuối cùng thì hiện nghiệm và tăng biến đếm nghiệm
Ngược lại thì Try(i+1)
+Trả lại trạng thái như trước khi chấp nhận đề cử
End;
End;
End;
Hoặc có thể viết dưới dạng sau:



X[i]:=a[j];
<ghi nhận trạng thái mới>;
If i=n then Update
Else Try(i+1);
<Trả lại trạng thái cũ>;
End;
End;
Procedure Search;
Begin
Try(1);
End;
Trên đây là các thuật toán vét cạn đối với bài toán tìm mọi cấu hình hay đếm
số cấu hình. Trong trường hợp bài toán cần tìm một cấu hình, tìm cấu hình tối ưu
thì thuật toán cũng tương tự, chỉ khác ở phần cập nhật (Update) khi sinh được một
cấu hình mới.
Chẳng hạn thủ tục Update đối với bài toán tìm nghiệm tối ưu:
procedure Update;
begin
If <f(x) tốt hơn f(best)> then best:=x;
end;
Ở đây chúng ta không xét việc áp dụng phương pháp vét cạn sử dụng đệ quy
quay lui dùng cho các bài toán đơn thuần mà tập trung vào các bài toán tìm cấu
hình tổ hợp, tối ưu tổ hợp
2. Một số dạng bài toán liệt kê (cấu hình tổ hợp)
Bài toán tổ hợp yêu cầu tìm các đối tượng x có dạng là một vector thỏa mãn
các điều kiện sau:
1. x gồm k phần tử: x=(x1,x2,…,xn)
2. Mỗi phần tử xi có thể nhận một trong tập các đối tượng a1,a2,…,an,

khi xét i=1 (x[0] là lính canh)
Về cấu trúc dữ liệu ta chỉ cần một mảng x để biểu diễn tổ hợp. Ràng buộc đối
với giá trị x[i] là: x[i−1]< x[i] ≤ n−k+i.
*Chương trình
Program Tohop;
uses crt;
const
max = 20;
input='TOHOP.INP';
output='TOHOP.OUT' ;
var n,k : integer;
x : array[0..max] of integer;
f1,f2:text;
procedure readfile;
var f:text;
begin
clrscr;
assign(f1,INPUT);reset(f1);
assign(f2,OUTPUT);rewrite(f2);
readln(f1,n,k);
end;
procedure print;
var i : integer;

9


f: text;
begin
for i := 1 to k do write(f2,x[i]);

Thuật toán sinh chỉnh hợp lặp như sau:
procedure Try(i);
var j;
begin
for j := 1 to n do
begin
10


x[i] := j;
if i=k then Print(x)
else Try(i+1);
end;
end;
Ví dụ 1: Liệt kê dãy nhị phân độ dài n (n nguyên dương)
*Phân tích
Một ví dụ dễ thấy nhất của chỉnh hợp lặp là các dãy nhị phân. Một dãy nhị
phân độ dài m là một chỉnh hợp lặp chập m của tập 2 phần tử {0,1}. Ví dụ dãy nhị
phân độ dài n=3 gồm 8 số: 101, 000, 001, 010, 011, 100, 110, 111. Vì có xét thứ tự
nên dãy 101 và dãy 011 là 2 dãy khác nhau.
*Chương trình
Program Nhiphan;
uses crt;
const max = 20;
input=’nhiphan.inp’;
output=’nhiphan.out’;
var
n : integer;
x : array[1..max] of integer;
f1,f2: text;

Readfile;
try(1);
close(f1); close(f2);
END.
Cây tìm kiếm quay lui liệt kê dãy nhị phân độ dài n = 3:

Ví dụ 2: Biểu thức Zero:
Cho số tự nhiên N (N≤ 9). Giữa các số 1, 2,…, N hãy chèn thêm vào các dấu
cộng (+) và trừ (-) sao cho được biểu thức có giá trị bằng 0. Hãy viết chương trình
tìm tất cả các khả năng có thể.
*Phân tích
Với bài toán này chúng ta sẽ dùng một mảng d[j] (j=1..2)chứa dấu cộng và trừ,
một mảng x[i] (i=2..n) chứa các phép toán tương ứng được chèn vào giữa các số 1,
2,…, N. Vậy nghiệm bài toán được mô tả như sau:
1. X là một vector, x=(x2,x3,…,xn)
2. xi nhận các giá trị trong tập {d1,d2}
3. Không có ràng buộc giữa các giá trị
*Chương trình
Program Bieuthuc_Zero;
const
d:array[1..2] of char=('+','-');
input='zero.inp';
output='zero.out';
12


var s:integer;
x:array[1..100] of char;
n, dem:integer;
f1,f2:text;

try(i+1);
case j of
1: s:=s-i ;
2: s:=s+i;
end;
end;
13


end;
BEGIN
Init;
try(2);
if dem=0 then writeln(f2,'Khong bieu thuc nao thoa man');
close(f1); close(f2);
END.
2.3. Chỉnh hợp không lặp
Nghiệm của bài toán tìm các chỉnh hợp không lặp chập k của tập n số nguyên
từ 1 đến n là các vector x thoả mãn các điều kiện:
1. x có k thành phần: x = (x1,x2,…xk)
2. Các giá trị xi lấy trong tập {1,2,..n}
3. Ràng buộc: các giá trị xi đôi một khác nhau, tức là xi≠xj với mọi i≠j.
Chỉnh hợp không lặp yêu cầu các phần tử phải khác nhau. Để đảm bảo điều
đó, ngoài mảng x, ta sẽ dùng thêm một cấu trúc dữ liệu nữa là mảng d để đánh dấu.
Khi một giá trị được chọn, ta đánh dấu giá trị đó, và khi chọn, ta chỉ chọn các giá
trị chưa đánh dấu. Mảng d sẽ là "trạng thái" của thuật toán. Bạn đọc xem phần giả
mã dưới đây để thấy rõ hơn ý tưởng đó.
procedure Try(i);
var j;
begin

assign(f2,output); rewrite(f2);
readln(f1,n);
writeln(f2,'Cac hoan vi cua day ',n ,' so:');
end;
procedure print;
var
i : integer;
begin
for i := 1 to n do write(f2,x[i]);
writeln(f2);
end;
procedure try(i:integer);
var
j : integer;
begin
for j := 1 to n do
if d[j] = 0 then
begin
x[i] := j; d[j] := 1;
if i = n then Print else try(i+1);
d[j] := 0;
end;
end;
BEGIN
readfile;
try(1);
close(f1); close(f2);
END.

15


2

Try(3)

Try(3)

1

2

3

132

213

2

1

231

312

Try(3)
1

321


Ta có thể viết riêng một hàm Ok để kiểm tra các ràng buộc đó. Nhưng giải
pháp tốt hơn là dùng thêm các mảng đánh dấu để mô tả rằng một đường chéo chính
và phụ đã có một con hậu khống chế. Tức là khi ta đặc con hậu i ở vị trí (i,j), ta sẽ
đánh dấu đường chéo chính i-j và đường chéo phụ i+j.
Như vậy về cấu trúc dữ liệu, ta dùng 4 mảng:
- Mảng x với ý nghĩa: x[i] là cột ta sẽ đặt con hậu thứ i.
- Mảng cot với ý nghĩa: cot[j]=true nếu cột j đã có một con hậu được đặt,
ngược lại thì cot[j]=false
- Mảng dcc với ý nghĩa: dcc[k]=true nếu đường chéo chính thứ k đã có một
con hậu được đặt, tức là ta đã đặt một con hậu tại vị trí (i,j) mà i−j=k; ngược lại thì
dcc[k]=false.
- Tương tự ta dùng mảng dcp với ý nghĩa: dcp[k]=true nếu đường chéo phụ
thứ k đã có một con hậu được đặt.
* Chương trình
Program Queens;
const
InputFile = 'QUEENS.INP';
OutputFile = 'QUEENS.OUT';
max = 100;
var
n: Integer;
x: array[1..max] of Integer;
cot: array[1..max] of Boolean;
dcp: array[2..2 * max] of Boolean;
dcc: array[1 - max..max - 1] of Boolean;
f1,f2: Text;
procedure Init;
begin
Assign(f1, InputFile); Reset(f1);
Assign(f2, OutputFile); Rewrite(f2);

Try(1);
Close(f1); Close(f2);
END.
Ví dụ 3. Tìm đường đi ngắn nhất:
Có n thành phố, a[i,j] là chi phí để di chuyển từ thành phố i đến thành phố j.
(Nếu không có đường đi thì a[i,j] = 0). Một người muốn đi du lịch qua tất cả các
thành phố, mỗi thành phố một lần rồi trở về nơi xuất phát sao cho tổng chi phí là
nhỏ nhất. Hãy xác định một đường đi như vậy.
*Phân tích
Phương án tối ưu của bài toán cũng là một vector x, trong đó xi là thành phố sẽ
đến thăm tại lần di chuyển thứ i. Các điều kiện của x như sau:
1. x = (x1,x2,…xn)
2. xi lấy giá trị trong tập {1,2,…n}
3. Ràng buộc: xi ≠ xj với mọi i≠j và a[xi,xi+1]>0 với mọi i=1,2,..n, coi xn+1=x1.
n

∑ a[ x , x
i

i +1

] → min

f(x) =
Trong đó:
- mảng x[i]: ghi lại hành trình
i =1

18


a[j, i] := a[i, j] ;
end;
Close(f);
end;
procedure Init;
begin
FillChar(D, n, false);
d[1] := False;
X[1] := 1;
Min:= maxint;
end;
19


procedure Print;
var
i: Integer;
f: Text;
begin
Assign(f, Output); Rewrite(f);
for i := 1 to n do Write(f, Best[i], '->');
WriteLn(f, 1);
WriteLn(f, 'Hanh trinh ngan nhat: ', Min);
Close(f);
end;
procedure update;
var s,i:integer;
begin
s:=a[x[n],1];
for i:=1 to n-1 do s:=s+a[x[i],x[i+1]];

Bi 1. Cho hỡnh vuụng kớch thc NX N (2 N 5). Hóy in cỏc ch cỏi
A,B,C,D vo cỏc ụ sao cho trờn mi dũng cng nh mi ct mi ch cỏi ch xut
hin mt ln. Hi cú bao nhiờu cỏch xp
Bi 2. Bi toỏn mó i tun: Cho bn c kớch thc NxN. Ta mi ụ ca
bn c l (x,y) vi x l s hiu dũng, y l s hiu ct. Mt quõn mó ang ụ (x, y),
hóy tỡm mt ng i ca quõn mó sao cho quõn mó i qua tt c cỏc ụ trờn bn c,
mi ụ ch i qua ỳng mt ln.
Bi 3. Cho N qu cõn cú cỏc khi lng tng ng l q1, q2,,qn (nguyờn)
v mt cỏi cõn 2 a. Khi cõn cú th t mt s qu cõn v vt cn cõn trờn a no
cựng c sao cho cõn thng bng. Cho vt cú khi lng M, hi cú th cõn nú
bng nhng qu cõn no?
Bi 4. Cú M loi tin cú giỏ tr ln lt l L1, L2,, Lm (nguyờn dng) vi
s t mi loi l s1,s2,sm (nguyờn dng). Hóy tỡm cỏch i t tin cú mnh giỏ
X thnh cỏc loi tin cú trong kho
Bi 5. Bi toỏn cỏi tỳi: Mt nh thỏm him cn em theo mt cỏi tỳi cú trng
lng khụng quỏ b. Cú n vt cn em theo. vt th j cú trng lng l aj v
giỏ tr s dng l cj (j = 1, 2, 3, ..,n). Hi rng nh thỏm him cn em theo cỏc
vt no cho tng giỏ tr s dng ca cỏc vt em theo l ln nht?
Bi 6. Một từ đợc gọi là chân chính loại M, N nếu nó đợc xây dựng từ tập hợp
gồm M ký tự, có độ dài N và không có 2 từ con nào liên tiếp giống nhau.
Giả sử tập M={'1', '2', '3'}
Ví dụ: 1232; 2123; 1231 là những từ chân chính loại 3,4; còn 1123;1212;1233
là những từ không phải là từ chân chính loại 3,4
III. KT QU THC NGHIM
Sau khi ỏp dng ti trong quỏ trỡnh ụn thi i tuyn, bng hỡnh thc giỏm
sỏt, ra kim tra kt hp thc hnh tụi ó thu c nhng kt qu sau:
Ni du n g cn n m bt
S lng
Hiu c kin thc va hc
6/6

II. ĐỀ XUẤT, KIẾN NGHỊ
*Đối với cấp trường
- Cần lắp đặt 2 đến 3 phòng máy chiếu cố định để giáo viên chủ động hơn
trong công tác giảng dạy,
- Các máy tính trong phòng thực hành hiện nay đã cũ, cấu hình thấp và thường
hay hư hỏng, cần nâng cấp và đầu tư thêm số lượng máy để học sinh thực hành tôt
hơn
*Đối với cấp sở
- Cần tổ chức thêm một số cuộc thi thuộc lĩnh vực tin học, ví dụ như cuộc thi
Tin học trẻ, Tin học và nhà trường, Thi soạn thảo văn bản,… để tạo cơ hội cho các
em học sinh phát triển khả năng tin học.
- Cần quan tâm và đầu tư thêm cơ sở vật chất cho bộ môn tin học như máy
chiếu đa năng, phòng thực hành,…
- Cần tăng thêm số lượng đi thi học sinh giỏi tỉnh nhằm mục đích mở rộng tìm
kiếm, khai thác các tài năng tin học trẻ

22


TÀI LIỆU THAM KHẢO
1.
2.
3.
4.

Gi ải t huật và l ập t rì nh( ebook) , t ác gi ả Lê M i nh Hoàng,
ĐH sư phạm Hà Nội
Phươ ng pháp gi ải bài t oán t rong t i n học, t ác gi ả Th.s
T rần Đức Huyên, NX B Gi áo dục
Em t ập l ập t rì nh 2, tác gi ả Trần Đỗ Hùng, NXB Gi áo