Sáng kiến kinh nghiệm Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi tỉnh khối 12

 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
1
Phần I: MỞ ĐẦU 
1. Lý do chọn đề tài: 
Ngôn ngữ lập trình Pascal là một nội dung được đưa vào chương trình học 
của bậc THPT và cũng là một nội dung được áp dụng cho các kỳ thi chọn học 
sinh giỏi tỉnh, học sinh giỏi quốc gia bộ môn tin học. Chính vì vậy cần nghiên 
cứu sâu về các giải thuật để hướng dẫn cho các học sinh ôn tập một cách tốt nhất 
cho các kỳ thi là một trong những mục tiêu cần đạt được của người giáo viên. 
Trong các kỳ thi tuyển học sinh giỏi tỉnh khối 12 hầu hết trong các đề thi 
đều có các bài toán cần sử dụng giải thuật đệ loang để giải quyết vấn đề. Đó là 
một dạng bài toán có ứng dụng khá phổ biến. Vậy nên, đã có rất nhiều tài liệu 
viết về nội dung này. Tuy nhiên, theo quan điểm, cách nhìn nhận của tôi việc 
phân tích các bài toán trong đó còn khá trừu tượng khiến người đọc khó hình 
dung, khó để hiểu và khó viết chương trình. 
Hiện nay, tại trường tôi việc hiểu và sử dụng giải thuật loang còn nhiều hạn chế, 
không những số học sinh tham gia bồi dưỡng hiểu và sử dụng được còn rất ít mà 
cả giáo viên tham gia bồi dưỡng cũng còn nhiều lúng túng khi giảng dạy phần 
nội dung này. Tôi cũng là một giáo viên tham gia bồi dưỡng học sinh giỏi, tôi 
nhận thấy cần nghiêm túc nghiên cứu nội dung này để đưa ra cách trình bày, 
cách phân tích mới giúp người đọc dễ hiểu, dễ biết và dễ viết chương trình. Để 
tạo điều kiện thuận lợi trong quá trình bồi dưỡng và qua quá trình bỗi dưỡng tôi 
đã đúc rút được một số kinh nghiệm về việc trình bày, phân tích bài toán, ứng 
dụng các giải thuật loang và cài đặt một số bài toán trong các đề thi học sinh giỏi 
khối 12 những năm gần đây. Với mong muốn người đọc dễ dàng tiếp cận được 
vấn đề . Vì vậy tôi chọn đề tài “Ứng dụng thuật toán loang trong việc giải 
quyết một số bài toán cho học sinh giỏi tỉnh khối 12” 
để nghiên cứu. Hy vọng đề tài trở thành một tài liệu quý cho học sinh tham 
gia bồi dưỡng và cũng là tài liệu đáng tham khảo cho quý thầy cô trong quá trình 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
2
tham gia bồi dưỡng đội tuyển học sinh giỏi tỉnh để có thể góp phần đưa về cho 
đội tuyển của mình những thành tích cao nhất. 
2. Mục đích nghiên cứu: 
Việc “Tìm hiểu về thuật toán loang” nhằm giúp tôi hiểu rõ hơn, sâu sắc hơn 
về giải thuật loang, các bài toán ứng dụng của giải thuật và cách viết các chương 
trình bằng phương pháp loang từ đó nâng cao khả năng nghiên cứu khoa học, 
khả năng tự học, tự bồi dưỡng, khả năng nhận biết, suy đoán và khả năng lập 
trình của bản thân. Qua đó tạo nên một tài liệu hỗ trợ học tập cho học sinh và 
nâng cao kiến thức chuyên môn cho giáo viên. 
3. Đối tượng nghiên cứu: 
Tôi được phân công bồi dưỡng học sinh giỏi của trường nên đối tượng 
nghiên cứu của tôi là học sinh các lớp chọn của khối. học sinh được chọn bồi 
dưỡng học sinh giỏi của trường đối với bộ môn tin học. 
4. Phạm vi nghiên cứu: 
Để nghiên cứu đề tài này, phạm vi nghiên cứu là ‘‘lý thuyết về loang và các 
ứng dụng của thuật toán loang để giải quyết các bài toán trong tin học bằng ngôn 
ngữ lập trình Pascal’’. 
5. Giả thuyết khoa học: 
Lý thuyết về loang, các ứng dụng của thuật toán loang thực sự đóng một vai 
trò quan trọng trong việc giúp học sinh định hướng, tìm ra phương pháp giải các 
bài toán ứng dụng về thuật toán loang trong các đề thi học sinh giỏi cấp tỉnh, cấp 
quốc gia. Bước đầu giúp học sinh nhận dạng, phân tích và giải quyết các bài 
toán liên quan một cách hiệu quả hơn. 
6. Nhiệm vụ nghiên cứu: 
Nghiên cứu về cơ sở lí luận 
Nghiên cứu về khái niệm, thuật toán và một số bài toán ứng dụng. 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
3
Nghiên cứu về cú pháp, câu lệnh trong ngôn ngữ lập trình Pascal để cài đặt 
một số bài toán về loang. 
7. Phương pháp nghiên cứu: 
Sử dụng phương pháp nghiên cứu lý thuyết, phương pháp tìm kiếm, thu 
thập thông tin, tổng hợp, phân tích và so sánh, thiết kế và cài đặt chương trình. 
8. Đóng góp mới của đề tài: 
Về mặt khoa học: Đề tài sẽ trình bày một cách logic các khái niệm từ đơn 
giản đến trừu tượng, giới thiệu, phân tích các bài tập cơ bản giúp hiểu rõ bản 
chất của vấn đề, từ đó vận dụng để giải quyết các bài toán phức tạp. 
Về mặt thực tiễn: Đề tài trình bày tương đối đầy đủ về khái niệm, các ví 
dụ của bài toán loang – phân tích ưu điểm của việc sử dụng thuật toán loang. các 
bài tập khá đa dạng giúp cho người đọc nắm bắt và hiểu rõ về ưu điểm của thuật 
toán, cách viết và sử dụng loang trong lập trình Pascal để giải quyết các bài toán. 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
4
Phần II: GIẢI QUYẾT VẤN ĐỀ 
1. Cơ sở lí luận: 
Trong tin học tìm kiếm là phương pháp phổ biến để giải quyết một bài toán. 
Và trong tìm kiếm có nhiều phương pháp tìm kiếm. Tuy nhiên, khi tìm kiếm trên 
đồ thị thì ta có hai cách tìm kiếm đó là: Tìm kiếm theo chiều sâu hoặc tìm kiếm 
theo chiều rộng. Mỗi cách tìm có những ưu điểm riêng. Đối với tìm kiếm theo 
chiều sâu ta thường sử dụng giải thuật đệ quy. Giải thuật này tương đối dễ cài 
đặt, nhưng nó chỉ giải quyết được các bài toán trên bộ dữ liệu bé. Với những bài 
toán có bộ dữ liệu lớn thì tìm kiếm theo chiều rộng – cài đặt thuật toán loang 
giúp ta khắc phục được hạn chế trên này. 
1.1. Khái niệm về loang 
Thuật toán Loang thực chất là thuật toán tìm kiếm theo chiều rộng trên đồ 
thị (Breadth First Search). Để hiểu rõ bản chất của thuật toán này, ta xét bài toán 
“Thăm các đỉnh của một đồ thị” như sau: Cho một đồ thị vô hướng G = (V,E), N 
đỉnh và M cạnh (số hiệu của các đỉnh là 1, 2, ,N). Bây giờ ta đưa ra thứ tự 
duyệt các đỉnh của đồ thị đã cho theo thuật toán tìm kiếm theo chiều rộng; thứ tự 
duyệt có thể bắt đầu từ một đỉnh v nào đó. Tư tưởng của thuật toán là sử dụng 
cấu trúc dữ liệu kiểu hàng đợi (QUEUE - vào trước ra trước). Phần tử được nạp 
vào đầu tiên của QUEUE là đỉnh v. Sau đó cứ mỗi đỉnh p lấy ra khỏi QUEUE là 
ta thăm đỉnh đó đồng thời nạp vào QUEUE những đỉnh chung cạnh với p (chỉ 
nạp vào những đỉnh chưa xét đến). Quá trình trên được lặp đi lặp lại cho đến khi 
nào QUEUE rỗng thì dừng. 
1.2. Thuật toán loang 
Thuật toán tìm kiếm theo chiều rộng BFS là thuật toán tìm kiếm trong đồ 
thị bằng cách tìm kiếm dựa trên 2 thao tác chính là: cho trước một đỉnh của đồ 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
5
thị và thêm các đỉnh kề với nó vào danh sách chờ duyệt. Phương pháp cài đặt 
này là “lập lịch” để duyệt các đỉnh theo thứ tự duyệt ưu tiên trên chiều rộng 
(đỉnh nào gần với đỉnh gốc sẽ được duyệt trước) 
Vì nguyên tắc trên (đỉnh nào gần gốc sẽ được duyệt trước) nên thuật toán 
tìm kiếm theo chiều rộng BFS thường được dùng để tìm đường đi ngắn nhất 
giữa các đỉnh. 
Chúng ta sẽ xây dựng một danh sách chứa các đỉnh đang chờ duyệt, tại mỗi 
bước chúng ta thăm đỉnh ở đầu danh sách và thêm những đỉnh kề với nó chưa có 
trong danh sách chờ vào cuối danh sách. 
Vì nguyên tắc đó nên chúng ta có thể tổ chức danh sách chờ đó bằng cấu 
trúc dữ liệu hàng đợi (Queue). 
Ban đầu tất cả các đỉnh i (i = 1..n) đều đặt cờ chuaxet[i] = True. Nếu đỉnh nào 
xét rồi ta đặt cờ của đỉnh đó sang trạng thái False. 
 Procedure BFS(v); Tìm kiếm theo chiều rộng bắt đầu từ đỉnh v 
 Begin 
 QUEUE = ; {Khởi tạo QUEUE ban đầu là rỗng} 
 QUEUE <= v; {Nạp đỉnh v vào QUEUE} 
 Chuaxet[v]:=False;{Đỉnh v nạp vào QUEUE là đã xét rồi => cờ của v là 
False} 
 While QUEUE ≠ do 
 Begin 
 P <= QUEUE; {Lấy p từ QUEUE} 
 Thăm đỉnh p; 
 For u € Ke(p) do {Những đỉnh u chung cạnh với đỉnh p} 
 If Chuaxet(u) then {Nếu đỉnh u chưa xét đến} 
 Begin 
 QUEUE <= u; {Nạp u vào QUEUE} 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
6
 Chuaxet[u]:=False; {Đỉnh u đã xét rồi =>cờ của u là False } 
 End; 
 End; 
 End; 
BEGIN {Chương trình chính} 
 For v € V do Chuaxet[v]:=True; 
 For v € V do 
 If Chuaxet[v] then BFS(v); 
END. 
Người ta thường dùng dữ liệu kiểu mảng để biểu diễn cấu trúc dữ liệu kiểu hàng 
đợi QUEUE và sử dụng 2 biến Dau và Cuoi để điều khiển việc nạp vào và lấy 
phần tử ra (biến Dau điều khiển thao tác lấy ra, biến Cuoi điều khiển thao tác 
nạp vào). 
Với bài toán trên ta sử dụng mảng 1 chiều Q: Array[1..N] of Byte để biểu diễn 
QUEUE. Khi đó thao tác nạp vào và lấy ra được thực hiện như sau: 
FillChar(Q,SizeOf(Q),0); {Khởi tạo tất cả các phần tử của Q có giá trị 0} 
Dau:=1; 
Cuoi:=1; 
Q[cuoi]:=v; {Ban đầu nạp đỉnh v vào Q} 
Để nạp thêm đỉnh u nào đó vào Q ta thực hiện: 
Cuoi:=Cuoi+1; {Hoặc dùng lệnh Inc(Cuoi)} 
Q[Cuoi]:=u; 
Để lấy một đỉnh p nào đó ra khỏi Q ta thực hiện: 
P:=Q[Dau]; 
Inc(Dau); 
2. Phân tích, cài đặt một số bài toán trong đề học sinh giỏi khối 12 
Bài toán 1:Tần số phát sóng 
Tóm tắt: 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
7
- Cho MxN ô vuông. Mỗi ô vuông chứa tần số A hoặc B. Từ vị trí này có thể di 
chuyển qua vị trí kia nếu hai ô nằm trong vùng ô vuông có chung cạnh. 
- Cho MxN ô vuông, mỗi ô vuông chứa tần số A hoặc B. Từ vị trí này có 
thể di chuyển qua vị trí kia nếu hai ô nằm trong vùng ô vuông có chung cạnh. 
Kiểm tra xem tọa độ hai điểm có liên thông hay không? 
Phân tích: 
Yêu cầu thực chất của bài toán là kiểm tra xem từ ô [x1;y1] đến ô [x2;y2] có 
liên thông với nhau hay không. 
 Ta dễ nhận thấy để biết được hai ô có liên thông với nhau được hay không 
ta dùng thuật toán loang là dễ nhất. Ta bắt dầu “loang” từ ô [x1,y1], nếu “loang” 
đến được ô [x2,y2] thì liên thông, ngược lại không liên thông. 
Hàng đợi phục vụ “loang” được thể hiện bởi mảng 2 chiều 
Q:Array[1..2,Mmax*NMax] of Byte; hàng thứ 1 của Q để lưu thông tin chỉ số 
hàng, hàng thứ 2 lưu thông tin của chỉ số cột của các ô khi nạp vào Q. 
Mảng A lưu thông tin tần số phát sóng tại 1 ô vuông. 
Ban đầu k:=A[x1;y1] 
Mảng B dùng để đánh dấu những ô đã “loang” đến; khi ô [i,j] được “loang” 
đến thì B[i,j] được gán giá trị là True. Điều kiện để loang đến được ô [x,y] là 
A[x,y] =k và B[x,y]= false 
Sau khi thực hiện xong việc “loang”, nếu B[x2,y2] = True thì điều đó có nghĩa 
là từ ô [x1,y1] liên thông đến ô [x2,y2] ngược lại là không liên thông. 
Đoạn Code chính của chương trình. 
While not eof(f) do 
 Begin 
 Fillchar(b,sizeof(b),fales); 
 Readln(f,x1,y1,x2,y2); 
K:= A[x1;y1]; 
B[x1;y1]:=true; 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
8
Dau:=1; 
Cuoi:=1; 
Q[1;dau]:=x1; 
Q[2;dau]:=y1; 
While (dau<=cuoi) do 
 Begin 
 I:= q[1;dau]; 
 J:=q[2;dau]; 
 Dau:=dau+1; 
 If (ix2) or (jy2) then 
 Begin 
 For r:=1 to 4 do 
 Begin 
 X:= i+hang[r]; 
 Y:= j+cot[r]; 
 If (a[x;y]=k) and (not B[x;y]) then 
 Begin 
 Cuoi:=cuoi+1; 
 Q[1;cuoi]:=x; 
 Q[2;cuoi]:=y; 
B[x;y]:=true; 
If B[x2,y2] then break; 
 End; 
End; 
End; 
End; 
If not B[x2,y2] then writeln(g,0) else writeln(1); 
End; 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
9
Bài toán 2: Nông trại 
Tóm tắt: 
- Cho MxN ô vuông. Mỗi ô chứa một kí tự: kí tự “.” là ô trống, kí tự ‘#’ là hàng rào, kí tự 
“c” là gà, kí tự “f” là cáo. Một miền được gọi là liên thông nếu không đi qua ô có rào 
chắn. Cần đưa ra số gà và số cáo của trại biết rằng: Trong mỗi miền liên thông, nếu số gà 
lớn hơn số cáo thì số cáo bằng 0 ngược lại số gà bằng 0. 
Phân tích: Yêu cầu thực chất của bài toán là kiểm tra xem trong mỗi miền liên 
thông sau một đêm còn lại bao nhiêu gà, bao nhiêu cáo. 
 Ta dễ nhận thấy để xác định miền liên thông ta dùng thuật toán loang là 
thuận tiện nhất. Khi xét đến ô (x,y) nếu A[x,y]= “.” Thì đẩy vào hàng đợi, nếu 
A[x,y]= “c” tăng biến gà rồi đẩy vào hàng đợi, nếu A[x,y]= “f” tăng biến cáo và 
đẩy vào hàng đợi. lặp đi lặp lại cho đến khi hàng đợi rỗng. 
 Hàng đợi phục vụ “loang” được thể hiện bởi mảng 2 chiều 
Q:Array[1..2,Mmax*NMax] of Byte; hàng thứ 1 của Q để lưu thông tin chỉ số 
hàng, hàng thứ 2 lưu thông tin của chỉ số cột của các ô khi nạp vào Q. 
Mảng A lưu thông tin kí tự tại 1 ô vuông. 
Ban đầu k:=A[x1;y1] 
Mảng B dùng để đánh dấu những ô đã “loang” đến; khi ô [i,j] được “loang” 
đến thì B[i,j] được gán giá trị .là True. Điều kiện để loang đến được ô [x;y] là 
A[x;y] =k và B[x;y]= false 
Sau khi thực hiện xong việc “loang”, nếu B[x2,y2] = True thì điều đó có nghĩa 
là từ ô [x1;y1] liên thông đến ô [x2;y2] ngược lại là không liên thông. 
Đoạn code chính của chương trình 
Procedure loang(sx,sy); 
Var localF, localC: integer; 
Procedure tham(x,y:integer); 
Var d:integer; 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
10
Begin 
 Case A[x,y] of 
 begin 
‘#’: Exit; 
‘f’: localF:= localF+1; 
‘c’: localC:=localC+1; 
 End; 
A[x,y]:=’#’; 
For d:=1 to 4 do 
Tham(x+dx[d], y+d[y]); 
End; 
 Begin 
LocalF:=0; 
LocalC:=0; 
Tham(sx,sy); 
If localC>localF then nC:=nC+loaclC 
 else nF:=nF+localF; 
End; 
Procedure solve; 
Var 
 i, j: integer; 
begin 
 nF:=0; nC:=0; 
 For i:= 1 to m do 
 For j:= 1 to n do 
 If A[i,j] ‘#’ then loang(i, j); 
End; 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
11
Bài toán 3: Đường đi của Robot (Đề thi HSG lớp 12 năm học 2009 - 2010, 
Tỉnh Hà Tĩnh) 
Một bảng hình chữ nhật có kích thước MxN (M,N nguyên dương và không lớn 
hơn 100) được chia thành các ô vuông đơn vị bằng các đường thẳng song song 
với các cạnh. Một số ô vuông nào đó có thể đặt các vật cản. Từ một ô vuông, 
Robot có thể đi đến một ô vuông kề cạnh với nó nếu ô vuông đó không có vật 
cản. Hỏi rằng nếu Robot bắt đầu xuất phát từ một ô vuông không có vật cản 
thuộc dòng K, cột L thì có thể đi đến được ô vuông không có vật cản thuộc dòng 
H, cột O hay không? Nếu có thì hãy chỉ ra đường đi qua ít ô vuông nhất. 
Dữ liệu vào là tệp văn bản BAI3.INP có cấu trúc: 
 - Dòng đầu tiên ghi các chữ số M, N, K, L, H, O. Các số ghi cách nhau ít 
nhất một ký tự trống; 
 - M dòng tiếp theo, mỗi dòng ghi N số 1 hoặc 0 tuỳ thuộc vào ô vuông 
tương ứng trong bảng hình chữ nhật nêu trên có vật cản hay không (ghi số 1 nếu 
có vật cản); các số trên mỗi dòng ghi liên tiếp nhau. 
Dữ liệu ra là tệp văn bản BAI3.OUT có cấu trúc: 
 Nếu Robot có thể đi được từ ô vuông thuộc dòng K, cột L đến ô vuông 
thuộc dòng H, cột O thì: 
 - Dòng đầu tiên ghi ‘Co duong di ‘; 
 - Các dòng tiếp theo, mỗi dòng ghi 2 số là chỉ số dòng và chỉ số cột của các 
ô vuông trong đường đi tìm được từ ô vuông thuộc dòng K, cột L đến ô vuông 
thuộc dòng H, cột O mà qua ít ô vuông nhất. Hai số trên mỗi dòng ghi cách nhau 
ít nhất một ký tự trống; 
 - Ngược lại, nếu Robot không thể đi được từ ô vuông thuộc dòng K, cột L 
đến ô vuông thuộc dòng H, cột O thì ghi ‘Khong co duong di’. 
Phân tích: 
Yêu cầu của bài toán thực chất là tìm đường đi từ ô [K,L] đến ô [H,O] sao cho 
qua ít ô vuông nhất. Ta dễ thấy thuật toán để xử lý một cách hợp lý nhất là thuật 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
12
toán Loang. Ta bắt dầu “loang” từ ô [K,L], nếu “loang” đến được ô [H,O] thì có 
đường đi, ngược lại không có đường đi. 
Hàng đợi phục vụ “loang” được thể hiện bởi mảng 2 chiều 
Q:Array[1..2,Mmax*Max] of Byte; hàng thứ 1 của Q để lưu thông tin chỉ số 
hàng, hàng thứ 2 lưu thông tin của chỉ số cột của các ô khi nạp vào Q. 
Mảng A lưu thông tin tình trạng các ô - có vật cản hay không của bảng hình chữ 
nhật chứa các ô vuông. 
Mảng P dùng để đánh dấu những ô đã “loang” đến; đồng thời để phục vụ cho 
việc truy xuất đường đi sau này nên khi ô [i,j] được “loang” đến thì P[i,j] được 
gán giá trị là r (r là giá trị tương ứng với hướng mà ô trước đó “loang” đến, 
hướng nào tương ứng với giá trị k bao nhiêu tuỳ theo quy định, ví dụ r = 1 - sang 
phải, 2 - đi xuống, 3 - sang trái, 4 - đi lên). 
Sau khi thực hiện xong việc “loang”, nếu P[H,O] = 0 thì điều có có nghĩa là ô 
[H,O] chưa được “loang” đến (không có đường đi), nếu P[H,O] = r (r=1..4 - 
loang theo 4 hướng) thì dựa vào hướng “loang” đến mà ta tìm được ô trước đó, 
rồi ta lại dựa vào giá trị k của ô tìm được ta tìm được ô trước đó nữa ... quá trình 
trên kết thúc khi tìm được ô [K,L]. 
Sau khi “loang” xong thì giá trị các phần tử trong mảng Q không còn giá trị sử 
dụng nữa nên ta có thể dùng mảng Q phục vụ cho việc truy xuất kết quả. 
Đoạn code của chương trình con thực hiện việc loang. 
Procedure Loang; 
 Begin 
 dau:=1; 
 cuoi:=1; 
 Q[1,dau]:=k; 
 Q[2,dau]:=l; 
 Fillchar(P,sizeof(P),0); {Mảng để đánh dấu ô đã duyệt hay chưa, khác 0 là đã 
duyệt rồi} 
 P[k,l]:=5; {Đánh dấu để những lớp sau không phải “loang” đến ô này nữa } 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
13
 While dau<=cuoi do 
 Begin 
 i:=Q[1,dau]; 
 j:=Q[2,dau]; 
 dau:=dau+1; 
 If (i=h) and (j=o) then Exit;{Đến ô cần đến} 
 If (i>1) and (P[i-1,j]=0) and (A[i-1,j]=0) then 
 Begin 
 P[i-1,j]:=4;{o truoc do ben duoi} 
 cuoi:=cuoi+1; 
 Q[1,cuoi]:=i-1; 
 Q[2,cuoi]:=j; 
 End; 
 If (i<M) and (P[i+1,j]=0) and (A[i+1,j]=0) then 
 Begin 
 P[i+1,j]:=2; 
 cuoi:=cuoi+1; 
 Q[1,cuoi]:=i+1; 
 Q[2,cuoi]:=j; 
 End; 
 If (j>1) and (P[i,j-1]=0) and (A[i,j-1]=0) then 
 Begin 
 P[i,j-1]:=3; 
 cuoi:=cuoi+1; 
 Q[1,cuoi]:=i; 
 Q[2,cuoi]:=j-1; 
 End; 
 If (j<N) and (P[i,j+1]=0) and (A[i,j+1]=0) then 
 Begin 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
14
 P[i,j+1]:=1; 
 cuoi:=cuoi+1; 
 Q[1,cuoi]:=i; 
 Q[2,cuoi]:=j+1; 
 End; 
 End; 
 End; 
Phần III: KẾT LUẬN VÀ KIẾN NGHỊ 
1. Kết luận 
 Với mục đích đã đặt ra đề tài đã làm được: 
- Giới thiệu rõ thuật toán loang. 
- Trình bày thuật toán loang. 
- Đưa ra các dạng bài tập thường gặp với cách giải cụ thể của các bài tập 
đưa ra 
 Tuy nhiên, với thời gian không nhiều và những hiểu biết còn nhiều hạn 
chế nên số lượng bài tập chưa được nhiều và chưa thật sự phong phú. 
2. Kiến nghị, đề xuất 
Đề tài đã giới thiệu về lý thuyết, cài đặt một số bài tập cơ bản và một số 
dạng bài trong các kì thi chọn học sinh giỏi. Tuy nhiên, do thời gian có hạn nên 
một số lời giải đưa ra có thể chưa tối ưu, trong thời gian tới tôi sẽ cố gắng đưa ra 
lời giải tối ưu hơn. 
Với việc trình bày khá chi tiết, đầy đủ về lý thuyết và các bài tập vận dụng 
tương đối dễ hiểu, hy vọng đề tài sẽ là tài liệu học tập tốt cho các em ôn thi học 
 “Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
15
sinh giỏi và cũng là tài liệu cần cho các giáo viên tham gia bồi dưỡng học sinh 
giỏi các cấp. 
Trong thời gian tới có thể mở rộng đề tài bằng cách bổ sung thêm các dạng 
toán thường gặp, trình bày các bài toán trong các kì thi học sinh giỏi, từ đó lập 
thành menu giúp học sinh học tập thuận lợi hơn. 
Phần IV. TÀI LIỆU THAM KHẢO 
1. Sách giáo khoa Tin học 11. NXB Giáo dục – năm 2014 
2. Hồ sĩ Đàm. Tài liệu giáo khoa chuyên Tin 1. NXB Giáo dục – năm 2009 
3. Nguyễn To Thành, Lập trình nâng cao trên ngôn ngữ Pascal. . NXB Đại 
học Quốc gia – năm 2000 
4. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật. NXB Khoa học và Kĩ thuật 
– năm 1998 
Lê Minh Hoàng, giải thuật và lập trình, NXB Đại học sư phạm Hà Nội – năm 
1999