Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Divide et impera |
Pentru a calcula c.m.m.d.c . (cel mai mare divizor comun) a n numere memorate î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 c.m.m.d.c . pentru fiecare subvector prin apelul recursiv al funcției. Apoi, putem calcula c.m.m.d.c . al celor două subvectori .
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ă c.m.m.d.c .
#include < iostream >
using namespace std ;
int gcd ( int a, int b) {
if (b == 0 ) {
return a;
} else {
return gcd (b, a % b);
}
}
int divideEtImpera ( int v[], int start , int end ) {
if ( start == end ) {
return v[ start ];
} else {
int mid = ( start + end ) / 2 ;
int left = divideEtImpera (v, start , mid );
int right = divideEtImpera (v, mid + 1 , end );
return gcd ( left , right );
}
}
int main () {
int v[] = { 12 , 24 , 36 , 48 }; // Exemplu: vectorul { 12 , 24 , 36 , 48 }
int n = sizeof (v) / sizeof (v[ 0 ]);
int cmmdc = divideEtImpera (v, 0 , n - 1 );
cout << "C.M.M.D.C. este " << cmmdc << endl ;
return 0 ;
}
În acest exemplu, am calculat c.m.m.d.c . pentru vectorul {12, 24, 36, 48}
și am afișat rezultatul. În funcția gcd , am implementat algoritmul Euclid pentru calculul c.m.m.d.c . a două numere. În funcția divideEtImpera , verificăm dacă subvectorul are o singură valoare, caz în care returnăm valoarea respectivă. În caz contrar, împărțim subvectorul în două subvectori și calculăm c.m.m.d.c . pentru fiecare subvector prin apelul recursiv al funcției divideEtImpera . Apoi, calculăm c.m.m.d.c . al celor două subvectori prin apelul funcției gcd .using namespace std ;
int gcd ( int a, int b) {
if (b == 0 ) {
return a;
} else {
return gcd (b, a % b);
}
}
int divideEtImpera ( int v[], int start , int end ) {
if ( start == end ) {
return v[ start ];
} else {
int mid = ( start + end ) / 2 ;
int left = divideEtImpera (v, start , mid );
int right = divideEtImpera (v, mid + 1 , end );
return gcd ( left , right );
}
}
int main () {
int v[] = { 12 , 24 , 36 , 48 }; // Exemplu: vectorul { 12 , 24 , 36 , 48 }
int n = sizeof (v) / sizeof (v[ 0 ]);
int cmmdc = divideEtImpera (v, 0 , n - 1 );
cout << "C.M.M.D.C. este " << cmmdc << endl ;
return 0 ;
}
În acest exemplu, am calculat c.m.m.d.c . pentru vectorul {12, 24, 36, 48}
Acest algoritm are o complexitate temporală de O(n log n), deoarece împărțim vectorul în jumătate la fiecare apel recursiv și calculăm c.m.m.d.c . pentru două numere în O(log n) prin algoritmul Euclid.