Quy Hoạch động Tìm Xâu Con Chung độ Dài Lớn Nhất

Bài toán xâu con chung dài nhất là một bài toán kinh điển cho việc ứng dụng thuật toán quy hoạch động để giải quyết.

DANH SÁCH BÀI VIẾT Duyệt đồ thị, tìm kiếm đường đi dài nhất, đường đi ngắn nhất trong đồ thị Kiểm tra đồ thị liên thông trong bài toán đồ thị lập trình Sinh các chuỗi nhị phân có độ dài bằng n trong C/C++ Tìm dãy con có tổng trọng số lớn nhất trong lập trình C/C++ Tính A^n bằng phương pháp chia để trị Quy hoạch động tìm xâu con chung độ dài lớn nhất

Ta có thể phát biểu yêu cầu bài toán bằng lời như sau:

Viết chương trình nhập vào hai xâu kí tự, tìm ra độ dài xâu con chung lớn nhất và in ra xâu con chúng đó.Ví dụ: hai xâu “BACDB” và “BDCB”, xâu con chung lớn nhất có độ dài là 3 và xâu con chung là “BCB”.

Tìm công thức truy hồi cho bài toán

Công thức truy hồi cho bài toán sẽ có cấu trúc như sau:

Nếu A[i] == B[j] thì L[i][j] = L[i-1][j-1] + 1 Ngược lại thì L[i][j] = max (L[i-1][j], L[i][j-1])

Trong đó A, B là 2 xâu A, B và mảng L quá trình quy hoạch động. A[i] là ký tự thứ i của xâu A và B[j] là ký tự j của xâu B.

Tại sao lại ra được công thức truy hồi như vậy, có thể mình nói hơi khó hiểu một chút bạn chịu khó hình dung nhé.

• Tại trường hợp 1: Khi A[i] == B[j] tức là tại ký tự thứ A i và ký tự thứ B j đã có 1 ký tự chung, tất nhiên số ký tự chung của 2 xâu sẽ tăng lên một, trường hợp này khá là dễ hiểu rồi.
• Tại trường hơp số 2: khi mà A[i] khác B[j], Như vậy tại vị trí đó không có ký tự chung, như vậy ta sẽ xem xét xem độ dài xâu con chung khi bỏ đi 1 ký tự của A hoặc bỏ đi 1 ký tự của B thì 2 xâu nào có xâu con chung lớn hơn thì xâu con chung tại vị trí i,j sẽ bằng nó.

Mình mô phỏng lại bẳng khi thực hiện quy hoạch động với 2 xâu trên(Khi code khởi tạo thêm 1 hàng và 1 cột tại i | j = 0 có giá trị bằng 0 hết nhé).

Như vậy trên thực tế 2 xâu trên ta tìm được 2 xâu con chung dài nhất bằng nhau là: BDB và xâu con BCB, tuy nhiên BDB ta tìm được trước nên ta sẽ chỉ in xâu con này.

Truy vết tìm xâu con chung

Sau khi quy hoạch động ta có được bảng như trên ta tiến hành truy vết để in ra xâu con chung đó.

Để truy vết ban đầu gắn biến tv = 0, duyệt bảng bên trên đến vị trí nào mà có L[i][j] > tv thì tức là tại đó sẽ có ký tự chung, ta in ra ký tự đó và gắn lại biến tv = L[i][j]…thực hiện lặp cho đến khi hết mảng L.

• tv = 0, tại L[1][1] = 1 lớn hơn 0, ta in được ký tự B gắn lại tv = 1.
• tv = 1, tại L[2][4] = 2 lơn hơn 1, ta in ký tự D gắn lại tv = 2
• tv = 2, tại L[4][5] = 3 lớn hơn 2, ta in ký tự B gắn tv = 3

=> Đã truy vết hết bảng, vậy xâu chung là BDB.

Chương trình tìm xâu con chung dì nhất

Mình viết lại code theo ý tưởng trình bày bên trên, bạn thăm khảo thêm nhé.

#include <iostream> #include <algorithm> using namespace std; int n, m; int s[1000][1000]; /*Mảng để quy hoach động - Khai báo biến toàn cục các phần tử sẽ = 0 hết (Nếu khai báo biến mảng trong hàm thì khi quy hoạch động cần khởi tại hàng 0 và cột 0 có giá trị là 0 nhé) */ //Hàm tìm độ dài xâu con chung lớn nhất int dodaixauchung(string a, string b) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { //áp dụng công thức truy hồi if(a[i-1] == b[j-1]) s[i][j] = s[i-1][j-1]+1; else s[i][j] = max(s[i-1][j], s[i][j-1]); } return s[n][m]; } //Hàm truy vết lấy ra xâu con chung đó string lanvet(string a) { string xauchung = ""; int t = 0; //TRuy vết theo đúng ý tưởng trên for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i][j] > t) { t = s[i][j]; xauchung+=a[i-1]; } return xauchung; //Trả về xau con } int main() { string a = "BACDB"; string b = "BDCB"; n = a.length(); m=b.length(); cout<<"Do dai xau chung: "<<dodaixauchung(a,b); //In ra độ dài xâu con cout<<"\nXau chung: "<<lanvet(a); //In ra xâu con đó return 0; }

Kết quả khi chạy chương trình.

Cảm ơn bạn đã đọc hết bài viết! CHúC BạN HỌc TốT@@

[Xem tất cả bài viết chủ đề C/C++ tại đây]

3.7 3 Phiếu bình chọn Xếp hạng bài viết