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