Giải một bài toán tin bằng mãng đánh dấu!!

-Trong các phương pháp đơn giản hóa một bài toán tin, thì mảng đánh dấu được xem là một phương pháp cơ bản và khá khôn ngoan khi cài đặt, dưới đây mình xin chia sẽ vài ví dụ điển hình cho vai trò của mảng đánh dấu!!
1.ví dụ 1

-Đề: Cho một mảng nguyên A với N phần tử, tìm dảy con liên tiếp tăng dần dài nhất của  mảng với   2<N<10^6.
*Thuật giải vét cạn:
 -Đây là cách giải thông thường khi chúng ta tiếp cận những dạng toán huy hoạch trên mãng như thế này.
-Tại mỗi vị trí thứ i của mảng ta duyệt từ i -->j để đếm số lượng phần tử của dãy con tăng dần theo yêu cầu , quá trình kết thúc khi tại j ta có a[j]<a[j-1].
-Đây là đoạn  chương trình mẫu trong C với hàm Thuchien trả về giá trị là dãy con lớn nhất.
    int Thuchien(int *A,int N)
   {
          int max = 0,count = 0;
          for (int i  = 0;i < N;i++)
          {
                j = i;count = 0;
                while (A[ j ]>A[ i ])
                {
                      count++;j++;
                }
                if (count > max) max = count;
            }
          return max;
    }
-Cách giải như trên là phương thức dể tiếp cận và cài đặt đối với chúng ta, tuy nhiên độ phức tạp của thuật toán lại là N*(N+1)/2  , làm một phép tính nho nhỏ ta dể dàng thấy được nỗi vất vã của C khi duyệt với N=10^6.
*Thuật giải với mảng đánh dấu:
 -Ở phương thức vét cạn nêu trên ở mỗi bước i ta lại duyệt một mãng con khác nhau, điều đó làm tốn khá nhiều phép toán trùng lặp không cần thiết.  Trong phương thức dưới đây chúng ta sẽ triệt để tận dụng các phép toán được sinh ra.
 - Để tiếp cận bài toán ta sẽ dùng một mảng phụ T ,với T[i] chính là số lượng phần tử dãy con  tại i,                            T[i] = T[i-1] +1; khi ta có A[i] >A[i-1];
            và ta sẽ khởi tạo lại T[i] = 1; khi ta có A[i]<A[i-1] hay khi dãy con tăng dần kết thúc.
- Dưới đây là thuật toán được cài đặt trong C;
int Thuchien(int *A,int N,int *T)
{
         int max = 0;
         T[0] = 1;
         for (int i = 1;i < N;i++)
         {
                if (A[ i ] > A[ i-1 ])
                       T[ i ] = T[ i-1]+1; 
                else T[ i ] = 1;
                if (T[ i ] > max) max = T[ i ];
          }
          return max;
}
-Với cách tiếp cận như trên bài toán thực hiên với độ phức tạp là tuyến tính N.

2 ví dụ 2:
  
 -Đề: Cho mãng nguyên A với N phần tử (2<N<1000) tìm số lượng phần tử của dãy con không liên tiếp tăng dần dài nhất của mãng.
         EX:         N = 5; A = (1,4,3,2,3) , kết quả là 3 với dãy con 1,2,3.
-Trong ví dụ này mọi vấn đề lại trở nên khá phức tạp khi phải giải quyết với dãy con không liền kề, để phá gở khó khăn này ta dùng một mảng đánh dấu T, với T[i] là số lượng phần tử lớn nhất của dảy con được nối bởi A[i].
-Khi đó ta sẽ chọn giá trị cho T[i] bằng cách duyệt từ i trở về 0,T[i] được chọn là giá trị T[j] lớn nhất thỏa A[j] < A[i] (j <i) cộng thêm cho 1;
-Dưới đây là phép cài đặt trong C thông qua hàm Thuchien trả về giá trị max cần tìm

int Thuchien(int *A,int N,int *T)
{
       T[0] = 1;
       int max = 0;
       int temp = 0;
        for (int i = 1;i < N;i++)
        {
             temp = 1;
             for (int j = i-1;j>= 0;j--)
                if (A[ i ] >A[ j ]&&T[ j ]+1> temp)
                     temp = T[ j ] +1;
             T[ i ] = temp;
             if (max < T[ i ])  max = T[ i ]);
          }
          return max;
} 
*Note: Thuật toán có thể phát triển để truy vết các phần tử của mảng con dài nhất!!!!
**Trên đây là hai ví dụ điển hình về ứng dụng mảng đánh dấu trong giải một bài toán tin học!

---Thân,
            
            
          Lê Võ Hữu Trí