Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Aflarea sumei primelor N sume Gauss

În această lecție discutăm despre cum se rezolvă problema #3807 SumaGaussDeSumeGauss de pe PbInfo.ro.

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

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;
}

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Interschimbarea a două variabile în C++ (3 metode)Suma 1 + 2 + 3 + ... + N în C++Instrucțiunea do while (structuri repetitive)Al N-lea termen dintr-o progresie aritmeticăOperații cu numere mari în C++ - Toate funcțiile explicateVerifică dacă o literă este mică sau mare în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiAflă secolul unui an citit de la tastatură în C++Verifică dacă trei puncte sunt coliniare C++Verifică dacă un număr aparține șirului Fibonacci în C++Instrucțiunea break (structuri repetitive)Codul ASCII (tabel complet)Verificare număr prim în C++ (Clasa a IX-a)Pointer în C++. Variabile de tipul char * (char steluță)Cifra maximă și minimă a unui număr în C++Valoarea absolută (modulul) unui număr în C++Afișarea elementelor unui vector recursiv în C++Cel mai mic număr cu suma cifrelor N în C++Citirea și afișarea matricelor în C++Generarea șirului Fibonacci generalizat în C++Instrucțiunea de decizie în C++: if, else, switch, caseTipuri de date în C++: numere întregi, reale, caractere și alteleCombinatorică în C++: permutări, aranjamente, combinări și alteleCitește un șir de caractere cu spații în C++Divide et Impera (metodă de programare C++)Transformarea unei litere mici în literă mare în C++Al N-lea termen Fibonacci în C++Matrice pătratice în C++. Diagonala principală și secundarăAria unui triunghi folosind coordonatele acestora în C++Afișarea divizorilor primi ai unui număr în C++Numărul de divizori al unui număr în C++Vectorii în C++: declarare și parcurgereBordarea unei matrice în C++Comentarii în C++Vectorii în C++: citire și afișareTransformarea unei litere mari în literă mică în C++Cel mai semnificativ bit în C++Structuri repetitive (while, do while, for, etc)Complexitatea unui algoritm (timp și spațiu) în C++Rădăcina cubică a unui număr în C++ (cube root)Ce este o funcție void în C++?Al N-lea termen dintr-o progresie geometricăCifra de control a unui numărSortare crescătoare recursivă în C++ - Merge sort și Bubble sortOglinditul unui număr în C++Cel mai frecvent element dintr-un șir în C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Instrucțiunea while (structuri repetitive)Numărul de apariții al unui număr într-un vector în C++Cifra maximă a unui număr recursiv în C++Inversarea unui vector în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Aria și circumferința unui cerc în C++Suma numerelor naturale dintr-un interval dat în C++Indicatorul lui Euler în C++Cel mai puțin semnificativ bit în C++Inversarea unui șir de caractere în C++Maximul și minimul a trei valori în C++Numărul combinărilor în C++ (formula combinărilor)Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleTransformarea unui număr din baza 10 în baza 2 în C++Șiruri de caractere în C++. Tot ce trebuie să știiFuncții în C++. Ce sunt subprogrameleCum să calculezi instant 2 la puterea N în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Interclasarea a doi vectori în C++Algoritm recursiv pentru căutare binară (clasa a X-a)Ce înseamnă variabilă globală și locală în C++?Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicIndicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Numărul de cifre ale factorialului unui numărVerifică dacă un număr dat este o putere de 2 în C++CMMDC recursiv a două numere naturale în C++Verifică dacă o literă este vocală în C++Do while vs while în C++ - Care e diferența?Recursivitate în C++Numărul permutărilor în C++ (formula permutărilor)Ce este o variabilă unsigned în C++?Factorialul unui număr în C++Oglinditul recursiv al unui număr în C++Cea mai lungă secvență de elemente crescătoare în C++Maximul și minimul unui vector în C++Suma divizorilor unui număr în C++Ciurul lui Eratostene în C++Tipul struct în C++. Ce sunt structurile de date neomogeneNumărul aranjamentelor în C++ (formula aranjamentelor)Mediana unui șir de valori în C++Verificare dacă un număr este palindrom în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Ce înseamnă endl în C++?Vectori de frecvență (de apariții) în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Numărul de divizori primi ai unui număr în C++Copiuțe: Cifrele unui numărVerificarea unui an bisect în C++Calculul combinărilor de n luate câte k (nCk) în C++Instrucțiunea for (structuri repetitive)Verifică dacă un caracter este cifră în C++Căutare binară în C++Câte numere naturale sunt într-un interval dat? (C++)Transformarea unui număr din baza 2 în baza 10 în C++Cum să citești și să afișezi în fișiere în C++Verificare dacă șir de caractere este palindrom în C++Șirul lui Fibonacci în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Maximul și minimul a două valori în C++Maximul și minimul a n valori în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Verifică dacă un caracter este literă în C++Instrucțiunea continue (structuri repetitive)Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorSuma elementelor unui vector recursiv în C++Prima cifră a unui număr în C++Aflarea sumei primelor N sume GaussCel mai mare divizor comun (CMMDC) a două numere în C++Distanța dintre două puncte în C++Verifică dacă un număr este par sau impar fără modulo în C++Radicalul unui număr în C++ (rădăcina pătrată)Numere triunghiulare. Verificarea unui număr triunghiularNumărul minim de peroane pentru o gară în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăCum să afișezi partea întreagă a unui număr real în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont