Ridicarea la putere este o operație binecunoscută, formulă uzuală fiind:
Un algoritm care implementează această metodă va avea complexitate liniară,
int Putere(int A , int n) { int P = 1 ; for(int i = 1 ; i <= n ; i ++) P = P * A; return P; }
Descriere
O metodă mai bună este cea numită exponențierea rapidă , sau ridicarea la putere în timp logaritmic, complexitatea sa fiind
Exemplu
Să calculăm
, deoarece25
este impar , deoarece24
este par , deoarece12
este par , deoarece6
este par , deoarece3
este impar , deoarece2
este par , deoarece1
este impar
Atunci în ordine inversă:
Constatăm că numărul înmulțirilor efectuate este mult mai mic decât în cazul primei metode.
Implementare recursivă
Implementarea recursivă este directă:
int Putere(int A , int n) { if(n == 0) return 1; if(n % 2 == 1) return A * Putere(A , n - 1); int P = Putere(A , n / 2); return P * P; }
Implementare iterativă
Să considerăm
Atunci
Se figurează următoarea idee, pentru a determina A
n
:
- vom determina un produs
P
, format din factori de formaA
1
,A
2
,A
4
,A
8
, … - determinăm cifrele reprezentării în baza
2
a luin
, începând cu cea mai nesemnificativă:- dacă cifra curentă este
1
, înmulțim peA
laP
,P = P * A;
- înmulțim pe
A
cu el însuși,A = A * A;
, obținând următoarea putere din șirul de mai sus
- dacă cifra curentă este
Implementare C++:
int Putere(int A , int n) { int P = 1; while(n) { if(n % 2 == 1) P = P * A; A = A * A; n /= 2; } return P; }
altă variantă, care folosește operațiile pe biți:
int Putere(int A , int n) { int P = 1; for(int k = 1 ; k <= n ; k <<= 1) { if((n & k)) P *= A; A = A * A; } return P; }
Observații
- ridicarea la putere rapidă poate fi folosită și pentru:
- operații modulo (determinarea restului împărțirii rezultatului la o valoare dată)
- numere mari
- ridicarea la putere a matricelor
- ridicarea la putere a polinoamelor
Probleme ataşate
Nr. | Problema | Clasa | Dificultate | Operații I/O |
---|---|---|---|---|
1 | #2398 - Moka | 9 | dificilă | fișiere |
2 | #2404 - Test | 9 | ușoară | fișiere |