Tin học Việt

A place for learning and sharing knowledge


    [Chuyên đề] Cấu trúc dữ liệu

    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 đề] Cấu trúc dữ liệu

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

    BITMARKS:
    (BIT MANIPULATION)
    Xử lí bit là 1 pp rất hữu hiệu để giải quyết các bài toán tối ưu về không gian rất tốt, đồng thời cũng giải quyết dc vấn đề về thởi gian của chương trình khi thưc hiện
    Bit được lưu trong 1 kiểu số nguyên, ví dụ như là byte (8 bit), integer(16 bit), longint(32 bit), và kiểu int64(64 bit)
    Trong đó, (n - 1) bit đầu là những bit dương, bit cuối cùng là bit để biểu thị mối quan hệ âm dương

    Các phép toán trên bit :
    AND : 156 AND 235 = 136
    OR : 156 OR 235 = 255
    XOR : 156 XOR 235 = 119
    NOT : NOT 156 = -157
    Note 1 : quan sát thì ta thấy dc khi not 1 số x, thì ta dc số đối của số đó - 1, cho nên tha vì gán x = -x, ta có thể gán NOT (x - 1)
    Note 2 : khi xor 1 số, nếu tần xuất xor 1 số là lẻ thì luôn ra chính nó : a xor a xor a = a
    Note 3 : ta cần pp biệt 1 vấn đề đó là vị trí của bit và thứ tự của bit :
    Bit thứ 8 có :
    Vị trí của bit : 0,1,2,3,4,5,6,7
    Thứ tự của bit : 1,2,3,4,5,6,7,8
    Qua ví dụ cho thấy bit cuối cùng của vị trí bit là 7 chứ hok là 8 như thứ tự bit. Trong toán học cũng như lập luận của đa phần sách, bit đầu tiên luôn đánh dấu là 0 chứ không phải là 1, việc chọn 1 chỉ là cách hiểu để dễ dàng diễn giải trong các thuật toán
    Để dễ dàng thể hiện tính đúng đắn cũng như thói quen dùng của nhiều người, tài liệu này sẽ biểu thị bit được biểu diễn bằng vị trí của bit :D

    Phép dịch chuyển bit trái, phải :
    Ta có phép shl (phép dịch chuyển sang trái) và phép shr (phép dịch chuyển sang phải) :
    Ví dụ : 12 shl 1 = 24
    12 shr 1 = 6
    ngoài ra, 1 tính chất quan trọng là shl = *2k , shr = div 2k
    shl k, shr k có thể viết thành << k, >> k
    tính chất quan trọng của phép toán này là tất cả các phép toán về bit đều tập trung vào tính chất của phép dịch chuyển bit này :D

    Thao tác trên bit :
    xem bit thứ k của bit x: vitri = (x shr k) and 1
    gán bit c vào vị trí k của bit x :
    if c = 1 then x = x or (x shr k)
    else x = x and (not (x shr k))
    phép chuyển bit : x xor (1 shl k)
    note : ngoài ra còn có:
    phép bật, tắt bit : bật bit là gán bit = 1, tắt bit là gán bit = 0
    để thuận tiện cho việc mở/ tắt bit ta dùng 1 mãng hằng để lưu giá trị
    bitcost = array[0..63] = (1,2,4,8,16,…)

    debug :
    Để check lại 1 cách nhanh chóng và hiệu quả, ta thường viết 1 function chuyển từ cơ số 10 ra cơ số 2
    Code:

    function coso2(i : integer) : string;
    var s : string;
    begin
      s := '';
      if i = 0 then s := '0' else
      repeat
        if i mod 2 = 0 then s := '0' + s else s := '1' + s;
        i := i div 2;
      until i = 0;
      coso2 := s;
    end;
    ứng dụng :
    xử lí bit được dùng nhiều nhất trong cái bài toán về xử lí trạng thái, lớp bài toán quy hoạch động về trạng thái
    dùng làm CTDL cho các bài toán tối ưu mảng :D 
    Problem about bitmask :
    LTPMSEQ vn.spoj.pl/problems/LTPMSEQ
    CHESSCBG vn.spoj.pl/problems/CHESSCBG
    LEM2 vn.spoj.pl/problems/LEM2
    NTSHEEP vn.spoj.pl/problems/NTSHEEP

    GIRD :
    Gird là 1 pp vét mảng
    Gird là 1 p, kĩ năng khá quan trong các bài toán vét cơ bản và cũng như là những bài toán tối ưu phức tạp (phụ thuộc vào cách cài đặt đúng dắn và hiệu quả)
    Thao tác này thực hiện trực tiếp trên mảng
    Ta có các thao tác cơ bản sau đây :
    Tính tổng của mảng 1 chiều : a[i]
    S[0] := 0;
    For I := 1 to n do s[i] := s[I – 1] + a[i];
    // ghi tổng từ I = 2  j = 7
    I := 2;j := 7;
    Res := s[j] – s[I – 1];

    Note :
    Với tính chất trên, ta còn có 1 cách tăng 1 dãy (i…j) thêm k giá trị :
    S[i] := s[i] + k;s[j + 1] := s[j + 1] – k;
    sau khi hoàn thành tất cả các thao tác trên, ta phải :
    for I := 1 to n do s[i] := s[I – 1] + s[I];
    lưu ý rất lớn là s[] mảng dc gán gái trị ban đầu là 0.
    Tính tổng trên mảng 2 chiều : f[m,n]
    For j := 2 to n do f[1,j] := f[1,j] + f[1,j – 1]
    For I := 2 to m do
    Begin
    For j := 1 to n do f[I,j] := f[I,j] + f[I,j - 1];
    For j := 1 to n do f[I,j] := f[I,j] + f[I – 1,j];
    End;

    // ghi tổng từ [d1,c1] cho tới [d2,c2]:
    Res := f[d2,c2] – f[d2,c1 – 1] – f[d1 – 1,c2] + f[d1 – 1,c1 – 1]

    Phép chuyển mảng :
    Chuyển từ mảng 1 chiều thành 2 chiều : a[k] thành b[I,j] // (c,d)
    I := (k - 1) div c + 1;
    If k mod c = 0 then j := c else j := k mod c;
    B[I,j] := a[i];

    Chuyển từ mảng 2 chiều thành 1 chiều : b[I,j] (d,c) thành a[k]
    k := (I - 1) * c + j;
    a[k] := b[I,j];

    chuyển từ mảng 3 chiều thành 1 chiều : a[I,j,k] (ii,jj,kk) thành a[h]
    h := (I - 1)*jj*kk + (j - 1)*kk + k;
    a[h] := b[I,j,k];

    chuyển từ mảng 1 chiều thành 3 chiều : a[h] thành a[I,j,k] (ii,jj,kk)
    I := (h - 1) div (jj*kk) + 1;
    C := (I - 1)*jj*kk;
    J := (h - 1 – c) div kk + 1;

    If (h - c) mod kk = 0 then k := kk else k := (h - c) mod kk;
    Pp nén mảng :
    khi phần tử liên tiếp của mảng trùng nhau 1 giá trị , ta có thể nén các gía trị ấy trong 1 mảng b[]
    Nếu có 256 phần tử cùng có 1 gía trị là k thì :
    If (n mod 256 = 0) then b[n div 256] := k;
    Problem :
    CVJETICI – [You must be registered and logged in to see this link.] (dùng pp nén mảng)

    FORWARD STAR :
    CTDL dạng này chủ yếu lưu giá trị của các cặp phân tử liên hệ lẫn nhau như là đồ thị
    Mối liên hệ càng ít thì bộ nhớ sử dụng càng ít
    Tuy nhiên để truy xét 1 cặp đối ngẫu bất kì thì ta phải duyệt hết tất cả các giá trị só thể có
    Dạng này có thể cài dưới dạng con trỏ
    Code:

    (dùng mảng)
    var n,m,i,j,u,v,vv: integer;
      head : array[1..maxn + 1] of longint;
      adj : array[1..maxn] of longint;
    begin
      readln(n,m);
      fillchar(head,sizeof(head),0);
      for i := 1 to m do
        begin
          readln(u,v);
          inc(head[u]);
        end;
      for i := 2 to n do head[i] := head[i] + head[i - 1];
      readln(n,m);
      for i := 1 to m do
        begin
          readln(u,v);
          adj[head[u]] := v;
          dec(head[u]);
        end;
      head[n + 1] := m;
      for u := 1 to n do
        for vv := head[u] + 1 to head[u + 1] do
          begin
            v := adj[vv];
            writeln(u,' ',v);
          end;
    end.

    STACK + QUEUE :
    Stack : hoạt động theo cơ chế FILO
    Queue : hoạt động theo cơ chế FIFO
    Ngoài ra, 1 số cơ chế quan trọng có thể nói như sau :
    deque - Double Ended Queue : là 1 pp kết hợp giữa stack và queue
    Piority queue : cài đặt dựa trên dang sách vòng
    Piority stack : đây là 1 pp khá hay, áp dụng khá nhiều trong nhiều bài tập khó và sáng tạo, và đây cũng là 1 dạng bài tập về pp CLDL phải hiểu rõ bản chất.
    pp:
    1 trong cách phổ biến là dùng biến left[] và right[] để cập nhật vị trí cưc trái và cực đại
    left[] và right[] dc cập nhật bằng cách :
    left[i] := left[left[i] – 1]
    right[i] := right[right[i] +1]

    note :
    pp dc nêu trên chủ yếu làm trong phần init, thực hiện trong vòng lặp.
    áp dụng tốt cho dạng bài tìm cực của pt mảng (vd : bài KAGAIN)

    Problem :
    MINK [You must be registered and logged in to see this link.] (dùng DEQUE – nhớ cập nhật biến front sau khi writeln ra vị trí nhỏ nhất)
    KAGAIN [You must be registered and logged in to see this link.] (dùng piority stack)
    CHEAT [You must be registered and logged in to see this link.]
    TTRAVEL [You must be registered and logged in to see this link.]

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