Tài li
ệ
u b
ồi dưỡ
ng HSG môn Tin h
ọ
c
Chuyên đề
: K
ỹ
thu
ậ
t Ch
ặ
t nh
ị
phân
–
Nguy
ễ
n Chánh Tín
–
trườ
ng THPT Chuyên B
ạ
c Liêu
1
S
Ở
GD&ĐT BẠ
C LIÊU
TRƯỜ
NG THPT CHUYÊN B
Ạ
C LIÊU
Chuyên đề bồi dưỡng HSG môn Tin học:
Ứ Ứ
NNGG DD
ỤỤ
NNGG K K
ỸỸ
TTHHUU
ẬẬ
TT CCHH
ẶẶ
TT NNHH
ỊỊ
PPHHÂÂNN TTR R OONNGG VVII
ỆỆ
CC GGII
ẢẢ
II CCÁÁCC BBÀÀII TTOOÁÁNN TTIINN HH
ỌỌ
CC
GV Biên soạn :
NGUYỄN CHÁNH TÍN
Đơn vị
:
Trườ
ng THPT Chuyên B
ạ
c Liêu
Tháng 02/2018
Tài li
ệ
u b
ồi dưỡ
ng HSG môn Tin h
ọ
c
Chuyên đề
: K
ỹ
thu
ậ
t Ch
ặ
t nh
ị
phân
–
Nguy
ễ
n Chánh Tín
–
trườ
ng THPT Chuyên B
ạ
c Liêu
2
M
Ụ
C L
Ụ
C
Mục
Nội dung
Trang
Lời mở đầu
3 1
Phần nội dung
4 2 I-
Cơ sở lý thuyết
4 3 II-
Chặt nhị phân theo kết quả
8 4
III-
Ch
ặ
t nh
ị
phân trên dãy s
ố
.
19 5 K
ế
t lu
ậ
n 37 6 Tài li
ệ
u tham kh
ả
o 38
Tài li
ệ
u b
ồi dưỡ
ng HSG môn Tin h
ọ
c
Chuyên đề
: K
ỹ
thu
ậ
t Ch
ặ
t nh
ị
phân
–
Nguy
ễ
n Chánh Tín
–
trườ
ng THPT Chuyên B
ạ
c Liêu
3
LỜI MỞ ĐẦU
Hiện
nay
trong các kỳ thi, đề thi luôn yêu cầu vận dụng và phối hợp nhiều thuật toán một cách linh hoạt
để giải bài toán.
V
ới mỗi bài toán học sinh không chỉ phải đưa ra được thuật toán đúng
mà
thuật toán đó còn phải tốt
đáp ứng yêu cầu về thời gian
để có thể “ăn”
hết các test lớn
. P
hần lớn khi giải bài toán, chúng ta chỉ tập trung ở mức độ tìm thuật toán đúng cho bài toán. Chẳng hạn với bài toán sau:
Cho
một dãy số nguyên gồm N phần tử,
hãy
sắp xếp để dãy số đã cho trở thành dãy không giảm? Trước tiên
chúng ta
ai cũng nghĩ ngay
đến thuật toán sắp xếp tráo đổi [thuật toán sắp xếp “nổi bọt”] có độ phức tạp
O[N
2
]
. Đây
là
thuật toán đúng nhưng chỉ trong trường hợp N≤ 1
0
3
. N
ếu tăng số lượng phần tử lên khoảng 10
5
phần tử thì ta cần một thuật
toán
sắp xếp tốt hơn như: QuickSort, MergeSort có độ phức tạp
O[NlogN]
.
Từ vấn đề thực tiễn trên thì kỹ thuật “Chặt nhị phân”
là
một kỹ thuật sẽ giúp làm giảm thời gian thực hiện thuật toán từ O[K] xuống còn O[logK]
.