Aflarea sumei primelor N sume Gauss
În această lecție discutăm despre cum se rezolvă problema #3807 SumaGaussDeSumeGauss de pe PbInfo.ro.
Dându-se un număr natural n
, ne propunem să aflăm valoarea sumei:
1 +
1 + 2 +
1 + 2 + 3 +
… +
1 + 2 + 3 + … + n
Această rezolvare este inspirată după problema SumaGaussDeSumeGauss #3807 de pe PbInfo, cu cerința:
Cerința Se dau
n
numere naturale. Pentru fiecare numarx
, calculati1+(1+2)+(1+2+3)+(1+2+3+4)+...+(1+2+3+...x)
.
Algoritmul naiv
Un algoritm naiv calculează suma dintre sumele Gauss: 1 * 2 / 2
, 2 * 3 / 2
, 3 * 4 / 2
, …, n * (n + 1) / 2
. Algoritmul are complexitatea O(n)
,
deoarece trebuie să calculăm cele n sume Gauss și să le adunăm.
Explicarea algoritmului eficient
Ne întrebăm cum putem simplifica problema mai mult. Iată o rezolvare matematică, care se poate verifica prin inducție matematică:
Așadar, este îndeajuns să afișăm formula de mai sus.
Rezolvare în C++
#include <iostream>
using namespace std;
int sumaDeSume(int x) {
return x * (x + 1) * (x + 2) / 6;
}
int main()
{
int n;
cin >> n;
cout << sumaDeSume(n);
return 0;
}
Alte observații pentru rezolvarea problemei SumaGaussDeSumeGauss #3807
Formula prezentată anterior poate ieși din tipul de date long long
în timpul
înmulțirii. Așadar, luăm cei termeni de înmulțit (n
, n + 1
, n + 2
) și
verificăm care se împarte la 2
și care se împarte la 3
— fiind numere
consecutive, minim unul se va împărți la 2
și categoric unul se va împărți
la 3
. Împărțim unul dintre numere la 2
, și la 3
, iar la final, afișăm
produsul numerelor fără să mai împărțim la nimic, deoarece am împărțit mai
devreme la 2
și la 3
. Iată rezolvarea problemei:
#include <iostream>
using namespace std;
int n;
unsigned long long x, a, b, c;
int main()
{
cin >> n;
while(n--) {
cin >> x;
a = x;
b = x + 1;
c = x + 2;
if(a % 2 == 0) a /= 2;
else if(b % 2 == 0) b /= 2;
else if(c % 2 == 0) c /= 2;
if(a % 3 == 0) a /= 3;
else if(b % 3 == 0) b /= 3;
else if(c % 3 == 0) c /= 3;
cout << a * b * c << " ";
}
return 0;
}
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.
Comentarii 0