CHUYÊN ĐỀ 3. TÌM KIẾM SẮP XẾP
1. Thuật toán tìm nhị phân trên mảng
- Thuật toán tìm kiếm nhị phân có thể tìm phần tử có giá trị bằng X trên mảng đã được
sắp xếp một cách hiệu quả trong thời gian O(logn). Thuật toán như sau:
- Giả sử cần tìm trong đoạn a[L], a[L + 1],.a[H] với giá trị cần tìm kiếm là X, trước hết ta
xem xét với giá trị của phần tử nằm giữa dãy, mid = (L + H) div 2
+Nếu a[mid] < X thì có nghĩa là đoạn từ a[L] tới a[mid] chỉ chứa các phần tử có giá trị
X thì có nghĩa là đoạn từ a[mid] tới a[H] chỉ chứa các phần tử có giá trị >
X, ta tiến hành tìm kiếm tiếp với đoạn từ a[L] đến a[mid -1]
+ Nếu a[mid] = X thì việc tìm kiếm thành công (kết thúc quá trình tìm kiếm).
- Quá trình tìm kiếm sẽ thất bại nếu đến một bước nào đó, đoạn tìm kiếm là rỗng.
Khi đó (L>H). Hàm được viết như sau :
Function timnhiphan(x:longint;a:mang):integer;
var d,c,tam:longint;
begin
d:=1; c:=n; timnhiphan:=0;
while (d
a. Kỹ thuật đếm phân phối
- Trong trường hợp các phần tử a[1],a[2] ,...,a[n] là các số nguyên nằm trong khoảng từ -k
tới k (|k|≤106) ta có thuật toán đếm số lần xuất hiện của các giá trị từ -k tới k như sau:
Xây dựng dãy c[-k],…,c[0], c[1],..., c[k] , trong đó c[v] là số lần xuất hiện v trong dãy.
For v:= -k to k do c[v]:=0;
For i:=1 to n do c[a[i]]:=c[a[i]] + 1;
b. Kỹ thuật tìm các bộ hai (ai,aj) của dãy số thỏa điều kiện
- Nếu điều kiện là i≠j thì ta có tất cả là n*(n-1)/2 cặp
Ví dụ dãy số có 5 phần tử : 3 7 5 9 8
i = 1 → j = 2..5 tạo thành 4 cặp (3,7), (3,5), (3,9), (3,8)
i = 2 → j = 3..5 tạo thành 3 cặp (7,5), (7,9), (7,8)
i = 3 → j = 4..5 tạo thành 2 cặp (5,9), (5,8)
i = 4 → j = 5..5 tạo thành 1 cặp (9,8)
Tổng cộng có : 1 + 2 + 3 + 4 = 5*(5-1)/2 = 10 cặp.
Ta có thể dùng hai lồng nhau để duyệt hết các bộ với độ phức tạp O(n2).
For i:=1 to n-1 do
For j:=i+1 to n do <Câu lệnh>
- Nếu điều kiện là i, j bất kỳ thì ta có tất cả là n*n cặp
- Tuy nhiên tùy theo tính chất của từng bộ ta có thể dùng kĩ thuật đếm hoặc sắp xếp hoặc
duyệt từ hai phía, tìm kiếm nhị phân….
c. Kỹ thuật về dãy con, đoạn con của một dãy số
Đoạn con: Là tập hợp các phần tử liên tiếp của dãy số. Số đoạn con của một dãy là
n*(n+1)/2 đoạn.
Ví dụ dãy số có 5 phần tử : 3 7 5 9 8
i = 1 → đoạn con bắt đầu bằng a1 có 5 đoạn (3), (3,7), (3,7,5), (3,7,5,9), (3,7,5,9,8)
i = 2 → đoạn con bắt đầu bằng a2 có 4 đoạn (7), (7,5), (7,5,9), (7,5,9,8)
i = 3 → đoạn con bắt đầu bằng a3 có 3 đoạn (5), (5,9), (5,9,8)
i = 4 → đoạn con bắt đầu bằng a4 có 2 đoạn (9), (9,8)
i = 5 → đoạn con bắt đầu bằng a5 có 1 đoạn (8)


- Ta thường dùng dãy nhị phân tương ứng để biểu diễn các dãy con. Ví dụ với dãy trên :
Dãy nhị phân :

(0 0 0) ↔ (∅);

(0 0 1) ↔ (5);

(0 1 0) ↔ (7);

(0 1 1) ↔ (7,5);

(1 0 0) ↔ (3);

(1 0 1) ↔ (3,5);

(1 1 0) ↔ (3,7);

(1 1 1) ↔ (3,7,5);


BÀI TẬP CHƯƠNG III
Bài 1: Tìm giá trị lớn nhất
Cho n số nguyên al, a2,... an.
Yêu cầu: Tìm giá trị lớn nhất trong n số đó.
Dữ liệu vào từ file ‘MAXN.INP’

Tên file chương trình ‘MAXN.???’

■ Dòng đầu là số nguyên dương n (n

Bài 3: Tổng dãy số
Tên file chương trình ‘SUMARR.???’
Cho n số nguyên a1, a2,... an.
Yêu cầu: Tính tổng của n số đó.
Dữ liệu vào từ file ‘SUMARR.INP’
■ Dòng đầu là số nguyên dương n (n
-2-1
2-1

RECT.OUT
-2-2
3 1


Bài 6: Diện tích hình chữ nhật

Tên file chương trình ‘SRECT.???’

Trong mặt phẳng tọa độ Oxy cho n điểm, điểm thứ i có tọa độ (xj, yj).
Yêu cầu: Hãy tính diện tích hình chữ nhật nhỏ nhất có các cạnh song song với 2 trục tọa
độ bao cả n điểm đã cho. Các điểm đã cho có thể nằm trên cạnh của hình chữ nhật.
Dữ liệu vào từ file ‘SRECT.INP’
■ Dòng đầu chứa số nguyên dương n (n

Tên file chương trình ‘COORDSYS.???’

Trên trục số x’Ox cho n điểm nguyên (có hoành độ nguyên). Gọi các điểm nguyên đó lần
lượt có giá trị (hoành độ) là a1, a2,... an.
Yêu cầu: Hãy cho biết phải dùng ít nhất bao nhiêu đơn vị độ dài trên x’Ox. Ví dụ:

Dữ liệu vào từ file ‘COORDSYS.INP’
■ Dòng đầu chứa số nguyên dương n (n

MULMAX3.INP
6
7 -2 4 -1 6 5
Bài 11: Phần thưởng

MULMAX3.OUT
210

Tên file chương trình ‘PRIZE.???’

Để tập cho các cháu mẫu giáo làm quen với số và các khái niệm “lớn hơn", “bé hơn” cô
giáo chuẩn bị n hộp giấy, bên ngoài hộp giấy thứ i ghi số nguyên ai. Các số ghi ngoài hộp
khác nhau từng đôi một. Các hộp được bỏ vào một túi ni lông to sẫm màu để không đọc
được số từ bên ngoài. Đến giờ học toán cô giáo cho các em lần lượt lên bàn cô, mỗi em
lấy ra hai hộp, sau đó bỏ lại vào túi hộp có số nhỏ hơn và giữ cho mình hộp kia. Lớp học
có tất cả n-1 em. Đứng quan sát, cô giáo rất hài lòng là không em nào bỏ sai hộp trở lại
vào túi. Sau khi cả lớp đã lấy xong hộp của mình cô giáo đi phát phần thưởng cho các
em, mỗi em nhận được số viên kẹo đúng bằng số ghi ở hộp mà các em có.
Phụ huynh học sinh cũng rất thích thú với phương pháp giảng dạy sinh động này. Tuy vậy
có người lo lắng, lỡ thiếu kẹo phát cho những học sinh cuối cùng thì sao? Cô giáo cho
biết là bao giờ cũng phải chuẩn bị đủ số kẹo phát cho các cháu, không thừa và không
thiếu lấy một viên!
Yêu cầu: Cho n và các số ai (1 < ai < 32767, i = 1 - n, 1 < n < 105). Hãy xác định số kẹo
cô giáo cần chuẩn bị.


Dữ liệu vào từ file văn bản PRIZE.INP:
■ Dòng đầu tiên chứa số nguyên n,
■ N dòng sau chứa các số nguyên a1, a2, . . ., an.

5
12357
24568

DAYSO2.OUT
2


Bài 13: Giá trị lớn nhất

Tên file chương trình ‘GETMAX.???’

Cho dãy số nguyên a1, a2,. an các phần tử đôi một khác nhau.
Yêu cầu: Hãy tìm giá trị lớn nhất của dãy số đó sao cho giá trị lớn nhất đó phải thuộc tập
số nguyên: b1, b2,... bm.
Dữ liệu vào từ file ‘GETMAX.INP’:
■ Dòng thứ nhất chứa lần lượt các số nguyên dương n, m (n, m
2
4
2
0
1
Bài 15: Độ lớn của dãy số

MANUEQUI.OUT
3

Tên file chương trình ‘MINMAX.???’

Cho dãy số nguyên a1, a2,... an. Người ta tìm độ lớn của dãy số thông qua cặp số a i và aj
(với i=1,2,...n; j=1,2,...n; i≠j). Tuy nhiên, để đảm bảo độ lớn không có giá trị âm người ta
xác định độ lớn của dãy số bằng phép tính |ai+aj|.
Yêu cầu: Với n số nguyên a1, a2,. an. Hãy cho biết dãy số có độ lớn trong phạm vi nào?
Dữ liệu vào từ file ‘MINMAX.INP’:
■ Dòng thứ nhất chứa số nguyên dương n(n
2

Tên file chương trình ‘FRIEND.???’

Theo quan niệm của người Á đông cổ, mỗi cá nhân khi sinh ra đều ứng với một ngôi sao,
được gọi là sao chiếu mệnh. Các hoạt động của cá nhân đều bị chi phối bởi ngôi sao này,
kể cả quá trình kết bạn - hẹn hò. Theo thuyết Âm dương - Ngũ hành, hai người chỉ có thể
tạo lập mối quan hệ bền vững khi các sao chiếu mệnh của họ không có các thuộc tính
tương khắc. Qua hàng ngàn năm quan sát và chiêm nghiệm, các chiêm tinh gia đã ghi
nhân được hầu hết các tính chất tương sinh - tương khắc của sao: mỗi sao, ngoài một mã
số để nhân diện còn có một giá trị thể hiện khả năng thích nghi của sao gọi là độ thích
nghi. Thông qua độ thích nghi, người ta tính khả năng tương hợp của các sao. Khả năng
tương hợp của 2 sao được tính bằng tổng 2 độ thích nghi của chúng.
Yêu cầu: cho n và dãy s1,s2, ...,sn là độ thích nghi của các sao. Hãy xác định số lượng T
các cặp sao có khả năng tương hợp bằng B. Hai cặp (Si, Sj) và (Sj, Si) được tính là 1.
Ví dụ trong 5 sao với mã số 3, 5, 6, 5, 3 có 4 cặp có khả năng tương hợp là 8.
Dữ liệu vào từ tập tin văn bản FRIEND.INP
-

Dòng đầu tiên ghi 2 số nguyên n, B (2 < n < 105)

-

Mỗi dòng trong n dòng tiếp theo ghi một số nguyên là độ thích nghi của một sao,
độ thích nghi có trị tuyệt đối bé hơn 215

Kết quả xuất ra tập tin văn bản FRIEND.OUT là số nguyên T tìm được
Ví dụ:
FRIEND.INP


4
1
Bài 19: Tổng Chẵn

SUMAVER.OUT
1

Tên file chương trình ‘SUMEVEN.???’

Cho dãy số nguyên gồm n phần tử a1, a2,...an. Người ta chọn trong dãy ra 2 phần tử ai và aj
(i=1, 2,….n; j=1, 2,…n) sao cho i