Tin học Việt

A place for learning and sharing knowledge


    [Bổ sung] Một vài mẹo trong CS

    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

    [Bổ sung] Một vài mẹo trong CS

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

    TWO POINTERS :
    Là 1 phương pháp xác định 2 điểm I,j để giải quyết các bài toán về dãy số, trục số,… có tính thứ tự
    Tính chất : I luôn tăng , j luôn giảm cho tới khi tìm dc kết quả của bài toán

    Ví dụ : cho 1 dãy A[] - tăng, tìm a[i] + a[j] = 0
    hướng dẫn :
    đặt i = 1; j = n
    trong vòng while :
    nếu như a[i] + a[j] > 0 thì dec(j) vì tăng j thì tổng sẽ tăng thêm
    nếu như a[i] + a[j] < 0 thì inc(i) vì giảm I thì tổng sẽ giảm mất
    Code:

    I := 1;J := n;
    While (j > 0) and (i < n + 1) do
       Begin
          if a[i] + a[j] = 0 then exit(I,’ ‘,j);
          if a[i] + a[j] > 0 then dec(j) else inc(i);
       End;
    Note 1: pp này ta còn có thể áp dụng cho các bài toán tìm 2 điểm sao cho min , max, trị tuyệt đối,… miễn sao cho thỏa 1 tính chất nào đó dc rồi
    Note 2: ngoài ra ta có thể áp dụng dễ dàng áp dụng 2 mảng với các cách tìm điểm như trên
    Problem :
    NKSGAME [You must be registered and logged in to see this link.]
    60A - Where Are My Flakes? [You must be registered and logged in to see this link.]

    CYCLE DETECTION

    Floyd's cycle-finding algorithm
    (thuật toán thỏ và rùa)


    Là thuật toán tìm kiến 1 chu trình trong 1 dãy số với độ phức tạp là O(n)
    Chú ý : trong chu trình các giá trị phải có các giá trị khác nhau (nếu giải quyết các trường hợp giống nhau thì mất tới O(n2))
    Cách tìm : (giả sử đang là thỏ và rùa) :
    Đặt thỏ = R , rùa = T
    Tìm vị trí chu trình gặp nhau :
    Cho vị trí của R và T ở đầu dãy
    Lần lượt tăng vị trí của R và T lên , với R tăng 2 bước, T tăng 1 bước
    Lặp lại cho tới khi giá trị đứng của R và T giống nhau
    Tìm vị trí bắt đầu chu trình :
    B1 : tìm vị trí chu trình gặp nhau
    B2 : ta cho vi trí thỏ trở về vị trí xuất phát, giữ nguyên vị trí của rùa, cho từng con đi tới 1 bước cho tới khi đứng tại vị trí giá trị bằng nhau
    Tìm độ dài của chu trình :
    B1 : tìm vị trí chu trình gặp nhau
    B2 : tìm vị trí xuất phát của chu trình
    B3 : ta cho vị trí của thỏ và rùa tới vị trí xuất phát của chu trình, đi 1 bước cho tới khi đứng tại giá trị bằng nhau.
    Problem
    PBCFIBO : [You must be registered and logged in to see this link.]

    KADANE’S ALGORITHM :
    Là 1 phương pháp dùng để xác định dãy
    1 cách dùng của nó là tìm dãy có tổng lớn nhất trong 1..n với phương châm là ; nếu như tổng liên tiếp các phần tử < 0 thì dãy cần tìm không nằm trong khoảng đó.
    Code :
    TH cho mảng 1 chiều :
    Code:

    k := 0;l := 0;t := 0;s := 0;dau := 1;
      for cuoi := 1 to n do
        begin
          t := t + a[cuoi];
          if t > s then
            begin
              s:= t;
              k := dau;l := cuoi;
            end;
          if t < 0 then
            begin
              t := 0;
              dau := cuoi + 1;
            end;
        end;
      writeln(k,' ',l);
    TH cho mảng 2 chiều :
    Code:

      for z := 1 to m do
        begin
          for i := 1 to n do pre[i] := 0;
          for x := z to m do
            begin
              t := 0;s := 0;dau := 1;
              k := 0;l := 0;
              for cuoi := 1 to n do
                begin
                  pre[cuoi]:= pre[cuoi] + a[x,cuoi];
                  t := t + pre[cuoi];
                  if t > s then
                    begin
                      s := t;
                      k := cuoi;
                      l := dau;
                    end;
                  if t < 0 then
                    begin
                      t := 0;
                      dau := cuoi + 1;
                    end;
                end;
              if s > res then
                begin
                  res := s;
                  x1 := z;y1 := l;
                  x2 := x;y2 := k;
                end;
            end;
        end;

      Similar topics

      -

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