SKKN Vận dụng 2 thuật toán sắp xếp hoặc tìm kiếm để tăng tốc độ chương trình, đảm bảo về mặt thời gian khi giải quyết các test lớn

Mục lục
1. Mở đầu
1.1. Lý do chọn đề tài
Đối với học sinh các trường THPT, chương trình Tin học 10 và Tin học 11 ngoài việc cung cấp cho học sinh cách tư duy và giải các bài toán với sự hỗ trợ của các Ngôn ngữ lập trình, cụ thể là Ngôn ngữ lập trình PASCAL, còn cung cấp 2 thuật toán sắp xếp (thuật toán sắp xếp bằng phương pháp tráo đổi) và tìm kiếm (tìm kiếm nhị phân).
Trong các đề thi học sinh giỏi Tin học tỉnh ta theo cấu trúc đề thi 2018 gồm 5 câu, trong đó câu 3, 4, 5 yêu cầu học sinh cần phải vận dụng được các thuật toán sắp xếp và tìm kiếm ở mức độ cơ bản và nâng cao để giải quyết các bài toán. Tuy nhiên một số học sinh có tư tưởng chỉ cần giải bài toán này bằng tư duy thông thường với bộ test nhỏ là đã quan niệm thuật toán của mình tối ưu. Việc này hoàn toàn sai lầm, khi giới hạn test được tăng cao thì chương trình của các em thường bị mất test khi chương trình chạy quá thời gian (mặc định giới hạn thời gian là 1 giây). Vì vậy muốn giải quyết các test lớn, ở 1 số bài toán các em phải vận dụng 2 thuật toán sắp xếp hoặc tìm kiếm để tăng tốc độ chương trình, đảm bảo về mặt thời gian khi giải quyết các test lớn.
1.2. Đối tượng và phạm vi nghiên cứu
- Môn Tin học lớp 11 ở trường THPT;
- Đội tuyển HSG trường THPT Hàm Rồng;
1.3. Phương pháp nghiên cứu
- Phân tích, tổng hợp, khảo sát.
- Đánh giá so sánh kết quả của học sinh;
2. Nội dung sáng kiến kinh nghiệm
2.1. Bài toán 1:
Cho 2 dãy số: dãy A có n phần tử, dãy B có m phần tử.
Yêu cầu: In ra m dòng, dòng thứ i là số lượng số trong dãy A nhỏ hơn hoặc bằng B[i]. 
Dữ liệu vào: Từ file văn bản SSDAYSO.INP
- Dòng đầu tiên chứa 2 số n, m lần lượt là số lượng phần tử của 2 dãy A, B.
- Dòng thứ 2 chứa n số nguyên A[1], A[2],  A[n].
- M dòng tiếp theo mỗi dòng chứa 1 số nguyên B[1], B[2],  B[m] 
(1 <= n, m, A[i], B[i] <= 106)
Dữ liệu ra: Ghi ra file văn bản SSDAYSO.OUT: In ra kết quả bài toán, mỗi kết quả trên 1 dòng.
SSDAYSO.INP
SSDAYSO.OUT
5 3
1 4 2 5 3
2
3
4
2
3
4
2.1.1. Thực trạng
Với cách tư duy thông thường học sinh sẽ khai báo 2 mảng A và B. 
- Duyệt từng phần tử trong mảng B, với mỗi phần tử B[i] duyệt toàn bộ mảng A:
+ Nếu a[j]<=b[i] thì tăng biến đếm
+ Sau khi duyệt hết mảng A thì ghi biến đếm lên tệp.
Như vậy thì độ phức tạp của thuật toán sẽ là (m x n), mà theo giới hạn đầu bài là: (1 <= n, m, A[i], B[i] <= 106). Suy ra với n,m lớn nhất ta có số phép toán phải thực hiện là 106 x 106 = 1012.
Nếu gặp test này thì chắc chắn chương trình không thể thực hiện trong 1 giây.
procedure process1;
var f:text; i,j,dem:longint;
begin
 assign(f,fo);
 rewrite(f);
 for i:=1 to m do
 begin
 dem:=0;
 for j:=1 to n do
 if a[j]<=b[i] then inc(dem);
 writeln(f,dem);
 end;
 close(f);
end;
2.1.2. Giải pháp 
Cách tư duy thứ 2 là hướng dẫn học sinh vận dụng thuật toán sắp xếp và tìm kiếm nhị phân để cải thiện thời gian cho chương trình như sau:
- Sắp xếp mảng A thành 1 dãy không giảm (bài giải tham khảo vận dụng thuật toán quicksort).
- Duyệt từng phần tử trong mảng B. Với mỗi phần tử B[i] ta thực hiện tìm kiếm nhị phân trên mảng A với cách tìm z>=A[mid].
Như vậy độ phức tạp của thuật toán sẽ là: m x O(logn)
Với n,m đạt giá trị max là 106 chương trình đảm bảo chạy tốt trong 1 giây.
Bài giải tham khảo:
const fi='ssdayso.inp';
 fo='ssdayso.out';
var n,m:longint;
 a,b:array[1..1000000] of longint;
procedure readfile;
var f:text; i:longint;
begin
 assign(f,fi);
 reset(f);
 readln(f,n,m);
 for i:=1 to n do read(f,a[i]);
 for i:=1 to m do readln(f,b[i]);
 close(f);
end;
procedure qs(l,r:longint);
var i,j,k,tg:longint;
begin
 i:=l; j:=r;
 k:=a[(l+r) div 2];
 repeat
 while a[i]<k do inc(i);
 while k<a[j] do dec(j);
 if i<=j then
 begin
 tg:=a[i];
 a[i]:=a[j];
 a[j]:=tg;
 inc(i);
 dec(j);
 end;
 until i>j;
 if l<j then qs(l,j);
 if i<r then qs(i,r);
end;
function tknp(z:longint):longint;
var l,r,mid,pos:longint;
begin
 l:=1; r:=n;
 while l<=r do
 begin
 mid:=(l+r) div 2;
 if a[mid]<=z then
 begin
 pos:=mid;
 l:=mid+1;
 end
 else r:=mid-1;
 end;
 exit(pos);
end;
procedure process;
var f:text; i,vt:longint;
begin
 assign(f,fo);
 rewrite(f);
 for i:=1 to m do
 if b[i]<a[1] then writeln(f,0)
 else
 begin
 vt:=tknp(b[i]);
 writeln(f,vt);
 end;
 close(f);
end;
BEGIN
 readfile;
 qs(1,n);
 process;
END.
2.2. Bài toán 2: Hẹn gặp	
Thành phố Gloaming (Hoàng hôn) nổi tiếng với đường dẫn vào công viên thành phố. Các bức tượng tuyệt đẹp theo chủ đề thần thoại Hy lạp – La mã đặt dọc theo con đường thẳng có một sức hút không cưỡng được với mọi khách du lịch. Còn khi những tia nắng cuối cùng trong ngày miễn cưỡng rời khỏi bầu trời thì sương mù dày đặc, như một tấm voan trắng mềm mại từ từ rũ xuống. Bây giờ đứng cách quá r mét là đã không nhìn thấy mặt nhau và các bức tượng trở thành nơi lý tưởng cho các đôi nam nữ thanh niên hẹn hò. 
James Bond cần gặp gấp 2 điệp viên nội tuyến của mình để nhận các mật báo khẩn. Không muốn 2 người này nhìn thấy nhau, Bond hẹn gặp mỗi người ở một bức tượng sao cho khoảng cách giữa chúng lớn hơn r. Trên đường có n bức tượng, bức tượng thứ i ở vị trí cách đầu con đường di mét i = 1 ÷ n, 1 ≤ d1< d2 < . . .< dn ≤ 109. 
Yêu cầu: Hãy xác định James Bond có bao nhiêu cách chọn địa điểm.
Dữ liệu vào: Vào từ file văn bản BAI3.INP:
Dòng đầu tiên chứa 2 số nguyên n và r (1 ≤ n ≤ 3×105, 1 ≤ r ≤ 109).
Dòng thứ 2 chứa n số nguyên d1, d2, . . ., dn.
Kết quả: Đưa ra file văn bản BAI3.OUT một số nguyên là số cách chọn địa điểm tìm được.
Ví dụ:
BAI3.INP
BAI3.OUT
4 4
1 3 5 8
2
Rằng buộc:
Có ½ số test tương ứng với ½ số điểm có n ≤ 104
Có ½ số test tương ứng với ½ số điểm có 104 < n ≤ 3×105
2.2.1. Thực trạng
Với cách tư duy thông thường học sinh sẽ khai báo mảng A lưu trữ vị trí di.
Sử dụng 2 vòng lặp for do để kiểm tra r + d[i] <d[j] thì dừng lại để cộng vào biến đếm.
Khi đó độ phức tạp của thuật toán sẽ là n2, mà theo giới hạn đầu bài 1 ≤ n ≤ 3×105 nên với n max thì số lượng phép toán phải thực hiện là: 3×105 x 3×105.
Nếu gặp test này thì chắc chắn chương trình không thể thực hiện trong 1 giây.
procedure process1;
var i,j:longint;
begin
dem:=0;
for i:=1 to n do
 for j:=i to n do
 if r+d[i]<d[j] then inc(dem,n-j+1);
end; 
2.2.2. Giải pháp
Cách tư duy thứ 2 là hướng dẫn học sinh vận dụng thuật toán tìm kiếm nhị phân để cải thiện thời gian (do dãy di đã sắp xếp theo thứ tự tăng dần) cho chương trình như sau:
Duyệt 1 vòng lặp for do từ 1 đến n, trong đó thực thi tìm kiếm nhị phân r+d[i].
Như vậy độ phức tạp của thuật toán sẽ là: n x O(logn)
Với n đạt giá trị max là 3 x 105 chương trình đảm bảo chạy tốt trong 1 giây.
Bài giải tham khảo:
program Hengap;
const fi='Gloaming.inp';
 fo='Gloaming.out';
var dem:int64;n,r:longint;
 d:array[1..300000] of longint;
procedure readfile;
var f:text; i:longint;
begin
 assign(f,fi);
 reset(f);
 read(f,n,r);
 for i:=1 to n do read(f,d[i]);
 close(f);
end;
function np(x,a,b:longint):longint;
var t,p,m:longint;
begin
 t:=a; p:=b;
 while t<=p do
 begin
 m:=(t+p)div 2;
 if d[m]=x then
 exit(m+1)
 else
 if d[m]<x then t:=m+1
 else p:=m-1;
 end;
 exit(t);
end;
procedure process;
var a,i,j:longint;
begin
 dem:=0;
 for i:=1 to n do
 begin
 a:=np(r+d[i],i,n);
 if a>n then break;
 inc(dem,n-a+1);
 end;
end;
procedure writefile;
var f:text;
begin
 assign(f,fo);
 rewrite(f);
 write(f,dem);
 close(f);
end;
BEGIN
 readfile;
 process;
 writefile;
END.
2.3. Hiệu quả của sáng kiến kinh nghiệm đối với hoạt động giáo dục, với bản thân, đồng nghiệp và nhà trường
- Sau khi áp dụng sáng kiến kinh nghiệm này cho đội tuyển HSG trường THPT Hàm Rồng năm học 2017-2018 từ tháng 12/2017 đến tháng 2/2018 đạt được kết quả như sau:
* Đối với học sinh: 100% học sinh đội tuyển khi gặp các bài toàn cùng dạng đã nhận thức được thực trạng không giải quyết hết test chương trình, đồng thời biết vận dụng thuật toán sắp xếp và tìm kiếm nhị phân để giải quyết bài toán.
* Đối với bản thân, đồng nghiệp:
- Nhận thức được cách giải quyết bài toán của đề thi học sinh giỏi Tin học theo hướng mới để đạt được 100% test khi áp dụng thuật toán sắp xếp và tìm kiếm nhị phân trên 1 lớp các bài toán cùng dạng.
- Chia sẻ cách thức vận dụng trong toàn bộ nhóm Tin trường THPT Hàm Rồng, đồng thời cùng thực hiện trên 1 lớp các bài toán để đưa ra cách thức áp dụng tối ưu nhất.
* Đối với nhà trường: Chất lượng học sinh đội tuyển học sinh giỏi của trường được nâng cao.
3. Kết luận, kiến nghị
Với cách tư duy thông thường của học sinh khi giải quyết các bài toán trong đề thi HSG Tin học 11 thì rất khó giải quyết khi gặp các Test lớn về giá trị và về mặt thời gian chương trình sẽ không tối ưu. Do đó học sinh nên vận dụng 2 thuật toán sắp xếp và tìm kiếm nhị phân để cải thiện chương trình. Tuy nhiên, không phải bài toán nào ta cũng áp dụng 2 thuật toán này mà phải tùy vào nội dung bài toán để có hướng áp dụng cho phù hợp. Việc này đòi hỏi học sinh phải được tiếp xúc với rất nhiều các bài toán tương tự, khi đó kỹ năng áp dụng 2 thuật toán vào các bài tập mới hoàn thiện.
Mặc dù bản thân đã cố gắng nhiều, song trong đề tài còn nhiều khiếm khuyết, tôi rất mong nhận được sự đóng góp ý kiến của các đồng nghiệp, để được hoàn thiện hơn và đạt hiệu quả trong giảng dạy và học tập của học sinh./.
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ
Thanh Hóa, ngày 05 tháng 5 năm 2018
Tôi xin cam đoan đây là SKKN của mình viết, không sao chép nội dung của người khác.
 Người viết
Nguyễn Thành Nam