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

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;