chào mọi người! e có bài tập về tìm dãy con chung của 3 dãy số X, Y, Z. Ban đầu ý tưởng của e khi giải quyết bài toán là tìm dãy con của 2 dãy X và Y là 1 dãy Temp rồi lại tìm dãy con chung giữa Temp và Z. Nhưng e thấy nó không phải là dãy con dài nhất. Mọi người có cách nào giúp em giải quyết bài toán trên được không ạ. nếu có thể cho em xin code mẫu C hoặc C++ thì càng tốt ạ. e xin cảm ơn.
Tìm dãy con chung dài nhất của 3 dãy số X, Y, Z
Cách của bạn có gì không ổn chứ?
Sao lại không phải là dãi con dài nhất. Cho ví dụ được không?
1 Like
x: 12345467898
y: 12345967823
z: 12678498921
f(x, y) = 12345
f(z, f(x, y)) = 12
KQ: 678
1 Like
#include "Lib.h"
void Random(int a[], int n)
{
srand(time(NULL));
int randnum = 0;
for (int i = 0; i < n; i++)
{
//tao random phan tu tu 0 - 99
randnum = rand() % max;
a[0] = 0;
a[i+1] = randnum;
}
}
void Ghi_file(int a[], int n, string filename)
{
ofstream myFile;
myFile.open(filename, ios_base::out);
myFile << n << endl;
myFile << 0;
for (int i = 0; i < n; i++)
{
myFile << " " << a[i];
}
myFile.close();
cout << "Ghi file thanh cong" << endl;
}
void Doc_file(int a[], int &n, string filename)
{
ifstream myFile;
myFile.open(filename, ios_base::in);
if (myFile.fail() == true)
{
cout << "File khong ton tai";
}
else
{
myFile >> n;
for (int i = 0; i < n; i++)
{
myFile >> a[i];
}
}
myFile.close();
}
void Xuatmang(int a[], int n)
{
for (int i = 1; i < n; i++)
{
cout << a[i] << " ";
}
}
int Max(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void DayConChung(int a[], int m, int b[], int n, int c[])
{
int i, j;
int temp[100][100];
for (i = 0; i <= m; i++)
{
temp[i][0] = 0;
}
for (j = 0; j <= n; j++)
{
temp[0][j] = 0;
}
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
if (a[i] == b[j])
{
temp[i][j] = temp[i - 1][j - 1] + 1;
}
else
{
temp[i][j] = Max(temp[i - 1][j], temp[i][j - 1]);
}
}
}
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
cout << " " << temp[i][j];
}
cout << endl;
}
cout << endl;
i = m - 1;
j = n - 1;
int k = temp[i][j];
int t = 0;
while ((i > 0) && (j > 0))
{
if (a[i] == b[j])
{
c[t] = b[j];
cout << k << ": " << c[t] << endl;
t++;
i--;
j--;
k--;
}
else
{
if (temp[i][j - 1] > temp[i - 1][j])
{
j--;
}
else
{
i--;
}
}
}
int x = t + 1;
Ghi_file(c, x, "Dayconchungdainhat.txt");
}
int main()
{
int X[100], Y[100], Z[100], T[100], Daycon[100];
int x, y, z, t, d;
/*cout << "x = "; cin >> x;*/
/*cout << "y = "; cin >> y;*/
/*cout << "z = "; cin >> z;*/
/*Random(X, x);*/
/*Random(Y, y);*/
/*Random(Z, z);*/
/*Ghi_file(X, x, "DayX.txt");*/
/*Ghi_file(Y, y, "DayY.txt");*/
/*Ghi_file(Z, z, "DayZ.txt");*/
Doc_file(X, x, "DayX.txt");
cout << "Mang X la:" << endl;
Xuatmang(X, x);
cout << endl;
Doc_file(Y, y, "DayY.txt");
cout << "Mang Y la:" << endl;
Xuatmang(Y, y);
cout << endl;
DayConChung(Y, y, X, x, T);
Doc_file(T, t, "Dayconchungdainhat.txt");
cout << "Day con chung dai nhat giua X va Y la:" << endl;
Xuatmang(T, t);
Doc_file(Z, z, "DayZ.txt");
cout << endl;
cout << "Mang Z la:" << endl;
Xuatmang(Z, z);
cout << endl;
DayConChung(T, t, Z, z, Daycon);
Doc_file(Daycon, d, "Dayconchungdainhat.txt");
cout << "Day con chung dai nhat giua X, Y va Z la:" << endl;
Xuatmang(Daycon, d);
_getch();
}
mong bác chỉ giáo :((
Cảm ơn @Phong_Ky_Vo
Ban đầu mình nghĩ là bạn ấy tìm nhiều mảng con chứ không phải 1 mảng.
Cách là phải tìm CÁC mảng con của X và Y trước. Sau đó xét từng mảng con đó với Z.
1 Like
for (int i = 1; i < len_x; i++)
for (int j = 1; j < len_y; j++)
for (int k = 1; k < len_z; k++) {
if (x[i] == y[j] && y[j] == z[k])
temp[i][j][k] = temp[i-1][j-1][k-1] + 1;
else
temp[i][j][k] = max(temp[i-1][j][k], temp[i][j-1][k], temp[i][j][k-1]);
}
3 Likes
Chào các bác!!! Cảm ơn các bác…Em đã giải quyết xong vấn đề và đây là code của em.
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include "conio.h";
using namespace std;
// tìm max
int max(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
//Hàm tìm dãy con chung lớn nhất của 3 dãy
void LCSLength(string X, string Y, string Z)
{
int i, j, k;
int m = X.length(), n = Y.length(), o = Z.length();
// X[0..i-1], Y[0..j-1], Z[0..k-1]
//khai báo mảng 3 chiều làm bảng phương án
int L[50][50][50];
// Khởi tạo giá trị ban đầu cho bảng phương án
/*memset(L, 0, sizeof L);*/
for (i = 0; i <= m; i++)
{
for (j = 0; j <= n; j++)
{
for (k = 0; k <= o; k++)
{
L[i][0][0] = 0;
L[0][j][0] = 0;
L[0][0][j] = 0;
}
}
}
// Duyệt từ đầu đến cuối mảng 3 chiều để xây dựng bảng phương án
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
for (k = 1; k <= o; k++)
{
// nếu ký tự hiện tại trùng nhau trả về như bên dưới
if (X[i - 1] == Y[j - 1] && Y[j - 1] == Z[k - 1])
L[i][j][k] = L[i - 1][j - 1][k - 1] + 1;
// nếu ký tự hiện tại đang xét không trùng nhau trả về giá trị max
else
L[i][j][k] = max(max(L[i - 1][j][k], L[i][j - 1][k]), L[i][j][k - 1]);
}
}
}
//in ra độ dài dãy con chung
//độ dài của dãy con sẽ là phần tử cuối cùng trong bảng phương án
cout << "Do dai day con chung la: " << L[m][n][o];
cout << endl;
//Truy vết từ cuối bảng phương án về đầu để tìm dãy con
while (m > 0 && n > 0 && o > 0)
{
int step = L[m][n][o];
if (X[m - 1] == Y[n - 1] && Y[n - 1] == Z[o - 1])
{
cout << step << ": " << X[m - 1] << endl;
m--;
n--;
o--;
step--;
}
else if (step == L[m - 1][n][o])
{
m--;
}
else if (step == L[m][n - 1][o])
{
n--;
}
else
{
o--;
}
}
}
int main()
{
string X = "ABCBDAB", Y = "BDCABA", Z = "BADACB";
LCSLength(X, Y, Z);
_getch();
}
3 Likes
bạn chuyển sang kiểu char rồi chia nhỏ 1 chuỗi xong dùng hàm strstr() để giải quyết xem có ok hơn k?
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?