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 caractere A şi B de lungime n, respectiv m. Într-un şir de caractere se pot executa numai următoarele trei operații prin care se poate transforma un şir S(i) — şte rge caracterul din poziția i, I( i,c ) — inserează caracterul c în poziţia i şi M( i,c ) — înlocuieşte caracterul din poziţia i cu caracterul c. Să se transforme şirul A în şirul B folosind un număr minim de operaţii . Problema se va rezolva în două variante: a) transformările se vor aplica de la stânga la dreapta; b) transformările se vor aplica de la dreapta la stânga.
Această problemă poate fi rezolvată cu programare dinamică. Pentru a minimiza numărul de operații necesare pentru a transforma șirul A în șirul B, putem construi o matrice DP de dimensiune (n+1)x(m+1), unde n și m sunt lungimile șirurilor A și B, astfel încât DP(i, j) să reprezinte numărul minim de operații necesare pentru a transforma primele i caractere ale șirului A în primele j caractere ale șirului B.
Observăm că pentru a ajunge la un anumit caracter din B, putem realiza următoarele operații asupra caracterelor din A:
Astfel, putem construi matricea DP după cum urmează:
Pentru a reconstrui soluția, începem de la DP(n, m) și comparăm valoarea curentă a DP( i,j ) cu DP(i-1,j-1), DP(i-1,j) și DP(i,j-1). Dacă DP( i,j ) este egal cu 1 + DP(i-1,j-1), atunci înlocuim caracterul din poziția i cu caracterul corespunzător din B și continuăm cu DP(i-1,j-1). Dacă DP( i,j ) este egal cu 1 + DP(i-1,j), atunci ștergem caracterul din poziția i și continuăm cu DP(i-1,j). În fine, dacă DP( i,j ) este egal cu 1 + DP(i,j-1), atunci inserăm caracterul din poziția j în poziția i și continuăm cu DP(i,j-1).
Iată soluția în C++ pentru varianta în care transformările se aplică de la stânga

# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_N = 1001 ;
int DP[MAX_N][MAX_N];
int minOpsL2R ( const string & A, const string & B) {
int n = A. length ();
int m = B. length ();
// Cazurile de bază
for ( int i = 0 ; i <= n; i++) {
DP[i][ 0 ] = i;
}
for ( int j = 0 ; j <= m; j++) {
DP[ 0 ][j] = j;
}
// Construirea matricei DP
for ( int i = 1 ; i <= n; i++) {
for ( int j = 1 ; j <= m; j++) {
if (A[i -1 ] == B[j -1 ]) {
DP[i][j] = DP[i -1 ][j -1 ];
} else {
DP[i][j] = 1 + min ( min (DP[i -1 ][j], DP[i][j -1 ]), DP[i -1 ][j -1 ]);
}
}
}
// Reconstruirea soluției
int i = n, j = m;
int numOps = DP[n][m];
char sol[MAX_N];
while (i > 0 && j > 0 ) {
if (A[i -1 ] == B[j -1 ]) {
sol[ numOps ] = A[i -1 ];
i--;
j--;
numOps --;
} else if (DP[i -1 ][j -1 ] <= DP[i -1 ][j] && DP[i -1 ][j -1 ] <= DP[i][j -1 ]) {
sol[ numOps ] = B[j -1 ];
i--;
j--;
numOps --;
} else if (DP[i][j -1 ] <= DP[i -1 ][j] && DP[i][j -1 ] <= DP[i -1 ][j -1 ]) {
sol[ numOps ] = B[j -1 ];
j--;
numOps --;
} else if (DP[i -1 ][j] <= DP[i][j -1 ] && DP[i -1 ][j] <= DP[i -1 ][j -1 ]) {
sol[ numOps ] = A[i -1 ];
i--;
numOps --;
}
}
while (i > 0 ) {
sol[ numOps ] = A[i -1 ];
i--;
numOps --;
}
while (j > 0 ) {
sol[ numOps ] = B[j -1 ];
j--;
numOps --;
}
// Afisarea soluției
cout << " Numar minim de operatii : " << DP[n][m] << endl ;
cout << " Sirul A modificat: " ;
for ( int k = 1 ; k <= DP[n][m]; k++) {
cout << sol[k];
}
cout << endl ;
return DP[n][m];
}
int main () {
string A, B;
cout << " Introduceti sirul A: " ;
cin >> A;
cout << " Introduceti sirul B: " ;
cin >> B;
minOpsL2R (A, B);
return 0 ;
}
Această soluție utilizează o matrice DP de dimensiune (n+1)x(m +1), unde n și m sunt lungimile șirurilor A și B. După ce matricea DP este construită, reconstruim soluția plecând de la DP(n, m) și comparând valorile DP(i-1,j-1), DP(i-1,j) și DP(i,j-1) pentru a determina ce operație trebuie efectuată. Algoritmul merge pe diagonală în matrice, începând de la elementul DP(n, m) și se deplasează spre stânga-sus, dreapta-sus și jos-stânga în funcție de valorile din matrice.
Dacă DP( i,j ) este egal cu DP(i-1,j-1), înseamnă că nu este necesară nicio operație, deoarece caracterele din A și B sunt egale. În acest caz, adăugăm caracterul corespunzător din A sau B la soluție și ne deplasăm în diagonală în matrice.
Dacă DP( i,j ) este egal cu DP(i-1,j-1)+1, înseamnă că trebuie să înlocuim caracterul din A(i-1) cu caracterul corespunzător din B(j-1). Adăugăm caracterul corespunzător din B la soluție și ne deplasăm în diagonală în matrice.
Dacă DP( i,j ) este egal cu DP(i-1,j)+1, înseamnă că trebuie să ștergem caracterul din A(i-1). Adăugăm caracterul corespunzător din A la soluție și ne deplasăm în sus în matrice.
Dacă DP( i,j ) este egal cu DP(i,j-1)+1, înseamnă că trebuie să inserăm caracterul din B(j-1) în A(i). Adăugăm caracterul corespunzător din B la soluție și ne deplasăm în stânga în matrice.
În cele din urmă, afișăm numărul minim de operații și șirul A modificat.
Iată soluția în C++ pentru varianta în care transformările se aplică de la dreapta la stânga:
# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_N = 1001 ;
int DP[MAX_N][MAX_N];
int minOpsR2L ( const string & A, const string & B) {
int n = A. length ();
int m = B. length ();
// Cazurile de bază
for ( int i = 0 ; i <= n; i++) {
DP[i][m] = n - i;
}
for ( int j = 0 ; j <= m; j++) {
DP[n][j] = m - j;
}
// Construirea matricei DP
for ( int i = n -1 ; i >= 0 ; i--) {
for ( int j = m -1 ; j >= 0 ; j--) {
if (A[i] == B[j]) {
DP[i][j] = DP[i+ 1 ][j+ 1 ];
} else {
DP[i][j] = 1 + min ( min (DP[i+ 1 ][j], DP[i][j+ 1 ]), DP[i+ 1 ][j+ 1 ]);
}
}
}
// Reconstruirea soluției
int i = 0 , j = 0 ;
int numOps = DP[ 0 ][ 0 ];
char sol[MAX_N];
while (i < n && j < m) {
if (A[i] == B[j]) {
sol[ numOps ] = A[i];
i++;
j++;
numOps --;
} else if (DP[i+ 1 ][j+ 1 ] <= DP[i+ 1 ][j] && DP[i+ 1 ][j+ 1 ] <= DP[i][j+ 1 ]) {
sol[ numOps ] = B[j];
i++;
j++;
numOps --;
} else if (DP[i][j+ 1 ] <= DP[i+ 1 ][j] && DP[i][j+ 1 ] <= DP[i+ 1 ][j+ 1 ]) {
sol[ numOps ] = B[j];
j++;
numOps --;
} else if (DP[i+ 1 ][j] <= DP[i][j+ 1 ] && DP[i+ 1 ][j] <= DP[i+ 1 ][j+ 1 ]) {
sol[ numOps ] = A[i];
i++;
numOps --;
}
}
while (i < n) {
sol[ numOps ] = A[i];
i++;
numOps --;
}
while (j < m) {
sol[ numOps ] = B[j];
j++;
numOps --;
}
// Afisarea soluției
cout << " Numar minim de operatii : " << DP[ 0 ][ 0 ] << endl ;
cout << " Sirul A modificat: " ;
for ( int k = 1 ; k <= DP[ 0 ][ 0 ]; k++) {
cout << sol[k];
}
cout << endl ;
return DP[ 0 ][ 0 ];
}
int main () {
string A, B;
cout << " Introduceti sirul A: " ;
cin >> A;
cout << " Introduceti sirul B: " ;
cin >> B;
minOpsR2L (A, B);
return 0 ;
}

Această soluție este similară cu cea pentru transformările de la stânga la dreapta, dar matrice este parcursă în sens invers. Astfel, începem de la colțul dreapta-jos și ne deplasăm spre stânga-sus în matrice.
Cazurile de bază sunt similare cu cele pentru transformările de la stânga la dreapta, cu diferența că acum se pornește de la capătul opus al matricei.
Construirea matricei DP este realizată în același mod ca și în varianta anterioară, doar că se începe de la n-1 și m-1 și se parcurge matricea în ordine inversă.
Reconstruirea soluției este, de asemenea, similară cu varianta anterioară, dar acum se începe de la capătul opus al matricei și se merge în direcția opusă.
Observați că această soluție poate fi optimizată pentru a folosi o singură matrice DP de dimensiune (m+1) și o variabilă temporară pentru a reține valoarea DP(i,j-1) în timpul construirii matricei. Această optimizare reduce spațiul necesar de la O(nm) la O(m).