mẹo hay Hỏi Đáp Ví dụ Khỏe Đẹp Bài tập Longest common subsequence Longest common substring VNOI Wiki

Bài tập ví dụ về dãy con chung dài nhất năm 2024

Bài toán tìm dãy con tăng dài nhất là một trong các bài toán được nghiên cứu nhiều trong các lĩnh vực như toán học, thuật toán, lý thuyết vật lý.

Ví dụ: Dãy ban đầu gồm các phần tử: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

Dãy con tăng dài nhất sẽ là: 0, 2, 6, 9, 13, 15.

Có thể thấy rằng nghiệm của bài toán không là duy nhất, trong ví dụ trên chúng ta có hai nghiệm khác là: 0, 4, 6, 9, 11, 15 và 0, 2, 6, 9, 11, 15.

Cách tiếp cận đầu tiên và không hiệu quả đối với bài toán này là duyệt qua các tập con của dãy ban đầu và kiểm tra các điều kiện: dãy tăng và dài nhất. Với một dãy n phần tử bạn sẽ cần duyệt hết 2n tập con của dãy và điều này là không thể dù với những giá trị n khá nhỏ. Cách tiếp cận đúng đắn với bài toán này là sử dụng kỹ thuật qui hoạch động.

Trong bài báo này tôi sẽ trình bày với các bạn 3 thuật toán qui hoạch động để giải quyết bài toán LIS-LDS với độ phức tạp thời gian giảm dần.

2.Sắp xếp mảng với hàm qsort[] trong C/C++

Trước hết là việc thực hiện sắp xếp một mảng [chúng ta sẽ cần dùng tới kiến thức này ở thuật toán thứ nhất] bằng hàm qsort[] của C/C++. Để sắp xếp một mảng các phần tử có kiểu bất kỳ chúng ta chỉ cần cài đặt một hàm so sánh thứ tự giữa hai phần tử đó và gọi tới hàm qsort[] [cài đặt thuật toán Quick sort] được cung cấp sẵn bởi C/C++.

Ví dụ để sắp xếp một mảng số nguyên ta cần khai báo hàm so sánh hai số nguyên như sau:

int cmp_function[const void *x, const void *y]

{

return [*[int*][x]] - *[[int*][y]]; // chuyển các con trỏ x và y thành con trỏ int *

}

Sau đó khi cần sắp xếp mảng a có n phần tử chúng ta sẽ gọi hàm qsort[] theo cú pháp sau:

qsort[a, n,sizeof[int], cmp_function]; // sizeof[int] là kích thước 1 phần tử của mảng a.

Việc cung cấp hàm so sánh để có thể làm việc với các kiểu dữ liệu khác dành lại cho các bạn độc giả như một bài tập nhỏ.

3.Bài toán tìm dãy con chung [LCS] của hai dãy

Đây là một bài toán khá phổ biến trong tin học, nhất là khi chúng ta học về qui hoạch động. Mục đích của bài toán là đi tìm dãy con chung [gồm 1 số phần tử] của hai dãy ban đầu có độ dài lớn nhất. Gọi hay dãy ban đầu là a gồm n phần tử và b gồm m phần tử [đánh chỉ số từ 0], chúng ta sẽ sử dụng các mảng hai chiều ret[][] và path[][] để lưu độ dài lớn của dãy con tìm được và giá trị truy hồi [mảng path] để tính ngược lại dãy con kết quả theo công thức sau:

Mỗi phần tử ret[i][j] sẽ là độ dài xâu con lớn nhất tương ứng với các dãy ban đầu a[0..i-1] và b[0..j-1], ban đầu các phần tử của mảng ret[][] sẽ được khởi tạo bằng 0.

Giá trị độ dài dãy con LCS lớn nhất được lưu tại biến ret[n][m] và đường đi sẽ được tính lại dựa trên giá trị của các biến path[i][j].

Để tìm hiểu kỹ hơn về thuật toán cho bài toán LCS các bạn có thể tham khảo trên các bài báo của tạp chí “Tin học và Nhà trường” các số trước đây.

Ở đây tôi xin đưa ra cài đặt cụ thể với ngôn ngữ C++ và dữ liệu demo cho bài toán LCS như sau:

include

using namespace std;

const int MAXMN = 100;

int ret[MAXMN][MAXMN];

int path[MAXMN][MAXMN];

int lcs[int a[], int n, int b[], int m];

void print_lcs[int a[], int i, int j];

int main[]

{

int a[] = {1, 8, 2, 3, 18, 2, 6, 9};

int n = sizeof[a]/sizeof[int];

int b[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};

int m = sizeof[b]/sizeof[int];

cout

2.Sắp xếp mảng với hàm qsort[] trong C/C++

3.Bài toán tìm dãy con chung [LCS] của hai dãy

include

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề