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 dă un şir de n matrice A1, A2, ..., An şi trebuie să se calculeze produsul lor: A1xA2x… xAn . Fiecare matrice Ai, cu 2<=i<=n, are pi-1 linii şi pi coloane (două matrice A şi B se pot înmulți numai dacă numărul de coloane din matricea A este egal cu numărul de linii din matricea B). Să se pună în acest produs parantezele potrivite astfel încât numărul de înmulţiri să fie minim (deoarece înmulţirea matricelor este asociativă, inserarea parantezelor nu modifică rezultatul). Indicaţie . Fiind date două matrice Ap,q şi Bq,r , matricea produs Cp,r conţine elementele:
Timpul necesar pentru calculul matricei produs este determinat de numărul de înmulţiri scalare: aik * bkj . De exemplu, pentru produsul A1xAzxA3, în care matricele au dimensiunile 10x20, 20x5 şi , respectiv, 5x40, numărul de înmulţiri scalare pentru paranterizarea (A1x(A2xA3)) este 10x20x5+10x5x40=1200, iar pentru paranterizarea (A1x(A2xA3)) este 10x20x40+20x5x40=12000 (de 10 ori mai mare decât în exemplul anterior). Valoarea asociată soluției este numărul de înmulţiri scalare, iar funcţia recursivă m( i,j ) defineşte numărul minim de înmulţiri scalare pentru calculul matricei produs Ajx ... xAj .
Numărul minim de înmulţiri scalare pentru calculul produsului A1x... xAn este m(1,n). Pentru a memora poziţiile parantezelor optime se va folosi matricea s, în care elementul sij are valoarea k ce reprezintă poziția parantezei optime în produsul Ajx ... xAj . Altfel spus, sij este egal cu k pentru care m( i,j ) = m( i,k ) + m(k+1,j) + pi-1 x Pk x pj .
Această problemă poate fi rezolvată folosind programarea dinamică. Avem de calculat numărul minim de înmulțiri scalare necesare pentru a înmulți matricele date, dar și poziția parantezelor optime în produsul final.
Pentru a rezolva această problemă, putem folosi o matrice DP de dimensiune (n+1)x(n+1), unde DP( i,j ) reprezintă numărul minim de înmulțiri scalare necesare pentru a înmulți matricele de la i la j. De asemenea, vom folosi o matrice s de aceeași dimensiune pentru a memora pozițiile parantezelor optime.
Pentru a calcula valorile matricelor DP și s, putem folosi următoarele relații de recurență:
DP( i,j ) = 0 pentru i = j (o singură matrice nu necesită înmulțiri scalare) DP( i,j ) = min(DP( i,k ) + DP(k+1,j) + pi-1 x Pk x pj ), unde i <= k < j s( i,j ) = k, unde DP( i,j ) = DP( i,k ) + DP(k+1,j) + pi-1 x Pk x pj și k este poziția parantezei optime în produsul Aj x ... x Aj
Pentru a reconstrui soluția, putem parcurge matricea s începând de la poziția (1,n) și inserând parantezele corespunzătoare.
Implementarea soluției în C++ poate arăta astfel:

# include < iostream >
# include < limits >
using namespace std ;
const int MAX_N = 100 ;
int p[MAX_N + 1 ];
int m[MAX_N + 1 ][MAX_N + 1 ];
int s[MAX_N + 1 ][MAX_N + 1 ];
void matrixChainOrder ( int n) {
for ( int i = 1 ; i <= n; i++) {
m[i][i] = 0 ;
}
for ( int l = 2 ; l <= n; l++) {
for ( int i = 1 ; i <= n - l + 1 ; i++) {
int j = i + l - 1 ;
m[i][j] = numeric_limits < int >:: max ();
for ( int k = i; k <= j - 1 ; k++) {
int q = m[i][k] + m[k + 1 ][j] + p[i - 1 ] * p[k] * p[j];
if (q < m[i][j]) {
m[i][j] = q;
s[i][j] = k;
}
}
}
}
}
void printOptimalParens ( int i, int j) {
if (i == j) {
cout << "A" << i;
} else {
cout << "(" ;
printOptimalParens (i, s[i][j]);
cout << " x " ;
printOptimalParens (s[i][j] + 1 , j);
cout << ")" ;
}
}
int main () {
int n;
cout << " Introduceti numarul de matrici : " ;
cin >> n;
cout << " Introduceti dimensiunile matricilor :\n" ;
for ( int i = 0 ; i <= n; i++) {
cin >> p[i];
}
matrixChainOrder (n);
cout << " Numarul minim de inmultiri scalare este: " << m[ 1 ][n] << endl ;
cout << " Parenezarea optima este: " ;
printOptimalParens ( 1 , n);
cout << endl ;
return 0 ;
}

Acest program calculează parantezarea optimă pentru produsul de matrice folosind programarea dinamică și afișează numărul minim de înmulțiri scalare și parantezarea optimă. Pentru a face acest lucru, utilizează matricele m și s pentru a stoca numărul minim de înmulțiri scalare și poziția parantezei optime.
Sa presupunem că avem matricile A1, A2 și A3 cu dimensiunile următoare:
A1: 5x10 A2: 10x3 A3: 3x12
Atunci, în momentul rulării programului, trebuie să introduceți dimensiunile astfel:
5 10 3 12
Iar programul va afișa numărul minim de înmulțiri scalare necesare pentru a obține produsul matricelor și pozițiile optime ale parantezelor, conform algoritmului explicat anterior.