Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Divide et impera |
Pentru a număra elementele pare dintr-un vector, putem folosi algoritmul Divide et Impera . 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 vectorul în două subvectori și calcula numărul de elemente pare pentru fiecare subvector prin apelul recursiv al funcției. Apoi, putem combina numărul de elemente pare din ambele subvectori pentru a obține numărul de elemente pare al întregului vector.
Pentru a implementa acest algoritm în C++, putem utiliza o funcție recursivă care primește vectorul, indicele de început și indicele de sfârșit ca parametri și returnează numărul de elemente pare.
#include < iostream >
using namespace std ;
int divideEtImpera ( int v[], int start , int end ) {
if ( start == end ) {
return v[ start ] % 2 == 0 ? 1 : 0 ;
} else {
int mid = ( start + end ) / 2 ;
int left = divideEtImpera (v, start , mid );
int right = divideEtImpera (v, mid + 1 , end );
return left + right ;
}
}
int main () {
int v[] = { 1 , 2 , 3 , 4 , 5 }; // Exemplu: vectorul { 1 , 2 , 3 , 4 , 5 }
int n = sizeof (v) / sizeof (v[ 0 ]);
int numarElementePare = divideEtImpera (v, 0 , n - 1 );
cout << " Numarul de elemente pare este " << numarElementePare << endl ;
return 0 ;
}
În acest exemplu, am calculat numărul de elemente pare din vectorul {1, 2, 3, 4, 5}
și am afișat rezultatul. În funcția divideEtImpera , verificăm dacă subvectorul are o singură valoare, caz în care returnăm 1 sau 0 în funcție de paritatea valorii. În caz contrar, împărțim subvectorul în două subvectori și calculăm numărul de elemente pare pentru fiecare subvector prin apelul recursiv al funcției divideEtImpera . Apoi, combinăm numărul de elemente pare din ambele subvectori pentru a obține numărul de elemente pare al întregului vector.using namespace std ;
int divideEtImpera ( int v[], int start , int end ) {
if ( start == end ) {
return v[ start ] % 2 == 0 ? 1 : 0 ;
} else {
int mid = ( start + end ) / 2 ;
int left = divideEtImpera (v, start , mid );
int right = divideEtImpera (v, mid + 1 , end );
return left + right ;
}
}
int main () {
int v[] = { 1 , 2 , 3 , 4 , 5 }; // Exemplu: vectorul { 1 , 2 , 3 , 4 , 5 }
int n = sizeof (v) / sizeof (v[ 0 ]);
int numarElementePare = divideEtImpera (v, 0 , n - 1 );
cout << " Numarul de elemente pare este " << numarElementePare << endl ;
return 0 ;
}
În acest exemplu, am calculat numărul de elemente pare din vectorul {1, 2, 3, 4, 5}
Acest algoritm are o complexitate temporală de O(n log n), deoarece împărțim vectorul în jumătate la fiecare apel recursiv.