Bài Toán Tìm Chuỗi Con Chung Dài Nhất Pdf - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (5 trang)

Trang chủ

Giáo Dục - Đào Tạo

Cao đẳng - Đại học

Bài toán tìm chuỗi con chung dài nhất pdf

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (115.79 KB, 5 trang )

Bài toán tìm chuỗi con chung dài nhất Cho hai xâu X =x1x2…xm và Y=y1y2…yn. Tìm xâu Z = z1z2…zk là xâu con chung dài nhất của X và Y. Một xâu con của xâu A là một cách chọn trong A một số phần tử giữ nguyên thứ tự. Bảng phương án Ta sẽ dùng mảng hai chiều B[0 m, 0 n] làm bảng phương án, trong đó B[i,j] là độ dài xâu chung dài nhất của các xâu con Xi (phần đầu của X) và Yj (phần đầu của Y). Cơ sở Rõ ràng nếu ít nhất một trong hai xâu X hoặc Y là xâu rỗng (j=0 hoặc i=0) thì B[i,j]=0. Công thức truy hồi Dễ dàng có các nhận xét sau: - Nếu i,j > 0 và xi=yi thì B[i,j] = B[i-1,j-1] + 1 - Nếu i,j > 0 và xi<>yj thì B[i,j] = max ( B[i,j-1], B[i-1,j] ) Truy vết Như vậy B[n,m] cho biết độ dài của xâu con chung dài nhất. Để chi ra tường minh xâu con chung dài nhất ta cần xây dựng bảng T[1 m, 1 n] để ghi nhận truy vết đánh dấu B[i,j] được tính từ B[i-1,j-1] hay B[i,j-1] hay B[i-1,j]. Cài đặt bài toán bằng ngôn ngữ Pascal VAR s1,s2,s:STRING; B,T:ARRAY[0 100,0 100] OF INTEGER; m,n,len:INTEGER; PROCEDURE GetInput; VAR f:TEXT; BEGIN assign(f,'xaucon.inp'); reset(f); readln(f,s1); readln(f,s2); close(f); m:=length(s1); n:=length(s2); END; PROCEDURE Optimize; VAR i,j:INTEGER; BEGIN FOR i:=0 TO m DO B[i][0]:=0; FOR j:=0 TO n DO B[0][j]:=0; FOR i:=1 TO m DO FOR j:=1 TO n DO IF s1[i]=s2[j] THEN BEGIN B[i,j]:=B[i-1,j-1]+1; T[i,j]:=0; END ELSE IF B[i-1,j]>B[i,j-1] THEN BEGIN B[i,j]:=B[i-1,j]; T[i,j]:=1; END ELSE BEGIN B[i,j]:=B[i,j-1]; T[i,j]:=-1; END; END; PROCEDURE Trace; BEGIN len:=B[m,n]; s:=''; WHILE (m>0) AND (n>0) DO BEGIN IF T[m,n]=0 THEN BEGIN s:=s1[m]+s; m:=m-1; n:=n-1; END ELSE IF T[m,n]=1 THEN m:=m-1 ELSE n:=n-1; END; END; PROCEDURE PutOutput; VAR f:TEXT; i:INTEGER; BEGIN assign(f,'xaucon.out'); rewrite(f); writeln(f,len); write(f,s); close(f); END; BEGIN GetInput; Optimize; Trace; PutOutput; END. Cài đặt bài toán bằng ngôn ngữ C++ #include <iostream> #include <fstream> #include <string.h> using namespace std; #define Input "xaucon.inp" #define Output "xaucon.out" int main() { char *s1=new char[10000],*s2=new char[10000]; //Đọc file ifstream fi(Input); fi>>s1; fi.get(); fi>>s2; fi.close(); int m=strlen(s1),n=strlen(s2); //Tạo động mảng 2 chiều int **B=new int*[m+1]; int **T=new int*[m+1]; for (int i=0; i<=m; i++) { B[i]=new int[n+1]; T[i]=new int[n+1]; } //Khởi gán bảng phương án for (int i=0; i<=n; i++) B[0][i]=0; for (int i=0; i<=m; i++) B[i][0]=0; //Tính bảng phương án và bảng truy vết for (int i=1; i<=m; i++) for (int j=1; j<=n; j++) if (s1[i-1]==s2[j-1]) { B[i][j]=B[i-1][j-1]+1; T[i][j]=0; } else { if (B[i-1][j]>B[i][j-1]) { B[i][j]=B[i-1][j]; T[i][j]=-1; } else { B[i][j]=B[i][j-1]; T[i][j]=1; } } ofstream fo(Output); fo<<B[m][n]<<endl; int len=B[m][n]; char *s=new char[len+1]; s[len]=0; //Truy vết while (m>=0 && n>=0) { if (T[m][n]==0) { s[ len]=s1[m-1]; m ; n ; } else if (T[m][n]==-1) m ; else n ; } fo<<s; fo.close(); //Giải phóng các vùng nhớ cấp phát động for (int i=0; i<n; i++) { delete []B[i]; delete []T[i]; } delete []B; delete []T; }

Tài liệu liên quan

BÀI TOÁN TÌM QUÃNG ĐƯỜNG ĐI ĐƯỢC DÀI NHẤT VÀ NGẮN NHẤT TRONG DAO ĐỘNG ĐIỀU HOÀ(Chu Văn Biên)
- 1
- 8
- 116
luyện thi đh kit 1 (đặng việt hùng) - bài toán tìm dao động cực đại, cực tiểu p3 (bài tập tự luyện)
- 3
- 868
- 16
luyện thi đh kit 1 (đặng việt hùng) - bài toán tìm dao động cực đại, cực tiểu p4 (bài tập tự luyện)
- 4
- 739
- 16
luyện thi đh kit 1 (đặng việt hùng) - bài toán tìm vị trí cực đại, cực tiểu p5 (bài tập tự luyện)
- 3
- 859
- 18
luyện thi đh kit 1 (đặng việt hùng) - bài toán tìm vị trí dao động cực đại, cực tiểu p2 (bài tập tự luyện)
- 3
- 754
- 14
Tài liệu Tuyển chọn các bài toán điển hình luyện thi đại học pdf
- 18
- 986
- 3
Tài liệu Phương pháp lắc balô và thuật toán xấp xỉ dây con chung dài nhất. docx
- 12
- 557
- 2
Slide bài giảng toán lớp 7 bội chung nhỏ nhất
- 8
- 997
- 7
ĐỒ án tốt NGHIỆP đại học NGHIÊN cứu bài TOÁN SO KHỚP TIỀN tố dài NHẤT áp DỤNG TRONG ROUTER
- 80
- 857
- 1
Bài toán tìm chuỗi con chung dài nhất pdf
- 5
- 9
- 71