Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidă
Ridicarea la putere este o operație bineștiută, valoarea an
fiind egală cu:
Algoritmul de determinare a ridicării la putere este una ușor de intuit, având complexitatea O(n) liniară:
int rasp = 1;
for(int i = 1; i <= n; i++) {
rasp = rasp * a;
}
cout << a << "^" << n << " = " << rasp;
Mai precis, pentru a calcula operația an
ne trebuie n
operații de
înmulțire… Cum putem optimiza algoritmul?
Cum putem ridica la putere într-un mod eficient
O metodă mai eficientă de a ridica la putere este ridicarea la putere în timp
logaritmic, numită și exponențierea rapidă. Complexitatea acestui algoritm
este O(log2 n)
. Această complexitate este incredibil de mică — spre exemplu,
pentru a ridica un număr la puterea 1.000.000.000
(un miliard), facem
aproximativ 30
de operații de înmulțire, în loc de un miliard cât ar fi luat
cu metoda anterioară.
Cum funcționează exponențierea rapidă
Algoritmul de ridicare la putere în timp logaritmic se bazează pe următoarea observație:
Cu această observație, putem calcula 220
astfel:
-
220 = (210)2
, deoarecen = 20
este par; -
210 = (25)2
, deoarecen = 10
este par; -
25 = 2 * (22)2
, deoarecen = 5
este impar; -
22 = (21)2
, deoarecen = 2
este par; -
21 = 2 * (20)2
, deoarecen = 1
este impar; -
20 = 1
.
Observăm că în loc să facem 20
de înmulțiri, efectuăm doar 6
.
Implementare recursivă a exponențierii rapide
Implementarea recursivă folosește exact observația de mai sus:
int ridicare(int a, int n) {
if(n == 0)
return 1;
if(n % 2 == 1) {
int next = ridicare(a, (n - 1) / 2);
return a * (next * next);
} else {
int next = ridicare(a, n / 2);
return next * next;
}
}
Implementarea iterativă a exponențierii rapide
Implementarea iterativă diferă un pic, însă se bazează pe aceeași idee. Să
reprezentăm exponentul n
ca sumă de puteri de 2
. Spre exemplu, pentru n = 20
, avem suma n = 4 + 16
. Prin urmare, operația `an = a20 = a(4 + 16) = a4
- a16 = (a1)0 * (a2)0 * (a4)1 * (a8)1 * (a16)1
, unde exponenții de
0și de
1este reprezentarea binară a lui
n = 20(
10100). Cu această idee, vom lua cifrele exponentului
nîn baza
2, de la ultima cifră către prima. Dacă cifra curentă este
1, atunci înmulțim răspunsul cu baza
a. La fiecare pas, vom ridica baza
a` la pătrat.
Iată implementarea în C++:
int ridicare(int a, int n) {
int rasp = 1;
while(n > 0) {
if(n % 2 == 1)
rasp = rasp * a;
a = a * a;
n /= 2;
}
return rasp;
}
Probleme rezolvate
#2398 Moka (PbInfo)
Moca dorește să posteze pe Pbinfo a
probleme de dificultate b
. Durata
postării celor a probleme de dificultate b
este restul împărțirii lui ab
la 1999999973
. Ajutați-l pe Moca să calculeze durata postării celor a
probleme de dificultate b
. Pentru enunțul complet și testarea codului poți
vizita această pagină.
Exemplu: Pentru a = 2
și b = 4
, avem rezultatul 24 = 16
.
Rezolvare: Deoarece b
poate atinge valori mai mari de patru miliarde,
rezolvarea problemei constă în aplicarea ridicării la putere în timp
logaritmic. Observăm că rezultatul operației poate depăși cu mult orice tip de
date (int
, long long
), astfel că după fiecare operație, trebuie să aplicăm
restul împărțirii la 1999999973
. Cum 1999999973
este un număr prim,
rezultatul nu va atinge valoarea 0
.
//Rezolvarea problemei #2398 Moka de pe PbInfo
//Explicații: https://infoas.ro
//Enunț: https://www.pbinfo.ro/probleme/2398/moka
#include <fstream>
using namespace std;
ifstream fin("moka.in");
ofstream fout("moka.out");
long long a, b;
long long ridicare(long long a, long long n) {
long long rasp = 1;
a = a % 1999999973; //În cazul în care baza depășește
//Restul operațiilor sunt identice, doar că cu modulo 1999999973
while(n > 0) {
if(n % 2 == 1)
rasp = rasp * a % 1999999973;
a = a * a % 1999999973;
n /= 2;
}
return rasp;
}
int main()
{
fin >> a >> b;
fout << ridicare(a, b);
return 0;
}
Ridicare la putere in timp logaritmic: lgput (InfoArena)
Dându-se două numere naturale N
și P
, se cere să se calculeze restul
împărțirii lui NP
la 1999999973
. Pentru enunțul complet al problemei și
testarea soluțiilor vizitează această
pagină.
Exemplu: Pentru numerele N = 2
și P = 5
, soluția este 25 = 32
.
Rezolvare: Observăm că problema este identică cu cea de dinainte (inclusiv
operația modulo
). Astfel, doar numele fișierelor se schimbă:
//Rezolvarea problemei lgput de pe InfoArena
//Explicații: https://infoas.ro
//Enunț: https://www.infoarena.ro/problema/lgput
#include <fstream>
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
long long a, b;
long long ridicare(long long a, long long n) {
long long rasp = 1;
a = a % 1999999973; //În cazul în care baza depășește
//Restul operațiilor sunt identice, doar că cu modulo 1999999973
while(n > 0) {
if(n % 2 == 1)
rasp = rasp * a % 1999999973;
a = a * a % 1999999973;
n /= 2;
}
return rasp;
}
int main()
{
fin >> a >> b;
fout << ridicare(a, b);
return 0;
}
Probleme propuse
Setul de probleme 162 nu a fost găsit.
Alte resurse sau bibliografie
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Cuprinsul lecției
Cum putem ridica la putere într-un mod eficientCum funcționează exponențierea rapidăImplementare recursivă a exponențierii rapideImplementarea iterativă a exponențierii rapideProbleme rezolvate#2398 Moka (PbInfo)Ridicare la putere in timp logaritmic: lgput (InfoArena)Probleme propuseAlte resurse sau bibliografieCreează-ți un cont InfoAs și primești…
- Acces la sute de lecții de calitate, cu animații și exerciții
- Acces la peste 800 de probleme de informatică
- Indicații și rezolvări pentru fiecare problemă
- Totul 100% gratuit!
Comentarii 0