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

 z
 SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ TĨNH
 
 SÁNG KIẾN KINH NGHIỆM
 Đề tài: 
 Sử dụng thuật toán “lùa bò vào chuồng” 
 để giải các bài toán đếm
 Hà Tĩnh, tháng 09 năm 2019 I.2. Mục tiêu nghiên cứu
 "Đếm" là công việc quan trọng và đơn giản mà chúng ta làm thường ngày, điều 
đó thì không cần phải bàn đến làm gì? Điều đáng nói ở đây là công việc có vẻ nhàm 
chán đó lại chứa bao điều thú vị, nhất là khi gặp những bài toán yêu cầu ta phải "đếm". 
 "Đếm" ở đây không phải đơn thuần là đếm 1, 2, 3, ... mà còn cần ở người đếm 
một sự khéo léo và có thể có một chút kỹ thuật. Bên cạnh đó để giúp các em học sinh 
có kiến thức khoa học cơ bản, hiện đại, tiến tiến, có tính tự lập và khả năng sáng tạo, 
nhận thức ở mức độ cao, tư duy tốt về lập trình. Các phương pháp đếm đơn giản là một 
trong những vấn đề mà bất cứ người lập trình tin học đều cần phải nắm vững. 
 I.3. Nhiệm vụ nghiên cứu
 Trước hết là thực hiện đổi mới phương pháp giảng dạy Tin học làm cho học sinh 
tìm ra những kết quả sáng tạo, lời giải hay trên một số “dạng bài toán tin có liên quan 
đến việc đếm”; giúp bản thân nắm vững hơn nữa về tư duy thuật toán, khả năng lập 
trình, đồng thời để trao đổi và học tập kinh nghiệm với các quý thầy cô giáo trong 
nhóm Tin học của nhà trường nói riêng và các quý thầy cô giảng dạy môn Tin học 
trong ngành nói chung. 
 I.4. Đối tượng nghiên cứu
 Trong nghiên cứu này, các học sinh được chọn là các em học sinh học môn Tin 
học khối 10, khối 11, các học sinh là thành viên của đội tuyển HSG môn Tin học, và 
một số giáo viên đứng lớp dạy Tin học ở các trường THPT trên địa bàn. 
 I.5. Các phương pháp nghiên cứu
 * Phương pháp suy luận, tổng hợp: kết hợp từ nhiều nguồn tài liệu tham khảo của 
các tác giả và tra cứu trên mạng internet với các đề thi HSG rút ra những kinh nghiệm, 
hệ thống lại kiến thức, mở ra các hướng mới.
 * Phương pháp trò chuyện – phỏng vấn: trao đổi tâm tình với nhiều HSG để nắm 
tình hình trong việc giải các bài toán tin về dãy số (mảng). 
 * Phương pháp khảo sát: bản thân được tham gia giảng dạy các lớp, đội tuyển 
HSG, các kỳ tập huấn; tham khảo các thầy cô, đồng nghiệp giảng dạy đội tuyển nhiều 
năm nên có tìm hiểu thêm về các phương pháp làm bài của các em học sinh. 
 * Phương pháp phân tích lý luận: phân tích giúp học sinh nắm thật rõ bản chất 
vấn đề, lựa chọn được phương pháp giải cho phù hợp.
 2 đố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: 
 4 Write('So ', li, ' co so luong lon nhat la ', return 0;
maxsl); }
 Readln; 
 END.
2. Bài 2: Nhập vào số nguyên dương N (2 ≤ N ≤ 10000) và một dãy a 1, 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 ( a i 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; #include 
 C: array[0..maxint] of integer; using namespace std;
 i, j, n, D: integer; const int maxint = 32768;
begin randomize; int i, D, n, a[10000], c[maxint];
 write('Nhap N = '); readln(n); int main()
 for i:=1 to n do { cout >n;
 a[i]:=random(maxint)-random(100); for(i=1; i<=n; i++)
 writeln('Day phan tu la '); a[i]=2+rand()%10001;
 for i:=1 to n do memset(c, 0, sizeof(c));
 write(a[i]:8); for(i=1; i<=n; i++)
 fillchar(C, sizeof(C), 0); { cout<<a[i]<<endl;
 for i:=1 to N do inc(C[a[i]]); c[a[i]]++; }
 D:=0; D=0;
 for j:=0 to maxint do for (i=1;i<= maxint;i++)
 if c[j]0 then inc(D); if (c[i]>0) D++;
 6 read(f, x); if(x<=n) c[x]++;
 if x<=n then inc(c[x]); }
 end; for (i=1; i<=n; i++)
 close(f); if(c[i]==0)
 for i:=0 to n do {
 if c[i]=0 then begin x=i;
 x:=i; break;
 break; }
 end; freopen("SN.out", "w", stdout);
 assign(f, fo); rewrite(f); cout<<x;
 write(f, x); return 0;
 close(f); }
END.
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 25
faculty of technology
Hanoi National University
aaAAAAAaaaaAAAAaAaAaAa
cccCCCeeefffggg123456$#)(*+= 
 8 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
 -1 0 2
 0 1
 10 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;
 12 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;
 14 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 lop10tin 
 abcdef 
 bbcc 
 lop10tin 
 abcdef 
 bbcc 
 abcdef 
 abcdef 
 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. 
 16 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ôi nhận thấy vấn đề này giúp ích rất 
nhiều cho HSG môn Tin học trong việc học, giúp các em không còn “e ngại” chuyên 
 18 III. KẾT LUẬN VÀ KIẾN NGHỊ
 1. Kết luận
 Công tác dạy và bồi dưỡng HSG ở trường tôi những năm gần đây tuy chưa đạt 
được kết quả cao trong kỳ thi HSG Tỉnh, nhưng phần nào đã đáp ứng được yêu cầu rèn 
luyện các mục tiêu nhận thức ở mức độ cao, sự trưởng thành của học sinh sau khi rời 
ghế nhà trường phổ thông. Hầu hết các em HSG môn Tin học đều được học tập ở môi 
trường cao hơn và học giỏi ở các trường Đại học. 
 So với số lượng tài liệu của những môn học truyền thống thì tài liệu để học 
chuyên tin thật sự quá ít. Chủ yếu các tài liệu chỉ nêu đề bài, rồi cho code, sách nào kỹ 
nữa thì cho test chứ những tài liệu mang tính định hướng làm bài, phân tích thuật toán 
rất ít. Vì vậy, tôi viết đề tài nghiên cứu này nhằm mục đích cùng trao đổi với Quý thầy 
cô dạy bồi dưỡng HSG Tin học về 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” để “hệ thống” các kiến thức, một vài kỹ năng, 
ứng dụng thuật toán vào lập trình giải quyết các bài toán tin. 
 2. Kiến nghị, đề xuất
 Trong quá trình áp dụng chuyên đề, để chuyên đề thực sự có hiệu quả chúng ta 
cần lưu ý những vấn đề sau:
 - Bồi dưỡng học sinh giỏi là một quá trình mang tính khoa học, không thể chỉ 
một vài tháng mà phải xây dựng kế hoạch cụ thể trong suốt cả ba năm học; như vậy 
mới cung cấp được đầy đủ các kiến thức cần thiết cho học sinh. Các bài giảng dạy theo 
các chuyên đề, tách thành các chủ đề, chủ điểm càng cụ thể càng tốt. 
 - Các giáo viên chúng ta cũng phải bình tĩnh, không nóng vội; nên đặt ra những 
mục tiêu giảng dạy thật thấp trong các bài học đầu tiên để đảm bảo học sinh không bị 
chán nản.
 - Việc gia tăng các tài liệu cho học sinh giỏi là việc tất yếu. Tài liệu viết nên có 
tính hệ thống hơn, nên biên soạn các bài tập theo chủ đề từ dễ đến khó, để kể cả các 
học sinh và giáo viên mới tiếp cận cũng dễ nắm bắt.
 Với những đặc điểm nêu trên, tôi kết luận rằng chuyên đề này có thể áp dụng 
được rộng rãi ở các trường THPT trong công tác bồi dưỡng HSG môn Tin học. Mong 
rằng, chuyên đề sẽ được sự góp ý của Hội đồng khoa học, các đồng nghiệp tham khảo 
 20 TÀI LIỆU THAM KHẢO
1. Hồ Sĩ Đàm (Chủ biên) 2006, Tin học 10, NXB Giáo dục, Hà Nội.
2. Hồ Sĩ Đàm (Chủ biên) 2006, Tin học 10 - Sách giáo viên, NXB Giáo dục, Hà Nội
3. Hồ Sĩ Đàm (Chủ biên) 2007, Tin học 11, NXB Giáo dục, Hà Nội
4. Hồ Sĩ Đàm (Chủ biên) 2007, Tin học 11 – Sách giáo viên, NXB Giáo dục, Hà Nội
5. Hồ Sĩ Đàm (Chủ biên) 2011, Tài liệu chuyên Tin học - quyển1, NXB Giáo dục, Hà Nội
6. Lê Minh Hoàng, Giải thuật và lập trình (Ebook-Bài giảng chuyên đề), ĐHSP Hà Nội
7. Nguyễn Xuân Huy, 2008, Sáng tạo trong thuật toán và lập trình - tập 1 (Ebook).
8. Nguyễn Xuân Huy, 2010, Sáng tạo trong thuật toán và lập trình - tập 2 (Ebook).
9. Nguyễn Xuân Huy, 2010, Sáng tạo trong thuật toán và lập trình - tập 3(Ebook).
10. Một số tài liệu trên mạng Internet;
11. Các đề thi HSG cấp tỉnh, các đề thi HSG Quốc gia, Các đề thi HSG Quốc tế.
 22