Part 1: link here
Hôm nay đẹp trời + yêu đời, viết tiếp cái part 2 chơi :v, tiện cũng sửa lại đống code ở Part 1, nhìn lại mới biết lúc đó mình code ngu ko tả được :angry:
Part 2 mình sẽ trình bày cách chặt nhị phân trên mảng tăng giảm.
Vấn đề đặt ra như sau:
Problem: Cho hàm f(x) nửa tăng nửa giảm ( hoặc nửa giảm nửa tăng) trên đoạn [a;b], tìm x’ sao cho f(x) đạt cực trị tại đó ( cực đại hoặc cực tiểu ).
Sau đây là đoạn code tìm cực tiểu hàm f(x) trên đoạn [lo,hi]
double bsearch(double (*f)(double), double lo, double hi) {
const double eps = 0.01;
double ans = lo;
while(abs(lo-hi) > eps) {
double m = (lo + hi) / 2;
double l = m - eps;
double r = m + eps;
if (f(l) < f(m)) {
ans = l;
hi = l;
} else if (f(r) < f(m)) {
ans = r;
lo = r;
} else {
ans = m;
break;
}
}
return ans;
}
+ Điều kiện lặp thực chất vẫn là lo <= hi, nhưng ta đang làm việc trên số thực nên cần có sai số eps để so sánh
+ Do toàn bộ hàm f hiện tại không còn tuyến tính, nên để biết được sự dịch chuyển của lo và hi, ta cần phải xét 2 vị trí lân cận nằm về 2 phía của m là l và r
*nếu f(l) < f(m), chứng tỏ nếu ta tiếp tục theo hướng trái, sẽ gặp cực tiểu. Tiến hành lưu kết quả, và bỏ toàn bộ phần từ m đến hi ( hi = l)
* nếu f(r) = f(l) và f(m) >= f(r), thì (m, f(m)) chính là điểm cực tiểu => thoát vòng lặp.
Trường hợp mảng 1 chiều, chính là sự rời rac của hàm liên tục f(x).
Problem: Cho màng a nửa tăng( giảm) nửa giảm ( tăng). Tìm vị trí mid sao cho a[mid] là max ( hoặc min)
int bsearch(int * a, int lo, int hi) {
int ans = -1;
while(lo <= hi) {
int m = (lo + hi) / 2;
int l = m - 1;
int r = m + 1;
if (a[l] < a[m]) {
ans = l;
hi = l;
} else if (a[r] < a[m]) {
ans = r;
lo = r;
} else {
ans = m;
break;
}
}
return ans;
}
Ứng dụng: http://vn.spoj.com/problems/MINCUT/
Happy coding
Nhan Nguyen 