Menu
Probleme Rezolvate
Manual clasa a Xi a |
Tehnici de programare |
Divide et impera |
P utem folosi algoritmul Divide et Impera pentru a calcula valoarea unui polinom P(x) într-un punct x precizat. 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 polinomul în două jumătăți și calcula valoarea polinomului pentru fiecare jumătate prin apelul recursiv al funcției. Apoi, putem combina valorile obținute din cele două jumătăți pentru a obține valoarea finală a polinomului în punctul x.
Pentru a implementa acest algoritm în C++, putem utiliza o funcție recursivă care primește polinomul sub formă de vector de coeficienți, gradul polinomului, punctul x și indicele de început și indicele de sfârșit al intervalului de evaluare. Funcția va returna valoarea polinomului în punctul x pentru intervalul de evaluare dat.
#include < iostream >
using namespace std ;
int hornerDivideEtImpera ( int a[], int n, int x, int start , int end ) {
if ( start == end ) {
return a[ start ];
} else {
int mid = ( start + end ) / 2 ;
int left = hornerDivideEtImpera (a, n, x, start , mid );
int right = hornerDivideEtImpera (a, n, x, mid + 1 , end );
return left * pow (x, ( end - mid )) + right ;
}
}
int main () {
int a[] = { 2 , 1 , -1 , 3 }; // Exemplu: polinomul 2 x ^ 3 + x ^ 2 - x + 3
int n = sizeof (a) / sizeof (a[ 0 ]) - 1 ;
int x = 2 ; // Exemplu: evaluarea polinomului in punctul x = 2
int result = hornerDivideEtImpera (a, n, x, 0 , n);
cout << "Valoarea polinomului in punctul " << x << " este " << result << endl ;
return 0 ;
}
using namespace std ;
int hornerDivideEtImpera ( int a[], int n, int x, int start , int end ) {
if ( start == end ) {
return a[ start ];
} else {
int mid = ( start + end ) / 2 ;
int left = hornerDivideEtImpera (a, n, x, start , mid );
int right = hornerDivideEtImpera (a, n, x, mid + 1 , end );
return left * pow (x, ( end - mid )) + right ;
}
}
int main () {
int a[] = { 2 , 1 , -1 , 3 }; // Exemplu: polinomul 2 x ^ 3 + x ^ 2 - x + 3
int n = sizeof (a) / sizeof (a[ 0 ]) - 1 ;
int x = 2 ; // Exemplu: evaluarea polinomului in punctul x = 2
int result = hornerDivideEtImpera (a, n, x, 0 , n);
cout << "Valoarea polinomului in punctul " << x << " este " << result << endl ;
return 0 ;
}
În acest exemplu, am calculat valoarea polinomului 2x^3 + x^2 - x + 3 în punctul x = 2 utilizând algoritmul Divide et Impera și am afișat rezultatul. În funcția hornerDivideEtImpera , am împărțit polinomul în două jumătăți și calculat valoarea polinomului pentru fiecare jumătate prin apelul recursiv al funcției hornerDivideEtImpera . Apoi, am combinat valorile obținute din cele două jumătăți utilizând formula Horner modificată pentru intervalul de evaluare dat.
Acest algoritm are o complexitate temporală de O(n log n)