Chặt nhị phân và các biến thể – part 2

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

Advertisements