SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ

TRƯỜNG THPT TRIỆU SƠN 3

SÁNG KIẾN KINH NGHIỆM

GIẢI MỘT SỐ BÀI TOÁN BẰNG PHƯƠNG PHÁP TÌM
KIẾM NHỊ PHÂN GIÚP NÂNG CAO HIỆU QUẢ BỒI
DƯỠNG HỌC SINH GIỎI

Người thực hiện: Lê Thị Quỳnh
Chức vụ: Giáo viên
Đơn vị công tác: Trường THPT Triệu Sơn 3
SKKN thuộc lĩnh vực (môn): Tin học

THANH HOÁ NĂM 2019


MỤC LỤC

1. MỞ ĐẦU..........................................................................................................1
1.1. Lý do chọn đề tài........................................................................................1
1.2. Mục đích nghiên cứu..................................................................................1
1.3. Đối tượng nghiên cứu.................................................................................1
1.4. Phương pháp nghiên cứu............................................................................1
2. NỘI DUNG......................................................................................................3
2.1. Cơ sở lý luận...............................................................................................3
2.1.1. Nội dung thuật toán..............................................................................3
2.1.2. Nội dung chương trình bằng NNLT PASCAL.....................................3
2.1.3. Độ phức tạp thuật toán.........................................................................3
2.2. Thực trạng của vấn đề cần giải quyết ........................................................4

1.2. Mục đích nghiên cứu.
Với lý do chọn đề tài đã trình bày ở trên, tôi mong muốn đề tài của mình sẽ
giúp đỡ phần nào các khó khăn khi nhận dạng bài toán tìm kiếm nhị phân trong
quá trình ôn luyện học sinh giỏi.
- Khảo sát, đánh giá được thực trạng việc bồi dưỡng học sinh tham gia thi học
sinh giỏi cấp Tỉnh của trường Trung học phổ thông Triệu Sơn 3.
- Nhìn nhận, giải quyết một số bài toán bằng phương pháp tìm kiếm nhị phân.
1.3. Đối tượng nghiên cứu.
- Thuật toán tìm kiếm nhị phân.
- Một số bài tập thi HSG các cấp.
- Sự tư duy, ý thức học tập của học sinh ôn thi học sinh giỏi.
1.4. Phương pháp nghiên cứu.
Để thực hiện đề tài này, tôi đã sử dụng các phương pháp:
- Phương pháp nghiên cứu xây dựng cơ sở lí thuyết: Cơ sở lý thuyết là phương
pháp tìm kiếm nhị phân, một số bài toán trong các đề thi các cấp; Sự hứng thú
trong giờ học môn Tin học và ý thức tự học của học sinh đối với môn học.

1


- Phương pháp điều tra khảo sát thực tế, thu thập thông tin: Thông qua kết quả
điều tra mức độ hiểu về thuật toán tìm kiếm nhị phân của học sinh lớp 11 trường
THPT Triệu Sơn 3.
- Phương pháp thống kê, xử lý số liệu: Trên cơ sở các kết quả đạt được, thống
kê các số liệu, xử lí số liệu để so sánh giữa nhóm thực nghiệm và đối chứng.

2


2. NỘI DUNG

Mid := (L + R) div 2;
if K[Mid] = X then
Begin
TK_NhiPhan := Mid;
exit;
end
else if K[Mid] < X then L := Mid + 1
else R := Mid – 1;
end;
TK_NhiPhan := 0;
End;

2.1.3. Độ phức tạp thuật toán.
Người ta chứng minh được độ phức tạp tính toán của thuật toán tìm kiếm
nhị phân trong trường hợp tốt nhất là O(1), trong trường hợp xấu nhất là
O(logN). Phương pháp tìm kiếm nhị phân chỉ thực hiện được với dãy đã được
sắp xếp, nên nếu dãy chưa sắp xếp thì cần phải tính đến thời gian cho việc sắp
xếp lại dãy trước khi áp dụng tìm kiếm nhị phân.
3


2.2. Thực trạng của vấn đề cần giải quyết .
Nhiều học sinh có thể hiểu thuật toán tìm kiếm nhị phân nhưng việc vận
dụng để giải một bài toán bằng phương pháp này thì thực sự chưa hiệu quả, chưa
nhìn nhận được cách giải bài toán bằng phương pháp tìm kiếm nhị phân, nhất là
các bài toán dạng tìm kiếm nhị phân “ẩn” hay nói cách khác là dạng tìm kiếm
nhị phân theo kết quả.
Trong nội dung thi học sinh giỏi Tin học các cấp, có nhiều bài thường có
thể giải với nhiều cách khác nhau, trong các cách đó thì không phải cách nào
cũng có thể giải quyết hết các bộ dữ liệu giới hạn của bài toán, việc hướng đến

tối thiểu xe taxi cần thiết để chở tất cả học sinh đến nơi.
Ví dụ:

TAXI.INP

TAXI.OUT

5
4
12433
Hướng dẫn giải
Bài này có thể giải theo hai cách như sau:
Cách 1: Tư duy theo kiến thức toán học. Kết quả bài toán là tổ hợp của các
trường hợp có thể xảy ra của bài toán. Theo cách làm này, học sinh khó lấy hết
các test của bài vì nếu không cẩn thận sẽ không xét hết các trường hợp có thể
xảy ra của bài toán. Thực tế là đã có rất nhiều học sinh bị mất điểm ở bài này
theo cách làm như vậy.
Độ phức tạp của thuật toán theo cách này là O(n)
Cách 2. Tìm kiếm nhị phân:
Bài này cần tìm kiếm nhị phân trên dãy dữ liệu của đề bài, nhưng trước
khi tìm kiếm nhị phân, cần sắp xếp lại dữ liệu của đề bài thành dãy không giảm.
Độ phức tạp của thuật toán theo cách này là O(nlogn)
Bước 1. Sắp xếp dãy số nguyên đã cho theo thứ tự không giảm (sắp xếp mảng
a);
Bước 2. dau←1; cuoi ← n;
Bước 3. Nếu a[dau] +a[cuoi]
j:=j-1;
end;
until i>j;
if l
là theo cách này là O(NlogN):
Gọi T[i] là tổng của các số A[1] đến A[i].
Vì A[i] là các số dương nên dãy T là dãy tăng dần.
Khi đó ta sẽ tiến hành tìm kiếm nhị phân trên dãy T như sau:
* Xét T[i]:
d = 1, c = i-1,
g = (d + c) div 2
Nếu T[i] – T[g] >= S thì kq = min(kq, i – g) và tìm kq tiếp tục ở đoạn bên
phải T[g]
Nếu T[i] – T[g] < S thì tìm kq ở đoạn bên trái T[g].
Dưới đây là code của bài toán bằng cách tìm kiếm nhị phân:

7


Program SUB;
const fi='SUB.IN0';
fo='SUB.OU0';
nmax = 100000;
oo = 100001;
Var A,T:array[0..nmax] of longint;
N,S,kq:longint;
F:text;
procedure doc;
var i:longint;
Begin
assign(F,fi);
reset(F);
T[0] := 0;
Readln(F,N,S);

8


end;
procedure ghi;
Begin
assign(F,fo);
rewrite(F);
if kq = oo then write(F,0)
else Write(F,kq);
close(F);
end;
BEGIN
doc;
xuly;
ghi;
END.
Cách 3: Bài toán có thể giải với độ phức tạp là O(N).
Xét tổng đoạn T = A[d] + A[d+1] + A[d+2] + …+ A[c]
Nếu T < S thì cần bổ sung thêm giá trị của A[c+1] vào tổng để T có thể >= S
Nếu T
Vậy tổng có 22 +21 chữ số = 23 - 2
444
447
474
477
744
747
774
777 Có 8 số có 3 chữ số
3
2
1
4
Với mỗi k=1,2,3...thì Vậy tổng có 2 + 2 + 2 =2 -2
tổng
số lượng các số may
mắn
là 22 -2 , 23 -2, 232, ...Vậy, nếu gọi vị trí của số đó là n thì số thứ n sẽ luôn lớn hơn một số có dạng
2x -2, tức là: 2x -2 ≤ n≤ 2x+1 -2. Ta sẽ duyệt x chạy từ 1 đến 30 (vì 2 31=
1073741824), nếu n nằm giữa khoảng trên thì tìm được 2 điểm đầu cuối
Vì vậy, vị trí đầu cuối để chặt nhị phân là 2x -2 và 2x+1 -2.
Thứ hai, ta thấy các chữ số luôn chia thành hai nửa, số 4 và số 7 nên ta
tìm kiếm nhị phân đoạn này thì ta sẽ tìm ra được chữ số.
Độ phức tạp của thuật toán theo cách này là O(log2x), với 1≤ x≤30
Dưới đây là code của bài toán bằng cách tìm kiếm nhị phân:
Const Fi='luckynum.inp';
Fo=' luckynum.out';
Var F1,F2:text;
F:array[1..30] of longint;
N,i,dau,cuoi,giua,dem:longint;

if N
procedure doc;
var i:longint;
Begin
assign(f,fi); reset(f);
readln(f,N);
for i:=1 to N do read(f,A[i]);
12


close(f);
end;
function ok(k:longint):boolean;
var i,j:longint;
Begin
fillchar(dem,sizeof(dem),0);
for i:=1 to k do inc(dem[A[i]]);
for i:=K+1 to N do
if dem[A[i]]=0 then dec(dem[A[i-k]])
else if A[i] A[i-k] then
Begin
inc(dem[A[i]]);
dec(dem[A[i-k]]);
end;
ok := false;
for i:=-1000 to 1000 do
if dem[i] > 0 then
Begin
ok := true;
exit;
end;

END.
Cách 2: Có thể sử dụng thuật toán với độ phức tạp là O(N) để giải quyết bài
toán.
Ta thấy 1 trong k số đầu tiên của dãy sẽ là số k – ngẫu nhiên.
Vì vậy sẽ dùng thêm mảng dem[-1000 .. 1000] để đếm tần số xuất hiện các của
k phần tử đầu tiên trong dãy, khi đó dem[A[i]] > 0 nghĩa là A[i] có thể là số k –
ngẫu nhiên.
Duyệt 1 vòng lặp: i từ k+1 đến N:
+ if dem[A[i]] = 0 then dec(dem[A[i-k]])
{Nếu số A[i] không xuất hiện trong k số từ A[i – k] tới A[i – 1] thì A[i] không là
số k ngẫu nhiên – thì giảm dd[A[i-k]] 1 đơn vị để loại số A[i-k] này ra khỏi dãy
có k số liên tiếp}
+ if (dem[A[i]] > 0) and (dem[A[i]] dem[A[i-k]] then
Begin
inc(dem[A[i]]);
dec(dem[A[i-k]]);
end;
{Nếu A[i] xuất hiện trong dãy A[i – k] tới A[i – 1] thì A[i] có thể là số k – ngẫu
nhiên và trong dãy A[i-k+1] đến A[i] có A[i] thì tăng dem[A[i]]}
Duyệt lại lần nữa để kiểm tra xem có dd[i] > 0 hay không? Nếu có thì dãy có số
k – ngẫu nhiên.
2.3.2. Phân loại các dạng thực hiện tìm kiếm nhị phân.
Để biết một bài toán nào đó có thể sử dụng thuật toán tìm kiếm nhị phân
để giải quyết hay không thì có thể qui về hai dạng như sau:
2.3.2.1. Dạng 1: Tìm kiếm nhị phân trên dãy (mảng) có sẵn.
Đối với dạng bài này sẽ đơn giản hơn vì dãy (mảng) các phần tử cần được
sắp xếp lại (hoặc đã được sắp xếp sẵn), yêu cầu bài toán cần chỉ ra kết quả có
thể xuất hiện trong dãy hay không. Với n lớn hơn 10 4, thì không thể duyệt 2
vòng để tìm kết quả vì sẽ quá thời gian qui định (1s). Khi đó, có thể nghĩ đến sắp
xếp bằng quick-sort và tìm kiếm nhị phân. Cụ thể:

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
Ý tưởng: (Nội dung này tham khảo trong tài liệu tập huấn giáo viên 2017 )
- Dùng một vòng lặp For – do để duyệt i từ 1 đến n-1, trong đó với mỗi vị
trí i thì ta tìm kiếm nhị phân để tìm địa điểm j xa nhất thỏa mãn r+di < dj.
Ví dụ 3. (Nguồn: Đề bài hội thi chọn GVG Tỉnh Thanh Hóa năm học 20132014)
Xét dãy số nguyên dương khác nhau từng đôi một a 1, a2,...., an. Với số
nguyên x cho trước. Hãy xác định số cặp (ai, aj) thỏa mãn các điều kiện:
- ai +aj =x
- 1 ≤ i
16


6
100 89 90 101 91 99

11

Ý tưởng: (Nội dung này tham khảo trong tài liệu tập huấn Sở GD&ĐT )
+ Sắp xếp tăng dần theo chiều cao
+ Duyệt từ i từ 1 đến n-1 với mỗi vị trí i thì ta chặt nhị phân để tìm người
có vị trí j xa nhất mà thỏa mãn 9*h[j] <= 10*h[i]. Nếu j > i thì ta được thêm số
cặp là j-i.
2.3.2.2. Dạng 2: Tìm kiếm nhị phân theo kết quả.
Nhiều người thường dùng cụm từ “chặt nhị phân ẩn” để nói về cách làm
này. Đây là cách dự đoán vào kết quả có thể xảy ra của bài toán thuộc khoảng
nào, từ đó giới hạn giá trị đầu, giá trị cuối và tìm kiếm nhị phân trên khoảng giá
trị đó để đưa ra kết quả của bài toán. Một số bài toán cụ thể như sau:
Ví dụ 1. Nguồn: />Có N cây gỗ, có chiều cao lần lượt là A[1], A[2], .., A[n]. Bạn cần lấy một
lượng gỗ độ cao tối thiểu là M bằng cách chặt từ N cây theo cách như sau: chặt
tất cả những phần thừa của các cây có độ cao lớn hơn H. Hãy tìm giá trị H lớn
nhất để bạn có thể lấy được lượng gỗ tối thiểu là M.
Dữ liệu: Vào từ file văn bản PTIT126J.INP
+ Dòng 1 chứa 2 số nguyên N (1
Dữ liệu: Vào từ file P145SUMG.INP gồm:
+ Dòng đầu tiên gồm 2 số nguyên N và M, lần lượt là số quầy gửi đồ và
số vị khách (N
Xếp giải
10.0
KK
8.5
Không
6.5
Không
9.0
Không

Năm học
2015-2016
2016-2017

Kết quả thi HSG
Năm học
Điểm
Xếp giải
1
Đào Công Cường
11D3
12.0
KK
2017-2018
2
Lê Thị Hương
11D3
15.0
Ba
3

Qua việc thực hiện đề tài, tôi nhận thấy tìm kiếm nhị phân là một phương
pháp cần thiết trong việc dạy học lập trình nói chung và ôn thi học sinh giỏi nói
riêng. Với nội dung được cung cấp trong sách giáo khoa lớp 10 thì chỉ mang tính
gợi mở, các em cần được rèn luyện thông qua các bài tập để có thể hiểu rõ bản
chất của thuật toán, biết vận dụng để giải quyết các bài toán bằng phương pháp
này hiệu quả thực sự.
Việc áp dụng thuật toán này cũng đã đem lại hiệu quả thực sự trong việc
ôn thi học sinh giỏi tại đơn vị THPT Triệu Sơn 3: Học sinh tự tin hơn, học tập
tích cực hơn, chủ động hơn, khả năng tư duy tốt hơn và có kết quả cao hơn.
3.2. Kiến nghị.
Đối với giáo viên, phải không ngừng tự học, tự bồi dưỡng, tham khảo các
ý kiến chia sẻ từ đồng nghiệp nhất là về các bài tập, các đề thi học sinh giỏi các
cấp. Từ đó vận dụng vào công tác bồi dưỡng học sinh giỏi đạt hiệu quả cao nhất.
Đối với các cấp lãnh đạo, cần tổ chức hội thảo chuyên đề cho giáo viên bộ
môn Tin học hàng năm để giáo viên có dịp được trao đổi, học hỏi kinh nghiệm,
tìm ra những giải pháp, biện pháp tốt, ý tưởng hay giúp nâng cao chất lượng dạy
học nói chung và ôn thi học sinh giỏi nói riêng.

XÁC NHẬN

Thanh Hóa, ngày 28 tháng 05 năm 2019

CỦA THỦ TRƯỞNG ĐƠN VỊ

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

LÊ THỊ QUỲNH



3.

Tên đề tài SKKN

Kết quả
Cấp đánh
đánh giá
giá xếp loại
xếp loại
(Phòng, Sở,
(A, B,
Tỉnh...)
hoặc C)
Sở GD&ĐT
C

Sử dụng sơ đồ tư duy nhằm
tạo hứng thú và nâng cao chất
lượng cho học sinh khi dạy
tiết 21 – bài tập, Tin học lớp
11.
Một số kinh nghiệm giáo dục Sở GD&ĐT
ý thức sử dụng Internet và kỹ
năng sống nhằm nâng cao
nhận thức và kết quả học tập
cho học sinh thông qua bài 9
và chương IV Tin học 10.
Hướng dẫn giải một số bài
Sở GD&ĐT