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 numar x, calculati 1+(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ă:

https://i.ibb.co/7tHHQ9w/image.png

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

Autentifică-te pentru a putea comenta.

Autentifică-te