online: 7; azi: 281; total: 52287 Manual clasa a xi a - Tehnici de programare - Metoda programarii dinamice

Probleme Rezolvate



Sa se afiseze cel mai mic numar cu exact n divizori
Se dau doua siruri de numere x
Se dau doua siruri de caractere a si b de lungime n
Se dau n numere naturale si un numar natural s
Se da un sir de n matrice a1
Se citesc de la tastatura doua siruri de caractere s1 si s2

Manual clasa a Xi a

Tehnici de programare

Metoda programarii dinamice
Se dau două şiruri de numere X=(x4, X2, ..., Xm ) si Y=(y1, Y2, … Ym ). Să se determine cel mai lung subşir comun al celor două şiruri . Şirul Z=(z1, z2, ..., Zk ) este subşir comun al şirurior X şi Y dacă el este subşir al şirului X şi subşir al şirului Y. De exemplu, dacă X=(1,2,3,2,2,1,4) şi Y=(2,1,3,1,2,4), şirul Z=(2,3,1,4) este un subşir comun al celor două şiruri . indicație. Valoarea asociată soluţiei este lungimea unui subşir comun, iar funcția recursivă defineşte valoarea lungimii maxime a unui subşir comun L( i,j ) unde i este indicele elementului cu care începe subşirul X, iar j este indicele elementului cu care începe subşirul Y.
# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_N = 1001 ;
int DP[MAX_N][MAX_N];
int LCS ( int X[], int Y[], int m, int n) {
// Cazurile de baza
for ( int i = 0 ; i <= m; i++) {
DP[i][ 0 ] = 0 ;
}
for ( int j = 0 ; j <= n; j++) {
DP[ 0 ][j] = 0 ;
}
// Construirea matricei DP
for ( int i = 1 ; i <= m; i++) {
for ( int j = 1 ; j <= n; j++) {
if (X[i -1 ] == Y[j -1 ]) {
DP[i][j] = 1 + DP[i -1 ][j -1 ];
} else {
DP[i][j] = max (DP[i][j -1 ], DP[i -1 ][j]);
}
}
}
// Reconstruirea solutiei
int i = m, j = n, k = 0 ;
int L = DP[m][n];
int sol[MAX_N];
while (i > 0 && j > 0 ) {
if (X[i -1 ] == Y[j -1 ]) {
sol[k++] = X[i -1 ];
i--;
j--;
L--;
} else if (DP[i][j -1 ] > DP[i -1 ][j]) {
j--;
} else {
i--;
}
}
// Afisarea solutiei
cout << "Cel mai lung subșir comun: " ;
for ( int l = k -1 ; l >= 0 ; l--) {
cout << sol[l] << " " ;
}
cout << endl ;
return DP[m][n];
}
int main () {
int m, n;
cout << " Introduceti dimensiunea sirului X: " ;
cin >> m;
int X[MAX_N];
cout << " Introduceti elementele sirului X: " ;
for ( int i = 0 ; i < m; i++) {
cin >> X[i];
}
cout << " Introduceti dimensiunea sirului Y: " ;
cin >> n;
int Y[MAX_N];
cout << " Introduceti elementele sirului Y: " ;
for ( int i = 0 ; i < n; i++) {
cin >> Y[i];
}
int lcsLen = LCS (X, Y, m, n);
cout << "Lungimea celui mai lung subșir comun: " << lcsLen << endl ;
return 0 ;
}

Această soluție folosește o matrice DP de dimensiune (m+1)x(n+1), unde DP( i,j ) reprezintă lungimea celui mai lung subșir comun al primelor i elemente din X și primele j elemente din Y.
Cazurile de bază sunt DP(i,0) = 0 și DP(0,j) = 0, deoarece niciunul dintre șiruri nu conține niciun element în cazul în care celălalt șir este vid.
Construirea matricei DP este realizată prin parcurgerea șirurilor X și Y și completarea matricei DP în funcție de lungimea celui mai lung subșir comun.
Dacă X(i-1) == Y(j-1), atunci DP( i,j ) = 1 + DP(i-1, j-1), deoarece cel mai lung subșir comun se poate obține prin adăugarea elementului X(i-1) la cel mai lung subșir comun al primelor i-1 elemente din X și primelor j-1 elemente din Y.
Dacă X(i-1) != Y(j-1), atunci DP( i,j ) = max (DP(i, j-1), DP(i-1, j)), deoarece cel mai lung subșir comun poate fi obținut fie din cel mai lung subșir comun al primelor i elemente din X și primelor j-1 elemente din Y, fie din cel mai lung subșir comun al primelor i-1 elemente din X și primelor j elemente din Y.
Reconstruirea soluției se face începând de la DP( m,n ) și mergând înapoi în matrice folosind aceleași reguli ca în construirea matricei DP.
Lungimea celui mai lung subșir comun este stocată în DP( m,n ) și se poate afișa împreună cu soluția obținută prin reconstruirea matricei DP.