Tin học Việt

A place for learning and sharing knowledge


    [Chuyên đề] Tìm kiếm nhị phân (Chặt nhị phân)

    Share

    Admin
    Admin
    Admin

    Posts : 48
    Golds : 2147483647
    Liked : 16
    Ngày tham gia : 2011-08-25
    Tuổi : 20
    Đến từ : Ho Chi Minh City

    [Chuyên đề] Tìm kiếm nhị phân (Chặt nhị phân)

    Post by Admin on Sun Jan 27, 2013 10:17 am

    BINARY SEARCH : (tìm kiếm/chặt nhị phân)
    Là 1 pp tìm kiếm kết quả dựa vào tính thứ tự của tập hợp thay cho cách tìm kiếm thông thường
    Pp tìm kiếm thỏa mãn :
    Trên 1 dãy tuyến tính tăng/ giảm theo cùng 1 tiêu chí nào đó
    Thỏa mãng dc tính chất của đề bài, lập luận thỏa mãn (nếu tôi đi lùi thì chỉ thu dc kết quả xấu hơn, còn đi tiếp thì hi vọng thỏa mãn)
    Độ phức tạp : O(log2n), nhanh nhiều so với O(n)

    Ví dụ 1: cho 1 tập n phần tử (a[i] < a[I + 1]) , vị trí của phần tử có giá trị là val dc nhập từ INPUT
    Code:

    function bs : integer;
    var
      l,r : integer;
      mid : integer;
    begin
      l :=1;r := n;
      while l <= r do
        begin
          mid := (l + r) div 2;
          if a[mid] = val then exit(mid);
          if a[mid] < val then l := mid  + 1
          else
            r := mid - 1;
        end;
      exit(-1);
    end;
    Ví dụ 2 : cho 1 tập n phần tử (a[i] < a[I + 1]) , vị trí của phần tử có giá trị là val dc nhập từ INPUT sao cho độ lệch của val – a[i] là nhỏ nhất
    C1 : ta val - cho dãy, bs như trên
    C2 : ta chặt nhị phân như sau :
    Code:

    function bs : integer;
    var
      l,r : integer;
      mid : integer;
    begin
      l := 1; r := n;
      while abs(l - r) <> 1 do
      begin
        mid := (l + r) div 2;
        if val = a[mid] then exit(mid);
        if val < a[mid] then r := mid
        else
          l := mid;
      end;
      if (abs(val - a[l]) < abs(val - a[r])) then exit(l)
        else exit(r);
    end;

    NOTE :
    note 1 : cách làm ở trên áp dụng cho 1 dãy mảng (1 dòng), ta cũng có thể áp dụng cách này cho pp tìm kiếm trên 2 dòng
    note 2 : có nhiều cách chặt nhị phân , không nhất thiết là phải như trên, ta xét các trường hợp sau :
    cách 1 :
    while I <= j do -> I := mid +1; j := mid – 1
    cách này ta làm khi muốn tìm chính xác phần tử hay giá trị thỏa mãn nhu cầu duyệt, không chắc rằng làm cách này có thể giải quyết dc bài toán tìm độ lêch và cung hok nên dùng cách này để giải quyết những bài toán tối ưu
    1 biến thể của cách 1 cũng khá hay là: (biến thể này có thể giải quyết cho bài toán tối ưu)
    While I < j do
    Begin
    Mid := (I + j + 1) div 2;
    I := mid;
    J := mid – 1;
    End;

    cách 2 :
    while abs(I - j) <> 1 do -> I := mid; j := mid
    cách này là 1 pp rất hay để tìm vị trí phần tử tối ưu, dạng bài toán tìm độ lệch, chú ý rằng giá trị tối ưu sẽ nằm trong 2 giá trị l,r nên ta phải kt thêm 1 lần nữa
    ngoài ra, cách 2 còn có các biến thể :
    while I <> j do -> I := mid + 1;j := mid
    thực chất 2 cách làm đều tương tự nhau, nếu quen dùng cách nào chỉ nên dùng cách đó, ở đay liệt kê ra chỉ là 1 số cách hay gặp trong code của 1 số ng :D
    note 3 : chặt nhị phân trên chính trục số thì làm tương tự như trên cũng ổn
    note 4 : chặt nhi phân trên trụ tọa độ, ta có pp làm như sau :
    while dau – cuoi < eps do
    begin
    mid = (dau + cuoi) / 2;
    dau := mid;
    cuoi := mid;
    end;

    note 5 : hàm lower_bound, up_bound tưa tựa bên C++ bằng cách tìm độ lêch giữa giá trị cho và pt mảng nhỏ nhất, rồi theo yêu cau lower hay up ta tìm trong khoảng (1,val) hay là (val,n) (tìm tiếp bằng độ lệch)

    PP xe ủi (chế)
    Code:

    Trong 1 số bài toán, thay vì sort lại kết quả của bài toán, ta có thể sử dụng thêm 1 mảng b[] dùng lưu giá trị sao cho : B[i] = way(b[i],b[I + 1]) (way() ở đây có thể là min, max, etc …)
    sau khi init  B[] xong, ta có thể binary search theo yêu cầu của đề bài
    note : muốn sử dụng thì phải cm tính đúng đắn của nó rồi mới sử dụng
    example : problem điển hình của lớp toán này là bài toán tìm a[j] xa a[i] nhất sao cho a[i] > a[j]
    Problem about binary search :
    LIS vn.spoj.pl/problems/LIS/
    RIDDLE vn.spoj.pl/problems/RIDDLE/
    YUGI vn.spoj.pl/problems/YUGI/ (1 bài tương tự là bài 8.5 sách “Tài liệu chuyên tin 3” - NXBGD)
    MTWALK vn.spoj.pl/problems/MTWALK/
    NKSPILJA vn.spoj.pl/problems/NKSPILJA/ (chia nhị phân trong hình học)
    96B- lucky number [You must be registered and logged in to see this link.]
    42A - Guilty — to the kitchen! [You must be registered and logged in to see this link.]
    159B - Matchmaker [You must be registered and logged in to see this link.]
    68B – Energy exchange [You must be registered and logged in to see this link.] (chú ý chuyển mọi pin đều chuyển x năng lượng)
    91B – Queue [You must be registered and logged in to see this link.] (dùng pp xe ủi :D)
    16C – Monitor [You must be registered and logged in to see this link.]
    140C – New year snowmen [You must be registered and logged in to see this link.]

    pha96
    Mod
    Mod

    Posts : 5
    Golds : 11
    Liked : 4
    Ngày tham gia : 2013-01-23
    Tuổi : 20

    Re: [Chuyên đề] Tìm kiếm nhị phân (Chặt nhị phân)

    Post by pha96 on Mon Apr 15, 2013 5:15 pm

    bạn cho mình hỏi bài RIDDLE (spoj) và Lucky Number (codeforce) chia nhị phân như thế nào vậy? mình cũng đang tìm hiểu phần này đây nhưng ví dụ thì ít quá mà trình độ thì có hạn :d.

      Current date/time is Tue Dec 06, 2016 3:39 am