Chặt nhị phân
Để tìm kiếm một phần tử trong mảng. Với cách thông thường, ta phải duyệt tất cả các số từ a[1] đến a[n], tức là mất độ phức tạp O(n). Tuy nhiên với mảng đơn điệu (dãy không tăng hoặc không giảm), thì ta chỉ mất độ phức tạp O(logn) để tìm kiếm, với bài toán này, ta dùng chặt nhị phân để tìm kiếm. Bài viết này tôi sẽ viết về cách chặt nhị phân và chặt tam phân.
Lưu ý:
- Chặt nhị phân chỉ dùng đưuọc cho dãy đơn điệu
- Chặt tam phân chỉ dùng được cho dãy tăng rồi giảm (hoặc giảm rồi tăng), tức là tồn tại một điểm i mà a[1..i] đơn điệu, a[i..n] đơn điệu.
- Có rất nhiều cách chặt nhị phân, và mỗi người lại code một cách khác nhau. Ở đây tôi xin đưuọc trình bày cách mà tôi thương dùng, vì cách này có tương đối nhiều ưu điểm.
1. Chặt nhị phân trên mảng
Giả sử ta có bài toán sau:
Bài toán
Cho một dãy n số. Với mỗi số k được nhập vào, in ra một số nằm trong dãy ban đầu, nhỏ nhất và lớn hơn hoặc bằng số k. (Sẽ có Q số k được nhập, Q<=100000, n<=100000)
Trước hết ta thấy rằng có thể sort lại mảng a (gọi a là dãy số ban đầu). Vì vậy ta có thể giả sử a là dãy không giảm. Ta sẽ làm như sau:
sort(a);
left=1, right=n;
for i = left to right do
if a[i]>=k then return a[i];
print "Not found"
Dưới đây là code không dùng chặt nhị phân.
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, k, m;
int a[1230997];
void bsearch(int k){
int ll=1, rr=n, i;
for (i=ll; i<=rr; i++)
if (a[i]>=k) { printf("%d\n", a[i]); return; }
printf("Not found\n");
}
main(){
int i;
scanf("%d", &n);
for (i=1; i<=n; i++) scanf("%d", &a[i]);
sort(a+1, a+n+1);
scanf("%d", &m);
for (i=1; i<=m; i++){
scanf("%d", &k);
bsearch(k);
}
}
Với thuật toán như trên, độ phức tạp là O(mn) (với m là số truy vấn/câu hỏi). Tôi sẽ thêm một số lệnh để giảm độ phức tạp xuống O((m+n) logn). Các lệnh mà tôi thêm vào sẽ được tô màu đỏ.
sort(a);
left=1, right=n;
i = (left + right) / 2;
while (left != i) and (i != right) do
if a[i]>=k then right = i;
else left = i;
i = (left + right) / 2;
for i = left to right do
if a[i]>=k then return a[i];
print "Not found"
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, k, m;
int a[1230997];
void bsearch(int k){
int ll=1, rr=n, i=(ll+rr)/2;
while (ll!=i && i!=rr){
if (a[i]>=k) rr=i;
else ll=i;
i=(ll+rr)/2;
}
for (i=ll; i<=rr; i++)
if (a[i]>=k) { printf("%d\n", a[i]); return; }
printf("Not found\n");
}
main(){
int i;
scanf("%d", &n);
for (i=1; i<=n; i++) scanf("%d", &a[i]);
sort(a+1, a+n+1);
scanf("%d", &m);
for (i=1; i<=m; i++){
scanf("%d", &k);
bsearch(k);
}
}
Với cách làm này, ta có thể kiểm tra độ chính xác của thuật toán bằng hàm bsearch ban đầu. Sau đó bạn có thể thêm một số dòng lệnh để cho chương trình chạy nhanh hơn.
Code trên đảm bảo rằng, với các a[i] giống nhau, hàm sẽ trả về a[i] đầu tiên trong mảng, để rõ hơn về điều này, ta xét bài toán sau.
Bài toán
Cho một dãy a đã sắp xếp tăng dần. Lần lượt nhập m số k. Có hai bài toán:
a, Với mỗi k, in ra số đầu tiên bé nhất lơn hơn hoặc bằng k.
b, Với mỗi k, in ra số cuối cùng lớn nhất bé hơn hoặc bằng k.
Tức là ở bài toán a, trong các a[i] thỏa mãn và bằng nhau, chọn a[i] có i nhỏ nhất. Ở bài toán b, trong các a[i] thỏa mãn và bằng nhau, chọn a[i] có i lớn nhất.
Trở lại với cách làm ở trên, đây là nội dung mã giả ở trên
sort(a);
left=1, right=n;
i = (left + right) / 2;
while (left != i) and (i != right) do
if a[i]>=k then right = i;
else left = i;
i = (left + right) / 2;
for i = left to right do
if a[i]>=k then return a[i];
print "Not found"
Để ý rằng dòng tô đỏ (if a[i]>k ...) ở trên, sẽ gán right = i cả khi a[i] = k. Vì thế kết quả luôn là a[i] với i nhỏ nhất. Để chọn i lớn nhất, ta thay đổi hai dòng tô đỏ ở trên thành:
sort(a);
left=1, right=n;
i = (left + right) / 2;
while (left != i) and (i != right) do
if a[i]>k then right = i;
else left = i;
i = (left + right) / 2;
for i = right to left do
if a[i]<=k then return a[i];
print "Not found"
2. Chặt nhị phân trên hàm
Với các hàm số thực, ta cũng làm tương tự như chặt nhị phân trên mảng. Giả sử ta có bài toán sau:
Nhập một số thực nằm trong khoảng từ 0 đến 1 (0 <= key <= 1). Tìm x để sin x = key.
Với bài này, ta đặt left=0, right =pi/2, sau đó chặt nhị phân giống như thuạt toán bên trên:
left=0, right=PI/2;
i = (left + right) / 2;
while (left != i) and (i != right) do
if sin(i)>=key then right = i;
else left = i;
i = (left + right) / 2;
print (l+r)/2;
Thuật toán như trên chắc chắn sẽ dừng tại một lúc nào đó, khi mà left rất gần với right, i sẽ bằng một trong hai giá trị left hoặc right, và lệnh while sẽ dừng lại. Bởi vậy, cách code ở trên không cần dùng epsilon, đây là một cách chặt nhị phân khá hay giúp bạn không cần phải quan tâm đến epsilon.
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <math.h>
double bsearch(double key){
double ll=0, rr=M_PI/2, i=(ll+rr)/2;
while (ll!=i && i!=rr){
if (sin(i) >= key) rr=i;
else ll=i;
i=(ll+rr)/2;
}
return (ll+rr)/2;
}
double key;
main(){
scanf("%lf", &key); // 0 <= key <= 1
printf("answer = %lf\n", bsearch(key));
printf("arcsin = %lf\n", asin(key));
}
3. Chặt tam phân
Có những hàm không thể chặt nhị phân mà có thể chặt tam phân. Ví dụ :
Bài toán
Cho hai điểm A, B trên mặt phẳng. Chọn một điểm C nằm trên trục Ox. Tìm điểm C để tổng AC + BC là nhỏ nhất. Gọi f(x) là tổng AC + BC với C ở tọa độ (x, 0). Ta cần tìm f(x) bé nhất.
Giả sử ta đã tìm được một điểm C0 thỏa mãn đề bài. Xét các điểm C nằm bên phải C0, ta tháy rằng khoảng cách từ C đến C0 càng tăng. Tương tự vơi bên trái. Có nghĩa là: bên phải điểm C0 là hàm tăng, bên trái C0 là hàm giảm, bới vậy ta dùng chặt tam phân.
LL=minX, RR=maxX;
ML=(LL+LL+RR)/3, MR=(LL+RR+RR)/3;
while (LL!=ML) and (ML!=MR) and (MR!=RR) do
if f(ML)>f(MR) then LL=ML;
else RR=MR:
ML=(LL+LL+RR)/3, MR=(LL+RR+RR)/3;
print (LL+RR)/2;
Dòng chữ đỏ đâu tiên, có nghĩa là chia đoạn LL..RR thành ba khoảng: LL..ML, ML..MR, MR..RR. Dòng chữ đỏ thứ hai có nghĩa là: nếu f(ML) > f(MR) thì tất cả f(LL)..f(ML) đều lớn hơn f(MR) suy ra cả đoạn LL..ML đều không phải là đáp án của mình. Tương tự với trường hợp f(ML) < f(MR). Vì vậy thuật toán trên là đúng.
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
double xa, ya, xb, yb;
double f(double x){
double AC = sqrt((xa-x)*(xa-x) + ya*ya);
double BC = sqrt((xb-x)*(xb-x) + yb*yb);
return AC+BC;
}
main(){
scanf("%lf%lf%lf%lf", &xa, &ya, &xb, &yb);
double rr=max(xa, xb);
double ll=min(xa, xb);
double ml=(ll+ll+rr)/3;
double mr=(ll+rr+rr)/3;
while (ll!=ml && ml!=mr && mr!=rr){
if (f(ml) > f(mr)) ll=ml;
else rr=mr;
ml=(ll+ll+rr)/3;
mr=(ll+rr+rr)/3;
}
printf("answer = %lf\n", (ll+rr)/2);
printf("cost = %lf\n", f((ll+rr)/2));
}
4. Dùng thư viện có sẵn
Dưới đây là các hàm có sẵn trong thư viện algorithm và ví dụ về cách sử dụng. Các hàm này chỉ hoạt động khi dãy số đưuọc sắp xếp tăng dần (chính xác hơn là dãy không giảm).
hàm lower_bound(first, last, value) : trả về vị trí đầu tiên lớn hơn hoặc bằng value trong dãy.
hàm upper_bound(first, last, value) : trả về vị trí đầu tiên lớn hơn value trong dãy.
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, m;
int a[1230997];
main(){
int i, p, q;
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
sort(a+1, a+n+1); // a[1..n]
for (i=1; i<=n; i++) printf(i==n?"%d\n":"%d ", a[i]);
scanf("%d", &m); // m times
while (m--){
scanf("%d", &p);
q = lower_bound(a+1, a+n+1, p) - a; // a[1..n], a[q]>=p
if (q==n+1) printf("No numbers are bigger than %d\n", p);
else printf("The 1st number >= %d is a[%d]=%d\n", p, q, a[q]);
q = upper_bound(a+1, a+n+1, p) - a; // a[1..n], a[q]>p
if (q==n+1) printf("No numbers are bigger than %d\n", p);
else printf("The 1st number > %d is a[%d]=%d\n", p, q, a[q]);
}
}
5. Cách code để chắc chắn mình chặt nhị phân đúng
Đây là mã giả đã nêu ở trên thể hiện đầy đủ các bước chặt nhị phân. Sau đây tôi xin được trình bày cách kiểm tra việc chắt nhị phân của mình để đảm bảo mình code đúng.
left=1, right=n;
i = (left + right) / 2;
while (left != i) and (i != right) do
if a[i]>=k then right = i;
else left = i;
i = (left + right) / 2;
for i = left to right do
if a[i]>=k then return a[i];
print "Not found"
Để kiểm tra code mình đúng hay không, hãy xóa bỏ (comment) vòng while và chạy chương trình. Khi xóa bỏ vòng while, code này trở thành code không chặt nhị phân:
left=1, right=n;
// vòng while bị loại bỏ ở vị trí này
for i = left to right do
if a[i]>=k then return a[i];
print "Not found"
Nếu chạy thử mà việc bỏ hay giữ nguyên vòng while làm cho kết quả có sự khác biệt thì bạn cần xem lại code của mình.
6. Các lỗi thường gặp
Time limit exceeded
- Kiểm tra điều kiện trong vòng lặp while, người mới code chặt nhị phân thường mắc phải cách code while (left<right) do hoặc while (left<=right) do. Như đã nói ở trên, code trên sẽ dẫn đến lặp vô hạn khi khoảng cách giữa left và right bằng 1. Sửa lệnh while thành while (left!=i and right!=i).
- Kiểm tra xem bạn có quên lệnh i=(ll+rr)/2 hay không.
- Kiểm tra xem bạn có quên lệnh gán ll=i hoặc rr=i không.
Wrong answer
- Kiểm tra xem có thiếu lệnh for (i=ll; i<=rr; i++) ... hay không. Khi ll và rr cách nhau một khoảng đủ nhỏ, thì một trong số số nằm trong khoảng ll đến rr là đáp án của mình, không thể ngay lập tức return i, vì ta chưa biết i có phải là nghiệm tối ưu nhất hay không.
- Kiểm tra điều kiện trong lệnh if (a[i]>=key) rr=i; else ll=i; một sai lầm hay mắc phải là dấu >= bị viết nhầm thành dấu >. Vì nếu dấu bằng xảy ra thì ta phải gán rr=i chứ không đưuọc làm ngược lại.
- Kiểm tra xem trường hợp vô nghiệm (Not found) có xảy ra hay không, bạn đã xử lý nó hay chưa.
- Kiểm tra xem mảng/hàm có phải đơn điệu hay không. Nếu không, bạn cần suy nghĩ lại xem thuật toán của mình có đúng không.