Sáng kiến kinh nghiệm Sử dụng thuật toán “lùa bò vào chuồng” để giải các bài toán đếm

các đối tượng thì ta dùng một cấu 
trúc dữ liệu hợp lý (thường dùng kiểu mảng hoặc kiểu con trỏ) với ý nghĩa giống như 
các “chuồng” để lưu các đối tượng, mỗi phần tử của mảng tương ứng với một chuồng. 
Trên cơ sở đó ta dễ dàng thực hiện được mục đích của mình là thực hiện thao tác đếm. 
Để hiểu rõ hơn thuật toán ta xét ví dụ sau: “Viết chương trình nhập từ bàn phím 
một xâu ký tự S và thông báo ra màn hình số lần xuất hiện của mỗi chữ cái tiếng Anh 
trong S (không phân biệt chữ hoa hay chữ thường)” – Bài 2. Bài tập và thực hành 5 - 
sách Tin học 11 - trang 73. Rõ ràng với bài toán này ta có thể duyệt toàn bộ xâu S và 
mỗi lần duyệt ta thực hiện thao tác đếm một chữ cái. Sau 26 lần duyệt tương ứng với 
26 chữ cái thì ta thu được toàn bộ kết quả. Tuy nhiên, vì việc duyệt xâu như vậy tương 
4 
đối chậm và có thể xâu văn bản đã cho rất dài nên về thời gian là không chấp nhận 
được. Ta vận dụng thuật toán “lùa bò vào chuồng” bằng cách sử dụng một mảng tĩnh 
A:array[′A′..′Z′] of Longint; với ý nghĩa như sau: giá trị A[c] trong đó c thuộc [′A′..′Z′] 
lưu số lần xuất hiện của ký tự c trong file văn bản. Mảng A được khởi tạo với tất cả 
các giá trị bằng 0, khi duyệt xâu ta đọc lần lượt các ký tự trong xâu ra một biến trung 
gian ch nào đó, và tăng giá trị của mảng tại vị trí tương ứng có chỉ số ch lên một đơn 
vị qua câu lệnh: A[ch]:=A[ch] + 1. Như vậy, bài toán được giải quyết chỉ với một lần 
duyệt xâu duy nhất. 
Sau đây chúng ta cùng khảo sát một số ví dụ điển hình vận dụng thuật toán này. 
1. Bài 1: Đếm bò 
Tên chương trình: DEMBO.* 
Bài toán đặt ra là giả sử trên cánh đồng rộng thả rất nhiều bò (N con), mỗi con bò 
đeo một thẻ có số hiệu nguyên dương (là số tháng tuổi của nó). 
Tất nhiên, hai con bò cùng tháng tuổi thì đeo thẻ có số hiệu như nhau. Làm thế 
nào để đếm được loại bò nào có nhiều nhất? 
Bài toán này có thể phát biểu lại như sau: 
+ Nhập từ bàn phím số nguyên dương N (0 < N ≤ 200) và các phần tử của mảng 
một chiều A(N) có giá trị nguyên dương (0 < A[i] ≤ 100). 
+ Giá trị nào xuất hiện nhiều nhất trong A và xuất hiện bao nhiêu lần? 
+ Ví dụ: A(12) = {2, 3, 2, 4, 5, 6, 2, 6, 7, 1, 6, 2} thì A(12) có số phần tử giá trị 
bằng 2 là nhiều nhất. Số lượng phần tử này là 4. 
Thuật toán “Lùa bò vào chuồng” 
Để giải bài toán này người ta dùng thuật toán “lùa bò vào chuồng” gồm 3 bước: 
- Bước 1: Đóng dãy chuồng bò và đánh số các chuồng bằng các số tự nhiên liên 
tiếp từ 1 đến max (max là số tháng tuổi của con bò già nhất), ban đầu mọi chuồng đều 
chưa có bò ở trong. 
- Bước 2: Lùa bò vào chuồng có số hiệu bằng số thẻ của nó. 
- Bước 3: Duyệt dãy chuồng bò tìm chuồng có nhiều bò nhất. 
Áp dụng thuật toán vào bài tập: 
5 
+ Bước 1: Giả sử con bò thứ i có tháng tuổi là a[i] (1 ≤ i ≤ n). Coi mảng b(n) như 
dãy chuồng bò, b[x] là số lượng bò (có x tháng tuổi) trong chuồng có số hiệu x, ban 
đầu các phần tử của mảng b(n) đều bằng 0. 
+ Bước 2: Con bò có tháng tuổi a[i] phải vào chuồng bò có số hiệu a[i]. Thêm 1 
con bò vào chuồng a[i] tương ứng với lệnh inc(b[a[i]]) 
+ Bước 3: Duyệt mảng b, tìm chỉ số phần tử lớn nhất. 
Chương trình tham khảo: 
Code Pascal Code C++ 
Const max = 200; 
Var N: integer; 
A: array[1..max] of byte; 
B: array[1..max] of byte; 
maxsl, i, li: integer; 
BEGIN 
 Write('Nhap N = '); Readln(N); 
 For i := 1 to N do 
Begin 
 Write('A[', i, ' ] = '); Readln(A[i]); 
End; 
Fillchar(B, sizeof(B), 0); maxsl := 0; 
{Tao day chuong bo rong chua co bo} 
For i := 1 to N do inc(B[A[i]]); 
{Tang them 1 con bo vao chuong co so hieu 
A[i]} 
For i := 1 to max do 
{Duyet day chuong tim chuong co nhieu bo 
nhat} 
 if B[i] > maxsl then 
 Begin 
 maxsl := B[i]; li := i; 
 End; 
#include 
using namespace std; 
int i, j, n, a[200], b[200], maxsl; 
int main() 
{ 
cout << " Nhap n = "; 
cin>>n; 
for(i=1;i<=n;i++) 
{ 
 cout<<"a["<<i<<"]="; 
 cin>>a[i]; 
 } 
memset(b,0,sizeof(b)); 
for(i=1;i<=n;i++) b[a[i]]++; 
maxsl=0; 
for (i=1;i<= 200;i++) 
 if (b[i]>maxsl) 
 { 
 maxsl=b[i]; 
 j=i; 
 } 
cout << " so "<<j<<" co so 
luong lon nhat la "<<maxsl; 
6 
 Write('So ', li, ' co so luong lon nhat la ', 
maxsl); 
Readln; 
END. 
 return 0; 
} 
2. Bài 2: Nhập vào số nguyên dương N (2 ≤ N ≤ 10000) và một dãy a1, a2,.an các 
phần tử nguyên dương (ai ≤ 32000). Cho biết dãy trên có bao nhiêu phần tử khác nhau. 
Ý tưởng: Để làm bài này ta dùng thuật toán “lùa bò vào chuồng”, các phần tử 
bằng nhau sẽ nhốt chung một chuồng, có bao nhiêu chuồng thì có bấy nhiêu phần tử 
khác nhau trong dãy ban đầu. 
Ta đóng dãy chuồng C, đánh số chuồng lần lượt từ 1, 2.32000 ( ai là các số 
nguyên dương, ai<32000), ban đầu các chuồng đều trống). Duyệt mảng A ban đầu, 
phần tử a[i] sẽ được “nhốt” vào chuồng có số a[i] (tăng C[a[i]] lên một đơn vị).. Đếm 
số chuồng khác trống đó chính là số phần tử khác nhau của dãy ban đầu. 
Chương trình tham khảo: 
Code Pascal Code C++ 
var A: array[1..10000] of integer; 
 C: array[0..maxint] of integer; 
 i, j, n, D: integer; 
begin randomize; 
write('Nhap N = '); readln(n); 
for i:=1 to n do 
a[i]:=random(maxint)-random(100); 
 writeln('Day phan tu la '); 
for i:=1 to n do 
write(a[i]:8); 
fillchar(C, sizeof(C), 0); 
 for i:=1 to N do inc(C[a[i]]); 
D:=0; 
for j:=0 to maxint do 
 if c[j]0 then inc(D); 
#include 
using namespace std; 
const int maxint = 32768; 
int i, D, n, a[10000], c[maxint]; 
int main() 
{ cout >n; 
 for(i=1; i<=n; i++) 
 a[i]=2+rand()%10001; 
 memset(c, 0, sizeof(c)); 
 for(i=1; i<=n; i++) 
 { cout<<a[i]<<endl; 
 c[a[i]]++; } 
 D=0; 
 for (i=1;i<= maxint;i++) 
 if (c[i]>0) D++; 
7 
writeln('So phan tu khac nhau cua day la 
', D:4); 
readln 
end. 
 cout << " so phan tu khac nhau la 
"<<D; 
 return 0; 
} 
3. Bài 3. (Ví dụ 5. Tài liệu chuyên Tin học - quyển 1 trang 53) 
Cho dãy gồm N (N <=30000) số tự nhiên không vượt quá 109, tìm số tự nhiên 
nhỏ nhất không xuất hiện trong dãy. 
Dữ liệu vào trong file SN.INP có dạng: 
- Dòng đầu là số nguyên N 
- Dòng thứ hai gồm N số 
Kết quả ra file SN.OUT có dạng: số tự nhiên nhỏ nhất không xuất hiện trong dãy. 
SN.INP SN.OUT 
5 
5 0 3 1 4 
2 
Ý tưởng: Ta có nhận xét sau: số tự nhiên nhỏ nhất không xuất hiện trong dãy sẽ 
nằm trong đoạn [0, n]. Do đó, ta sử dụng mảng c: array[0..30000] of longint; với c[x] 
là số lần xuất hiện của x trong dãy, nếu c[x]=0 tức là x không xuất hiện trong dãy. 
Chương trình tham khảo: 
Code Pascal Code C++ 
Const limit = 30000; 
fi='SN.INP'; 
fo='SN.OUT'; 
var c:array[0..Limit] of longint; 
n, i, x: longint; 
f:text; 
BEGIN 
 fillchar(c, sizeof(c), 0); 
 assign(f, fi); reset(f); readln(f, n); 
for i:=1 to n do 
begin 
#include 
using namespace std; 
int i, x, n, c[30000]; 
int main() 
{ 
 memset(c,0,sizeof(c)); 
freopen("SN.inp", "r", stdin); 
 cin>>n; 
 for(i=1; i<=n; i++) 
 { 
 cin>>x; 
8 
 read(f, x); 
 if x<=n then inc(c[x]); 
end; 
close(f); 
for i:=0 to n do 
if c[i]=0 then begin 
 x:=i; 
 break; 
 end; 
 assign(f, fo); rewrite(f); 
 write(f, x); 
 close(f); 
END. 
 if(x<=n) c[x]++; 
 } 
for (i=1; i<=n; i++) 
 if(c[i]==0) 
 { 
 x=i; 
 break; 
 } 
freopen("SN.out", "w", stdout); 
 cout<<x; 
 return 0; 
} 
4. Bài 4. Tần số (Đề thi Olimpic sinh viên 2001, khối đồng đội) 
Cho một văn bản gồm không quá N (N ≤500) dòng, mỗi dòng chứa không quá 80 
ký tự. Ta gọi tần số của một ký tự trong văn bản là số lần xuất hiện của ký tự đó trong 
văn bản. 
Yêu cầu: Tìm tần số lớn nhất trong các tần số của các chữ cái (không phân biệt 
chữ hoa hay chữ thường) trong văn bản đã cho. 
Dữ liệu vào: từ file văn bản có tên là FREQ.INP: 
Dòng đầu tiên chứa N là số lượng dòng văn bản. 
N dòng tiếp theo mỗi dòng chứa một dòng của văn bản đã cho. 
Kết quả: ghi ra file văn bản có tên FREQ.OUT tần số lớn nhất tìm được. 
Ví dụ: 
FREQ.INP FREQ.OUT 
4 
faculty of technology 
Hanoi National University 
aaAAAAAaaaaAAAAaAaAaAa 
cccCCCeeefffggg123456$#)(*+= 
25 
9 
Lời giải cho bài toán này gần giống như ví dụ đã trình bày ở trên. Bạn đọc có thể 
xem thuật giải thông qua chương trình mẫu dưới đây: 
var a:array[1..256] of longint; 
 n:integer; 
procedure solve; 
var f:text; 
i,j,k:integer; 
s:string; 
ss:set of byte; 
begin 
fillchar(a,sizeof(a),0); 
ss:=[65..90]; 
assign(f,′FREQ.INP′); reset(f); 
readln(f,n); 
for i:=1 to n do 
begin 
 readln(f,s); 
 for j:=1 to length(s) do 
 begin 
 k:=ord(s[j]); 
 if k in ss then k:=k+32; 
 inc(a[k]); 
 end; 
end; 
close(f); 
end; 
procedure output; 
var f:text; i,m:longint; 
begin 
 assign(f,′FREQ.OUT′); 
 Rewrite(f); 
10 
 m:=a[1]; 
 for i:=2 to 256 do 
 if m < a[i] then m:=a[i]; 
 write(f,m); close(f); 
end; 
BEGIN 
 solve; 
 output; 
END. 
5. Bài 5. Phủ nhỏ nhất (Đề thi chọn HSG Quốc gia lớp 12 năm 1998-1999) 
Cho tập hợp n đoạn thẳng (đánh số từ 1 đến n) với các đầu mút có toạ độ nguyên 
[Li,Ri], i=1,2, 3,,n và một đoạn thẳng [P,Q] (P, Q là các số nguyên). 
Yêu cầu: Cần tìm một số ít nhất đoạn thẳng trong tập đã cho để phủ kín đoạn 
thẳng [P,Q] (nghĩa là mỗi điểm x thuộc [P,Q] phải thuộc vào ít nhất một trong số các 
đoạn thẳng được chọn). 
Dữ liệu vào: từ file văn bản PHU.INP: 
- Dòng đầu tiên ghi 3 số n, P, Q phân cách nhau bởi dấu trắng; 
- Dòng thứ i trong số n dòng tiếp theo chứa hai số L, R phân cách nhau bởi dấu trắng 
(i=1, 2,, n); 1 ≤ n ≤ 100 000; P − Q ≤ 5000; |Li| ≤ 50000; |Ri|≤50000, 
i = 1, 2,, n. 
Kết quả: ghi ra file văn bản PHU.OUT: 
- Dòng đầu tiên ghi số k là số lượng đoạn cần chọn (quy ước ghi số 0 nếu không tìm 
được lời giải); 
- Nếu k > 0 thì mỗi dòng trong số k dòng tiếp theo ghi số của một đoạn thẳng được 
chọn. 
Ví dụ: 
PHU.INP PHU.OUT 
2 0 1 
-1 0 
0 1 
1 
2 
11 
Thuật toán: Ta phân tích bài toán để có thể áp dụng sáng tạo tư tưởng của thuật 
toán đã trình bày như sau: Ta thấy rằng độ dài đoạn thẳng [P,Q] không lớn hơn 5000. 
Còn số đoạn thẳng trong tập đã cho có thể lên tới 100000. Ta không thể lưu tất cả các 
đoạn thẳng này lại được. Vậy chúng ta có thể lưu các đoạn thẳng này theo cách: lưu 
từng đoạn một, dùng một mảng A có độ dài chính bằng độ dài đoạn thẳng [P,Q], kích 
thước của mảng này là 5000x2 (A: Array [ 0..5000, 1..2 ] Of LongInt;) 
Ta coi đoạn [P,Q] là mảng A trên. Ta lần lượt đọc các đoạn thẳng của tập n các đoạn 
thẳng. Với mỗi đoạn thẳng vừa đọc được, ta xét xem chúng phủ đoạn [P,Q] bắt đầu từ 
đâu và độ dài mà đoạn thẳng đó phủ được. Ta sẽ lưu lại trên mảng A ở phần tử mà 
đoạn thẳng chúng ta vừa đọc bắt đầu phủ đoạn [P,Q] chỉ số của đoạn thẳng đó và độ 
dài chúng phủ được. 
A[Phần tử bắt đầu phủ,1] = chỉ số của đoạn vừa đọc và A[Phần tử bắt đầu 
phủ, 2] = độ dài mà đoạn đó phủ được. 
Nếu có nhiều đoạn thẳng bắt đầu phủ đoạn [P,Q] tại cùng một vị trí thì chọn đoạn 
nào có độ dài phủ được là lớn nhất. 
Sau khi làm xong công việc trên ta được một mảng gồm các đoạn thẳng phủ lên 
đoạn [P, Q]. Bây giờ ta sẽ tiến hành tìm xem số đoạn phủ ít nhất sẽ là bao nhiêu bằng 
cách: ta bắt đầu đi từ vị trí 0 (nếu tại vị trí này mà không có đoạn nào phủ thì sẽ không 
có lời giải) ta tìm xem có đoạn nào giao với đoạn này mà tạo thành một đoạn thẳng có 
phủ dài nhất thì ta lưu đoạn này lại (nếu không có đoạn thẳng nào giao với đoạn thẳng 
này để tạo được một đoạn thẳng có độ che phủ lớn hơn độ che phủ của đoạn trên thì sẽ 
không có lời giải). Làm tương tự với đoạn thẳng vừa tìm được cho đến khi các đoạn 
thẳng được chọn sẽ phủ kín đoạn [P, Q] ta sẽ được số đoạn thẳng ít nhất để phủ đoạn 
[P, Q]. Như vậy, thuật toán này cho phép giải quyết bài toán cũng chỉ với một lần 
duyệt mảng duy nhất. 
Dưới đây là chương trình minh hoạ: 
Const Fi = ′PHU.INP′; 
 Fo = ′PHU.OUT′; 
 Max = 5000; Dd = 2; 
Var n, P, Q, Min, Id : LongInt; 
 A : Array [ 0..Max,1..2 ] Of LongInt; 
12 
 C: Array[0..Max] Of LongInt; 
 F : Text; 
Procedure InitData; 
Var i, L, R : LongInt; 
Begin 
Id:=1; 
Assign(F, Fi); Reset(F); 
Readln(F, n, P, Q); 
FillChar(A, SizeOf(A), 0); 
For i := 1 To n Do 
 Begin 
Readln(F, L, R); 
If L <= P then 
 If A[0, Dd] < R - P then 
 Begin 
 A[0, id] := i; 
 If R > Q then A[0, Dd] := Q - P else A[0, Dd] := R - P; 
 End 
 else 
 else If L <= Q then 
 If A[L - P, Dd] < R - L then 
 Begin 
 A[L - P, id] := i; 
 If R > Q then A[L-P, Dd]:= Q-L else A[L-P, Dd]:= R - L; 
 End; 
 End; 
Close(F); 
End; 
Function tt(u,v:LongInt):LongInt; 
Begin 
If A[u, Dd]+u<=A[v, Dd]+v then tt:=A[v, Dd]+v else tt:=A[u, Dd]+u; 
13 
End; 
Procedure solve; 
Var i, j, tmp, Count, Max:LongInt; 
 Dung:Boolean; 
Begin 
Min:=0; 
If A[0, id]=0 then Exit; 
j:=0; Dung:=False; Count:=1; 
C[1]:=A[0, id]; 
If A[0, Dd] = Q-P then 
 Begin 
 Min:=1; Exit; 
 End; 
While Not Dung Do 
 Begin 
 Max:=j+A[j, Dd]; 
 For i:=j + 1 To j + A[j, Dd] Do 
 If (A[i, id]0) And (tt(i, j)>Max) then 
 Begin 
 Max:=tt(i, j); tmp:=i; 
 End; 
 If Max=j+A[j, Dd] then Exit else 
 Begin 
 Count:=Count + 1; 
 C[Count]:=A[tmp, id]; 
 j :=tmp; 
 If Max = Q - P Then Dung := True; 
 End; 
 End; 
Min := Count; 
14 
End; 
Procedure ReSult; 
Var i : LongInt; 
Begin 
Assign(F, FO); Rewrite(F); 
 Writeln(F, Min); 
 If Min 0 Then 
 For i: = 1 To Min Do Writeln(F, C[i]); 
 Close(F); 
End; 
BEGIN 
 InitData; 
 solve; 
 ReSult; 
END. 
Tham khảo thêm: Trong Sáng tạo trong thuật toán và lập trình - tập 2 (Ebook) 
tác giả Đỗ Xuân Huy có giới thiệu thêm thuật toán giải bài toán này như sau: 
Bài 1.7 trang 21 - Phương pháp: Tham (độ phức tạp N2) 
* Sắp các đoạn tăng theo đầu phải R. 
* k : = 1; { chỉ số đầu tiên }; v := P; { Đầu trái của đoạn [P,Q] } 
* Lặp đến khi v >= Q 
- Duyệt ngược từ N đến k 
- Tìm đoạn j [Lj, Rj] đầu tiên có đầu trái Lj <=v 
 + Nếu không tìm được: vô nghiệm; 
 + Nếu tìm được: 
Ghi nhận đoạn j; 
Đặt lại v := Rj; 
Đặt lại k := j+1; 
15 
* Có thể dùng thuật toán “Lùa bò vào chuồng” để giải quyết bài toán sau: 
1. Bài 1: Dự tiệc 
Ông An đến dự một buổi tiệc. Buổi tiệc đã có N người (0 < N < 500.000). Mỗi 
người dự tiệc đều được cài lên áo một bông hoa trên đó có ghi một con số nguyên 
dương X bất kì ( X<106) cho biết người khách đó sẽ dự tiệc tại phòng có chỉ số X. Hầu 
hết các phòng đều có số lượng khách là số chẵn, duy nhất chỉ có một phòng có số 
lượng khách là số lẻ. 
Để đảm bảo đủ cặp cho việc khiêu vũ nên ban tổ chức cần tìm ra số hiệu của 
phòng khách có số lượng khách là số lẻ để ghi số cho ông An. 
Yêu cầu: Cho trước một danh sách khách dự tiệc cùng với các số trên áo của họ, 
hãy giúp ban tổ chức tìm ra số hiệu của phòng khách có số lượng khách là số lẻ. 
Dữ liệu vào: Cho trong file văn bản DUTIEC.INP, gồm: 
+ Dòng đầu tiên ghi một số N cho biết số khách của buổi tiệc khi ông An đến. 
+ Trong N dòng tiếp theo, mỗi dòng ghi một số nguyên dương cho biết con số 
ghi trên áo của người khách thứ i. 
Dữ liệu ra: Ghi ra file văn bản DUTIEC.OUT gồm một số nguyên dương duy 
nhất. Đó là số hiệu của phòng có số lượng khách là số lẻ. 
Ví dụ: 
DUTIEC.INP DUTIEC.OUT 
5 
1 
2 
2 
3 
1 
3 
Hướng dẫn: Trong bài toán này, dãy phòng chỉ cần đóng số hiệu từ 1 đến số 
hiệu Xmax (Xmax = 106) và mỗi phòng chỉ chứa 1 trong 2 trạng thái chẳn hoặc lẻ 
(true, false), tìm thấy thêm một người khách của phòng i thì đổi trạng thái phòng i 
(toán tử not). 
16 
2. Bài 2: Chuỗi kiểm tra 
Cho một file văn bản có n dòng (3 < n ≤ 30000), mỗi dòng là một chuỗi S có tối 
đa 255 kí tự, các kí tự S[i] ∈ [‘a’..’z’] với 1 ≤ i ≤ length(S). Trong đó, chỉ có một 
chuỗi S có số lần xuất hiện là một số lẻ, các chuỗi khác có số lần xuất hiện là số chẳn. 
Yêu cầu: Tìm chuỗi S (có số lần xuất hiện lẻ) đó. 
Dữ liệu vào: từ file ‘CHUOIKT.inp’ 
+Dòng đầu là một số nguyên n. 
+ Dòng thứ i + 1 trong n dòng sau, mỗi dòng là một chuỗi kí tự (1 ≤ i ≤ n). 
Kết quả: ghi vào file ‘CHUOIKT.out’ chứa chuỗi kí tự tìm được. 
Ví dụ: 
CHUOIKT.INP CHUOIKT.OUT 
7 
abcdef 
bbcc 
lop10tin 
abcdef 
bbcc 
abcdef 
abcdef 
lop10tin 
3. Bài 3: Tuyển nhân viên 
Công ty phần mềm máy tính A có số lượng nhân viên rất lớn. Để tiện việc quản 
lý, công ty đã cấp cho mỗi nhân viên một mã số, mã số của mỗi nhân viên là một số 
nguyên dương, hai nhân viên bất kỳ thì có mã số khác nhau. Tuy nhiên, sau một thời 
gian thì một số nhân viên đã nghỉ hưu hoặc chuyển công tác, nên công ty phải tiến 
hành tuyển thêm k nhân viên mới. Các nhân viên mới này sau khi được tuyển vào 
cũng sẽ được cấp mã số, mỗi nhân viên một mã số và mã số này cũng phải là một số 
nguyên dương. 
Yêu cầu: Với n nhân viên hiện có (còn lại) của công ty tương ứng với các mã số 
a1, a2, , an. Hãy tìm k mã số nhỏ nhất để cấp cho k nhân viên mới tuyển vào sao cho 
vẫn thỏa mãn hai nhân viên bất kỳ (cả nhân viên cũ và nhân viên mới) có mã số khác 
nhau. 
17 
Dữ liệu vào: từ file ‘Recruit.inp’ có nội dung như sau: 
+ Dòng đầu chứ hai số nguyên dương lần lượt là n và k (k ≤ n ≤ 106). 
+ n dòng tiếp theo, dòng thứ i là số nguyên dương ai (i = 1, 2, , n; ai≤ 2*109). 
Kết quả: ghi vào file ‘Recruit.out’ k mã số theo thứ tự từ nhỏ đến lớn (mỗi mã số 
trên một dòng). 
Ví dụ: 
RECRUIT.INP RECRUIT.OUT 
5 3 
3 
1 
6 
9 
8 
2 
4 
5 
Hướng dẫn: 
+ Cách 1: Thuật toán O(NlogN) dùng quicksort đủ chấp nhận. 
+ Cách 2: Dùng Sắp xếp phân phối (Distribution sort). Trong bài toán này, dãy 
chuồng chỉ cần đóng số hiệu từ 1 đến số hiệu 2*nmax (nmax = 106) và mỗi chuồng chỉ 
chứa 1 trong 2 trạng thái đã có hoặc chưa có (true, false). Bằng cách chạy từ 1 đến n, 
nếu số nào < n+k thì đánh dấu chuồng đó bằng true. Sau đó chạy từ 1 đến n+k, nếu số 
nào bằng false thì in số đó ra file (chỉ in đủ k số). 
4. Bài 4: Xâu fibonacci. 
Định nghĩa: Dãy xâu fibo được xây dựng theo nguyên tắc sau: 
+ F1 =’B’; F2 =’A’; 
+ Fk = Fk-1 + Fk-2. 
Yêu cầu: Tính số lần xuất hiện của SR trong Fn (tức là số xâu con các kí tự liên 
tiếp nhau bằng SR). Hai xâu con được gọi là khác nhau nếu khác nhau ít nhất một ký 
tự.(N<=100). 
Dữ liệu vào: File FSTR.inp 
+ Dòng đầu tiên là số N. 
+ Dòng tiếp theo là xâu SR.(length(SR)<=15). 
Dữ liệu ra: File FSTR.out 
Số lần xuất hiện tìm được. 
18 
Hướng dẫn Thuật toán: Với phương pháp này chỉ giải quyết với dữ liệu không 
lớn lắm (N<=35) nhưng cũng là một cách để cách bạn tham khảo. 
+ Tìm Fn. Ta sẽ tìm Fn và đưa đó vào file để chứa. 
Chuơng trình tìm và xuất Fn rất đơn giản như sau: 
Function Fibo(N:integer):integer; 
Begin 
If n=1 then write(g, ’B’) 
Else 
If n=2 then write(g, ’A’) 
Else 
Fibo:=Fibo(n-2)+Fibo(n-1); 
End; 
+ Nhập xâu SR. Ta tưởng tượng rằng ’A’ chính là 1,’B’ chính là 0. Lúc này SR 
là biểu diễn nhị phân của số K. Vấn đề tìm k khá đơn giản. Sau khi tìm được k, ta mở 
file chứa Fn ra, sau đó lấy từng đoạn liên tiếp có chiều dài length(SR) ra chuyển ra nhị 
phân (với ’A’ chính là ’1’, ’B’ là ’0’), nếu chuyển ra nhị phân bằng đúng k thì tăng 
đếm lên 1. Sau khi đọc hết file thì biến đếm chính là kết quả cần tìm. 
Ví dụ: 
SR=’ABA’ SR=’101’ đây là biểu diễn của số K=5. 
Nếu dịch từng đoạn 3 ta sẽ đươc các xâu sau: 
’101’, ’011’,’110’,’101’,’010’,’101’,’011’,’110’,’101’,’011’,’110’. Ta sẽ chuyễn 
các xâu này ra số nếu bằng k thì tăng dem lên. Để tiết kiệm thời gian ta sẽ dùng bit để 
khỏi dùng chương trình chuyển nhị phân. 
+ Có thể có bạn sẽ hỏi là tại sao ta không dùng xâu luôn cho nó nhanh khỏi phải 
dùng nhị phân chi cho nó mệt. Ta đọc từng đoạn xâu con rồi kiểm tra có bằng SR 
không là xong. Tôi muốn giới thiệu cho các bạn phương pháp trên để giải quyết bài có 
thể hỏi nhiều xâu Sr chứ không phải là một xâu. Nếu như dùng xâu thì ta tốn đến 15 
byte, nhưng dùng số thì chỉ tốn 2 byte thôi. 
B. KẾT QUẢ NGHIÊN CỨU 
Qua quá trình nghiên cứu và vận dụng đề tài chuyên đề “Sử dụng thuật toán 
“lùa bò vào chuồng” để giải các bài toán đếm”, tô