PHẦN I: MỞ ĐẦU
1. Lí do chọn đề tài
Qua thực tiễn giảng dạy bộ môn tin học ở THPT, đặc biệt quá trình bồi dưỡng học
sinh dự thi chọn HSG tỉnh tôi nhận thấy để đạt được điểm tối đa trong các kỳ thi, ngoài
việc tìm ra thuật toán học sinh còn phải tìm được thuật toán giải quyết bài toán nhanh,
đáp ứng yêu cầu của tất cả các bộ test khi chấm.
Trong quá trình giảng dạy, tôi thấy có nhiều bài toán học sinh có thể dễ dàng tìm ra
cách giải, tuy nhiên nó chỉ có hiệu quả đối với các trường hợp test đơn giản. Đặc biệt với
các bài toán tìm kiếm tối ưu, nhiều trường hợp bài toán chỉ giải quyết được hết các yêu
cầu khi áp dụng thuật toán tìm kiếm nhị phân.
Nội dung thuật toán tìm kiếm nhị phân đã được trình bày ở Sách giáo khoa Tin học
10, phần thuật toán và Sách giáo khoa tin học 11 khi giảng dạy về Pascal. Tuy nhiên nếu
chỉ nắm bắt được những nội dung này thì học sinh chỉ áp dụng được một bài toán đơn
giản là tìm số nguyên k trong 1 dãy số đã sắp xếp. Hiện nay thì tài liệu tham khảo để
hướng dẫn việc áp dụng thuật toán tìm kiếm nhị phân cũng rất ít. Trong quá trình tham
gia các diễn đàn, giải bài tập, đề thi trên mạng, tôi đã tổng hợp được một số cách nhận
dạng và kỷ thuật cài đặt thuật toán tìm kiếm nhị phân để giải quyết các bài toán tìm kiếm
một cách tối ưu – Kỷ thuật “chặt nhị phân”. Chính vì những lý do trên mà tôi lựa chọn đề
tài Kỷ thuật “chặt nhị phân” trong bài toán tìm kiếm để tìm hiểu và vận dụng vào quá
trình bồi dưỡng học sinh giỏi của mình.
2. Mục đích nghiên cứu
Trong phạm vi đề tài của mình, tôi muốn nghiên cứu về kỷ thuật “chặt nhị phân”.
Từ việc tìm hiểu một bài toán đơn giản trong sách giáo khoa để linh hoạt cài đặt và giải
quyết các bài toán tìm kiếm một cách tối ưu nhất. Với các đối tượng học sinh khá giỏi sẻ
biết cách nhận dạng và áp dụng kỷ thuật này để giải quyết các bài toán tìm kiếm với độ
phức tạp thấp nhất, đáp ứng hết tất cả các yêu cầu về giới hạn dữ liệu vào. Cũng qua đề
tài này, tôi muốn được cùng các đồng nghiệp nghiên cứu, tìm hiểu, trau dồi chuyên môn,
nghiệp vụ và nhất là niềm đam mê lập trình.
3. Đối tượng nghiên cứu
- Kỷ thuật chặt nhị phân và cách áp dụng để giải các bài toán tìm kiếm.
- Phân tích, đánh giá độ phức tạp thuật toán và so sánh với cách giải khác để đưa ra

việc áp dụng thuật toán này.
- Về thực tiễn: Sử dụng đề tài làm tài liệu tham khảo để giảng dạy bộ môn tin học,
đặc biệt là quá trình bồi dưỡng, luyện thi học sinh giỏi.
PHẦN II. GIẢI QUYẾT VẤN ĐỀ
1. Cơ sở lý luận
Bản chất của kỷ thuật “chặt nhị phân” là thuật toán tìm kiếm nhị phân được trình
bày ở phần thuật toán, sách giáo khoa tin học lớp 10. Bài toán cơ sở như sau:
Cho dãy số nguyên A tăng dần và 1 số nguyên K. Đưa ra chỉ số i mà Ai=k hoặc
thông báo không có số hạng nào của dãy A có giá trị bằng k.
- Ý tưởng: Sử dụng tính chất dãy A là dãy số tăng dần, ta tìm cách thu hẹp nhanh
phạm vi tìm kiếm sau mỗi lần so sánh khóa với số hạng được chọn. Để làm điều đó ta
chọn số hạng Agiua ở giữa dãy để so sánh với K, trong đó Giua=[N+1] div 2.
Khi đó chỉ xảy ra một trong ba trường hợp sau:
- Nếu Agiua=k thì giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.
- Nếu Agiua>k thì việc tìm kiếm tiếp theo chỉ xét trên dãy A 1, A2, …, Agiua-1 (Phạm vi
tìm kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trước đó).
- Nếu Agiua10 3 mà thuật
toán tìm kiếm tuần tự bị bắt các lỗi chạy quá thời gian quy định. Tuy nhiên chỉ áp dụng

2


tìm kiếm nhị phân khi dãy đã sắp xếp nên chúng ta thường sử dụng thuật toán sắp xếp
nhanh (Qsort) với độ phức tạp O(NlogN) để sắp xếp dãy trước đó.
2. Cơ sở thực tiễn.
Hầu hết các học sinh sau khi học xong thuật toán tìm kiếm nhị phân chỉ áp dụng

4
2
3
5
11

Slbehon.out
1
1
2
5

3


Cách 1: Nhìn qua đây là một bài toán đơn giản và học sinh thường giải theo cách
sau đây: Xây dựng 1 hàm để đếm số lượng phần tử trong mảng A có giá trị bé hơn M,
hàm này được viết thường là duyệt tuần tự từ A 1 đến AN, so sánh Ai với M và tăng biến
lưu giá trị đếm. Chương trình được viết như sau:
program slbehonc1;
const fi='slbehon.inp';
fo='slbehon.out';
nmax=100000;
var
a:array[1..nmax] of longint;
n,m,q:longint;
f,f1:text;
function dem(m:longint):longint;
var i:longint;
begin



Cách 2: Để giải quyết vấn đề này hiệu quả chúng ta phải giải quyết nó trong
O(Nlogn) thời gian phức tạp. Ta thực hiện sắp xếp mảng đã cho bằng thuật toán Qsort và
áp dụng kỷ thuật “chặt nhị phân” để xác định chỉ số cuối cùng của phần tử nhỏ hơn M.
program So_luong_be_hon;
const fi='slbehon.inp';
fo='slbehon.out';
nmax=100000;
var
a:array[1..nmax] of longint;
n,m,q:longint;
f,f1:text;
procedure qsort(l,h:integer);
var i,j,tam,k:longint;
begin
i:=l;
j:=h;
k:=a[(l+h) div 2];
repeat
while a[i]k do dec(j);
if i
var i:integer;
x:longint;
begin
assign(f1,fo);
rewrite(f1);
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do read(f,a[i]);
qsort(1,n);
readln(f);
readln(f,q);
for i:=1 to q do
begin
readln(f,x);
writeln(f1,tknp(x));
end;
end;
begin
doc;
close(f1);
end.
Bài 2. Cho 1 dãy N số khác nhau. Hãy tìm xem có bao nhiêu cặp số có chênh lệch
là k đơn vị.
Dữ liệu vào: Tệp ‘chenhlech.inp’:
- Dòng đầu tiên là N - số lượng dãy số và số nguyên K (N≤105, K≤109)
- Dòng tiếp theo chứa N số nguyên trong dãy. (A[i] ≤ 109)
Dữ liệu ra: Tệp ‘chenhlech.out’
- Gồm một số duy nhất là số cặp có độ chênh lệch k.
Capso.inp

for i:=1 to n do read(f,a[i]);
end;
begin
doc;
dem:=0;
for i:=1 to n-1 do
for j:=i+1 to n do
if abs(a[i]-a[j])=k then inc(dem);
assign(f,fo);
rewrite(f);
writeln(f,dem);
close(f);
end.
Chương trình trên có độ phức tạp là O(N 2). Với giới hạn input của bài toán là
(N≤105) thì chương trình trên không thực hiện được với test tối đa.
Cách 2: Sử dụng kỷ thuật “chặt nhị phân”. Đầu tiên ta sắp xếp dãy tăng dần bằng
Qsort. Tiếp theo ta duyệt dãy A. Tại Ai, nếu hàm TKNP(A[i]-k)=true thì ta tăng biến đếm
(tìm được 1 số có chênh lệch k so với A[i]). Độ phức tạp O(NlogN).
program capso;
const fi='capso.inp';
fo='capso.out';
nmax=100000;
var
f:text;
n,k,dem:longint;
a:array[1..nmax] of longint;
procedure doc;
var i:longint;
begin
assign(f,fi);

var d,c,g:longint;
begin
d:=1;
c:=n;
while d
23

tcds.out
0

Cách 1: Thông thường học sinh sẻ nghĩ ngay đến cách duyệt 2 vòng For như sau:
For i:=1 to n do
begin
For j:=1 to n do
Tong:=abs(b[i]+c[j]);
If tong
dec(j);
end;
until (i>j);
if l
if abs(x1+b[i])
begin
doc;
max:=0;
xuly;
assign(f,fo);
rewrite(f);
writeln(f,max);
close(f);
end.
Cách 2: Sử dụng thuật toán chặt nhị phân. Gọi a[z] là số lớn nhất trong bộ 3 số a[i],
a[j], a[z]. Tìm kiếm nhị phân số a[z] sao cho tổng 3 số
repeat
while a[i]k do dec(j);
if ij;
if il then qsort(l,j);
end;
procedure xuly;
var i,j,z:longint;
begin
for i:=1 to n-2 do
for j:=i+1 to n-1 do
begin
z:=tknp(i,j);
if z=0 then break
else
if (a[i]+a[j]+z>max) and (a[i]+a[j]+z
End;
End;
-

Trường hợp tìm giá trị lớn nhất
Procedure chat_nhi_phan;
Var dau,cuoi,giua:longint;
Begin
Dau:=1;
Cuoi:=n;
While dau
16


fo='mangmoi.out';
var B:array[1..nmax,1..nmax] of longint;
n,m,i,j,max1,min1,cl:longint;
a:array[1..nmax] of longint;
f:text;
procedure doc;
var i,j:longint;
begin
assign(f,fi);
reset(f);
readln(f,n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(f,b[i,j]);
readln(f);
end;
end;
procedure qsort(k,l,h:integer);
var i,j,tam,x:longint;
begin
i:=l;
j:=h;
x:=b[k,(l+h) div 2];
repeat
while b[k,i]x do dec(j);

end;

end;
function timmin(i,x:longint):longint;
var dau,cuoi,k1:longint;
begin
dau:=1;
cuoi:=m;
while daux then cuoi:=k1-1
else
begin
dau:=k1+1;
timmin:=b[i+1,k1];
end;
end;
end;
function min(x,y:longint):longint;
begin
if x
23
2
2
4

1≤ A[i] ≤ 106

‘Thutukeo.out’
1
2

Ghi chú
Hộp đầu tiên sẽ có các viên kẹo thứ tự: 1, 2
Hộp thứ hai sẽ có các viên kẹo chỉ số: 3, 4, 5

Ý tưởng: Xây dựng mảng S với ý nghĩa S[i] là tổng các phần tử từ A[1] đến A[i].
Thực hiện tìm kiếm nhị phân trên mảng S.
program chiso_keo;
const nmax=100000;
fi='thutukeo.inp';
fo='thutukeo.out';
var a:array[1..nmax] of longint;
n,q,x:longint;
s:array[0..nmax] of int64;
f,f1:text;
function tknp(x:longint):longint;
var d,c,k:longint;
begin
d:=1;
c:=n;

begin
assign(f1,fo);
rewrite(f1);
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do
begin
read(f,a[i]);
s[i]:=s[i-1]+a[i];
end;
readln(f);
readln(f,q);
for i:=1 to q do
begin
readln(f,x);
writeln(f1,tknp(x));
end;
close(f1);
end;
begin
s[0]:=0;
doc_xuly;
end.
Độ phức tạp: O(N+Q*log(N))
Bài 3. Cho N điểm nằm trên mặt phẳng, điểm thứ i nằm ở tọa độ (xi, yi), bạn cần
phải trả lời q truy vấn.Trong lần truy vấn thứ i, bạn sẽ được cho một số nguyên ri, và xem
bạn vẽ một vòng tròn trung tâm tại gốc (0,0) với bán kính ri, hãy cho biết số điểm nằm
20


program sodiem;
const
fi='sodiem.inp';
fo='sodiem.out';
nmax=100000;
var
f,f1:text;
n,t,i,q:longint;
b:array[1..nmax] of int64;
p:array[1..nmax] of real;
function tknp(x:int64):int64;
var d,c,k:longint;
begin
d:=1;
c:=n;
if p[n]
for i:=1 to n do
begin
readln(f,x,y);
p[i]:=sqrt(x*x+y*y);
end;
readln(f,q);
for i:=1 to q do
begin
22


readln(f,t);
b[i]:=t;
end;
end;
begin
assign(f1,fo);
rewrite(f1);
doc;
qsort(1,n);
for i:=1 to q do writeln(f1,tknp(b[i]));
close(f1);
end.
Bài 4. Cho 1 xâu S chỉ chứa các ký tự in thường ['a'-'z'] và 1 số nguyên K. Hãy tìm
các xâu con liên tiếp của S có trọng lượng bằng K.
Trọng lượng của 1 ký tự được tính như sau: ['a']=1; ['b']=2; ['c']=3,…['z']=26.
Trọng lượng của xâu S được tính là tổng trọng lượng các ký tự có trong xâu S.
Dữ liệu đầu vào: Tệp ‘timxaucon.inp’:
Dòng đầu tiên chứa số lượng các trường hợp cần kiểm tra T. Với mỗi test dữ liệu
được cho trên 2 dòng, dòng đầu là số nguyên K và dòng sau là xâu S.



reset(f);
readln(f,t);
for i:=1 to t do
begin
readln(f,cs[i]);
readln(f,luus[i]);
end;
end;
procedure taobang(s:ansistring);
var i,x:longint;
begin
s1[0]:=0;
for i:=1 to length(s) do
begin
x:=ord(s[i])-96;
s1[i]:=s1[i-1]+x;
end;
end;
function tknp(x:longint):boolean;
var d,c,k:longint;
begin
tknp:=false;
d:=1;
c:=n;
while d
chỉ số x1, x2, ..., xk, thì giá của sản phẩm xj là bxj + xj* k với 1 ≤ j ≤ k. Nói cách khác,
giá của một mặt hàng bằng với giá căn bản cộng với chỉ số nhân với hệ số k.
Tân muốn mua càng nhiều đồ càng tốt mà không phải trả nhiều tiền hơn một số SP.
Lưu ý rằng mỗi món hàng chỉ được mua 1 lần. Hãy giúp Tân chọn cách mua với nhiều
mặt hàng nhất.
Dữ liệu vào: Tệp ‘muahang.inp’
- Dòng đầu tiên chứa hai số nguyên n và SP (1 ≤ n ≤ 105 và 1 ≤ SP ≤ 109) - số lượng
các mặt hàng trên và số tiền tối đa Tân có thể mua
- Dòng thứ hai chứa n số nguyên b1, b2, ..., bn(1 ≤ bi ≤ 105) - giá trị cơ bản của các
mặt hàng.
Dữ liệu ra: Tệp ‘muahang.out’
- In hai số nguyên k, T là số lượng tối đa các hàng mà Tân có thể mua và tổng chi
phí tối thiểu để mua những mặt hàng k.
Muahang.inp
3 11
235

Muahang.out
2 11

Giải thích test
Trong ví dụ này, Tân không thể lấy cả ba mặt hàng
bởi vì giá của mỗi mặt hàng lần lượt là [5, 9, 14] và
tổng chi phí của nó 28. Nếu Tân chỉ mua hai mặt
hàng, thì chi phí sẽ là [4, 7] và tổng chi phí là 11.

program muahang;
const fi='muahang.inp';
fo='muahang.out';
nmax=10000;