Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Divide et impera |
Pentru a calcula suma 1+1x2+1x2x3+...+1x2x3x... xn , 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 problema în două subprobleme:
Putem apoi combina soluțiile pentru a obține suma finală.
Pentru a implementa acest algoritm în C++, putem utiliza o funcție recursivă care primește n ca parametru și returnează suma respectivă.
# include < iostream >
using namespace std ;
int divideEtImpera ( int n) {
if (n == 1 ) {
return 1 ;
} else {
int half = n / 2 ;
int sum = 0 ;
int product = 1 ;
for ( int i = 1 ; i <= half; i++) {
sum += i;
product *= (half + i);
}
return product * divideEtImpera (half) + sum * divideEtImpera (n - half);
}
}
int main () {
int n = 5 ; // Exemplu: n = 5
cout << "Suma este " << divideEtImpera (n) << endl ;
return 0 ;
}
using namespace std ;
int divideEtImpera ( int n) {
if (n == 1 ) {
return 1 ;
} else {
int half = n / 2 ;
int sum = 0 ;
int product = 1 ;
for ( int i = 1 ; i <= half; i++) {
sum += i;
product *= (half + i);
}
return product * divideEtImpera (half) + sum * divideEtImpera (n - half);
}
}
int main () {
int n = 5 ; // Exemplu: n = 5
cout << "Suma este " << divideEtImpera (n) << endl ;
return 0 ;
}
În acest exemplu, am calculat suma pentru n = 5 și am afișat rezultatul. În funcția divideEtImpera , verificăm dacă n este 1, caz în care returnăm 1. În caz contrar, împărțim problema în două subprobleme, calculăm suma și produsul corespunzătoare pentru fiecare subproblemă și apoi combinăm soluțiile pentru a obține soluția finală.
Acest algoritm are o complexitate temporală de O(n log n), deoarece împărțim problema în jumătate la fiecare apel recursiv.