Mục lục
1. Mở đầu...............................................................................................................2
1.1. Lý do chọn đề tài.........................................................................................2
1.2. Đối tượng và phạm vi nghiên cứu...............................................................2
1.3. Phương pháp nghiên cứu.............................................................................2
2. Nội dung sáng kiến kinh nghiệm.......................................................................3
2.1. Bài toán 1:...................................................................................................3
2.1.1. Thực trạng.............................................................................................3
2.1.2. Giải pháp..............................................................................................4
2.2. Bài toán 2:...................................................................................................5
2.2.1. Thực trạng.............................................................................................6
2.2.2. Giải pháp..............................................................................................6
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........................................................................9
3. Kết luận, kiến nghị..........................................................................................10

1


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.

2
3
4

SSDAYSO.OUT
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]
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]
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ò.
5


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
44
1358

BAI3.OUT
2



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
- 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.

8


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, để