Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Divide et impera |
Putem folosi algoritmul Divide et Impera pentru a interschimba coloana p cu coloana q într-o matrice cu n linii și m coloane. Algoritmul constă în împărțirea problemei în subprobleme mai mici, calcularea soluției pentru fiecare subproblemă și combinația soluțiilor pentru a obține soluția finală.
În cazul de față, putem împărți matricea în două submatrice și interschimba coloana p cu coloana q pentru fiecare submatrice prin apelul recursiv al funcției. Apoi, putem combina cele două submatrice pentru a obține matricea finală cu coloanele p și q interschimbate.
Pentru a implementa acest algoritm în C++, putem utiliza o funcție recursivă care primește matricea sub formă de vector bidimensional, numărul de linii și coloane, indicii coloanelor de interschimbat p și q și indicele de început și indicele de sfârșit al intervalului de evaluare pe linii. Funcția va returna matricea cu coloanele interschimbate.
# include < iostream >
using namespace std ;
void swapColumns ( int **a, int n, int m, int p, int q, int start, int end ) {
if (start > end ) {
return ;
}
for ( int i = start; i <= end ; i++) {
swap (a[i][p], a[i][q]);
}
int mid = (start + end ) / 2 ;
swapColumns (a, n, m, p, q, start, mid );
swapColumns (a, n, m, p, q, mid + 1 , end );
}
int main () {
int n, m, p, q;
cout << " Introduceti numarul de linii: " ;
cin >> n;
cout << " Introduceti numarul de coloane: " ;
cin >> m;
int **a = new int *[n];
for ( int i = 0 ; i < n; i++) {
a[i] = new int [m];
for ( int j = 0 ; j < m; j++) {
cout << "a[" << i << "][" << j << "] = " ;
cin >> a[i][j];
}
}
cout << " Introduceti coloana p: " ;
cin >> p;
cout << " Introduceti coloana q: " ;
cin >> q;
swapColumns (a, n, m, p, q, 0 , n - 1 );
// Afisarea matricei cu coloanele interschimbate
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
cout << a[i][j] << " " ;
}
cout << endl ;
}
for ( int i = 0 ; i < n; i++) {
delete [] a[i];
}
delete [] a;
return 0 ;
}
using namespace std ;
void swapColumns ( int **a, int n, int m, int p, int q, int start, int end ) {
if (start > end ) {
return ;
}
for ( int i = start; i <= end ; i++) {
swap (a[i][p], a[i][q]);
}
int mid = (start + end ) / 2 ;
swapColumns (a, n, m, p, q, start, mid );
swapColumns (a, n, m, p, q, mid + 1 , end );
}
int main () {
int n, m, p, q;
cout << " Introduceti numarul de linii: " ;
cin >> n;
cout << " Introduceti numarul de coloane: " ;
cin >> m;
int **a = new int *[n];
for ( int i = 0 ; i < n; i++) {
a[i] = new int [m];
for ( int j = 0 ; j < m; j++) {
cout << "a[" << i << "][" << j << "] = " ;
cin >> a[i][j];
}
}
cout << " Introduceti coloana p: " ;
cin >> p;
cout << " Introduceti coloana q: " ;
cin >> q;
swapColumns (a, n, m, p, q, 0 , n - 1 );
// Afisarea matricei cu coloanele interschimbate
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
cout << a[i][j] << " " ;
}
cout << endl ;
}
for ( int i = 0 ; i < n; i++) {
delete [] a[i];
}
delete [] a;
return 0 ;
}
Acest cod citește dimensiunile matricei, valorile sale și coloanele de interschimbat de la tastatură, apelează funcția swapColumns și afișează matricea cu coloanele interschimbate. Matricea este alocată dinamic cu ajutorul operatorului new și este dezalocată cu ajutorul operatorului delete .