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

ngth(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);
 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
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;
 	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;
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;
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;
* 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). 
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. 
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.
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 đề này nữa, các em đã hiểu và vận dụng khá tốt những phần liên quan đến việc đếm ứng dụng vào Tin học; một số em đã bước đầu sáng tạo được những cách giải hay, các giải mới (tuy là những bài toán còn “đơn giản”). Riêng bản thân tôi sẽ tiếp tục nghiên cứu sâu hơn nữa về chuyên đề này hy vọng sẽ “làm rõ hơn nữa” để các học sinh trong đội tuyển HSG Tin học thích học và đạt nhiều thành tích hơn nữa.
Nếu biết vận dụng tốt những suy luận sẽ làm cho những bài toán tin có những giải thuật đơn giản và đạt được kết quả tốt hơn. Đặc biệt là trong công việc đếm, đòi hỏi phải lựa chọn cách giải quyết phù hợp cho các bài toán có đầu vào lớn.
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 và bổ sung đầy đủ hơn. Vì kiến thức và thời gian còn nhiều hạn chế nên chắc rằng nghiên cứu còn có thiếu sót, tôi chân thành đón nhận sự góp ý của Quý thầy cô.
 Xin chân thành cảm ơn!
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ế.
MỤC LỤC
	Trang