Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Divide et impera |
Pentru a determina numărul de apariții ale unei valori x într-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 apariții al valorii x pentru fiecare subvector prin apelul recursiv al funcției. Apoi, putem combina numărul de apariții din ambele subvectori pentru a obține numărul total de apariții al valorii x.
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, precum și valoarea x ca parametri și returnează numărul de apariții.
#include < iostream >
using namespace std ;
int divideEtImpera ( int v[], int start , int end , int x) {
if ( start == end ) {
return v[ start ] == x ? 1 : 0 ;
} else {
int mid = ( start + end ) / 2 ;
int left = divideEtImpera (v, start , mid , x);
int right = divideEtImpera (v, mid + 1 , end , x);
return left + right ;
}
}
int main () {
int v[] = { 1 , 2 , 3 , 2 , 4 , 2 , 5 }; // Exemplu: vectorul { 1 , 2 , 3 , 2 , 4 , 2 , 5 }
int n = sizeof (v) / sizeof (v[ 0 ]);
int x = 2 ; // Exemplu: valoarea x = 2
int numarAparitii = divideEtImpera (v, 0 , n - 1 , x);
cout << "Valoarea " << x << " apare de " << numarAparitii << " ori." << endl ;
return 0 ;
}
În acest exemplu, am calculat numărul de apariții ale valorii 2 în vectorul {1, 2, 3, 2, 4, 2, 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 egalitatea cu valoarea x. În caz contrar, împărțim subvectorul în două subvectori și calculăm numărul de apariții al valorii x pentru fiecare subvector prin apelul recursiv al funcției divideEtImpera . Apoi, combinăm numărul de apariții din ambele subvectori pentru a obține numărul total de apariții al valorii x.using namespace std ;
int divideEtImpera ( int v[], int start , int end , int x) {
if ( start == end ) {
return v[ start ] == x ? 1 : 0 ;
} else {
int mid = ( start + end ) / 2 ;
int left = divideEtImpera (v, start , mid , x);
int right = divideEtImpera (v, mid + 1 , end , x);
return left + right ;
}
}
int main () {
int v[] = { 1 , 2 , 3 , 2 , 4 , 2 , 5 }; // Exemplu: vectorul { 1 , 2 , 3 , 2 , 4 , 2 , 5 }
int n = sizeof (v) / sizeof (v[ 0 ]);
int x = 2 ; // Exemplu: valoarea x = 2
int numarAparitii = divideEtImpera (v, 0 , n - 1 , x);
cout << "Valoarea " << x << " apare de " << numarAparitii << " ori." << endl ;
return 0 ;
}
În acest exemplu, am calculat numărul de apariții ale valorii 2 în vectorul {1, 2, 3, 2, 4, 2, 5}
Acest algoritm are o complexitate temporală de O(n log n)