Programare Competitivă

Prelucrarea unui șir de numere (fără vectori)

Până acum, am lucrat de obicei cu unul sau două numere: am citit un număr, l-am descompus în cifre, i-am calculat divizorii etc.

Dar în multe probleme, primim mai multe numere și trebuie să le prelucrăm:

  • să aflăm cel mai mare sau cel mai mic;
  • să calculăm suma sau media lor;
  • să numărăm câte au o anumită proprietate;
  • să aflăm câte sunt pare, câte sunt prime etc.

Cum citim mai multe numere?

De obicei, pe prima linie primim un număr n care ne spune câte valori urmează.

Apoi, pe a doua linie, primim cele n numere.

Exemplu:

Input:
5
3 7 2 9 4

Aici avem n = 5 și numerele sunt: 3, 7, 2, 9, 4.

Ideea de bază

Citim numerele unul câte unul într-o buclă for și le prelucrăm imediat, fără a le stoca pe toate.

Nu avem nevoie de vectori. Folosim o singură variabilă x pe care o citim de n ori:

for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    // prelucrăm x aici
}

La fiecare pas, x primește o nouă valoare și o putem folosi cum dorim.

Suma a n numere

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int suma = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        suma = suma + x;
    }

    cout << suma;

    return 0;
}
Input:
4
10 20 30 40
Output:
100

Ce face programul?

Pas x citit suma
start - 0
1 10 0 + 10 = 10
2 20 10 + 20 = 30
3 30 30 + 30 = 60
4 40 60 + 40 = 100

Media aritmetică

Media aritmetică = suma tuturor numerelor împărțită la câte numere sunt.

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int suma = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        suma = suma + x;
    }

    cout << suma / n;

    return 0;
}
Input:
4
10 20 30 40
Output:
25

Atenție: dacă vrem media cu zecimale, trebuie să folosim double: cout << (double)suma / n;

Maximul unui șir de numere

Vrem să aflăm cea mai mare valoare din cele n numere.

Ideea

  • citim primul număr și presupunem că el este maximul;
  • pentru fiecare număr următor, verificăm dacă este mai mare decât maximul curent;
  • dacă da, actualizăm maximul.
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int x;
    cin >> x;
    int maxim = x;

    for (int i = 2; i <= n; i++) {
        cin >> x;
        if (x > maxim) {
            maxim = x;
        }
    }

    cout << maxim;

    return 0;
}
Input:
5
3 7 2 9 4
Output:
9

Pas cu pas

Pas x citit maxim
1 3 3
2 7 7 (7 > 3)
3 2 7 (2 < 7)
4 9 9 (9 > 7)
5 4 9 (4 < 9)

Minimul unui șir de numere

La fel ca maximul, dar folosim < în loc de >:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int x;
    cin >> x;
    int minim = x;

    for (int i = 2; i <= n; i++) {
        cin >> x;
        if (x < minim) {
            minim = x;
        }
    }

    cout << minim;

    return 0;
}
Input:
5
3 7 2 9 4
Output:
2

Numărarea valorilor cu o proprietate

Câte numere pare sunt?

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int cnt = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x % 2 == 0) {
            cnt++;
        }
    }

    cout << cnt;

    return 0;
}
Input:
6
3 8 2 7 4 1
Output:
3

Cele pare sunt: 8, 2, 4 → trei numere.

Câte numere sunt mai mari decât o valoare dată?

#include <iostream>
using namespace std;

int main()
{
    int n, prag;
    cin >> n >> prag;

    int cnt = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x > prag) {
            cnt++;
        }
    }

    cout << cnt;

    return 0;
}
Input:
5 5
3 7 2 9 4
Output:
2

Numerele mai mari decât 5 sunt: 7 și 9.

Maximul și poziția lui

Uneori vrem să știm nu doar care este maximul, ci și al câtelea număr este.

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int x;
    cin >> x;
    int maxim = x;
    int pozitie = 1;

    for (int i = 2; i <= n; i++) {
        cin >> x;
        if (x > maxim) {
            maxim = x;
            pozitie = i;
        }
    }

    cout << "Maximul este " << maxim << endl;
    cout << "Se afla pe pozitia " << pozitie;

    return 0;
}
Input:
5
3 7 2 9 4
Output:
Maximul este 9
Se afla pe pozitia 4

Combinarea mai multor prelucrări

Putem calcula mai multe lucruri în aceeași buclă:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int x;
    cin >> x;

    int suma = x;
    int maxim = x;
    int minim = x;
    int cnt_pare = 0;
    if (x % 2 == 0) cnt_pare++;

    for (int i = 2; i <= n; i++) {
        cin >> x;
        suma = suma + x;

        if (x > maxim) maxim = x;
        if (x < minim) minim = x;
        if (x % 2 == 0) cnt_pare++;
    }

    cout << "Suma: " << suma << endl;
    cout << "Maxim: " << maxim << endl;
    cout << "Minim: " << minim << endl;
    cout << "Numere pare: " << cnt_pare << endl;

    return 0;
}
Input:
5
3 7 2 9 4
Output:
Suma: 25
Maxim: 9
Minim: 2
Numere pare: 2

De reținut: nu avem nevoie de o buclă separată pentru fiecare calcul. Totul se poate face într-o singură parcurgere!

Citirea până la o valoare specială (fără n)

Uneori nu știm dinainte câte numere urmează. Primim numere până când apare o valoare specială (de exemplu 0):

#include <iostream>
using namespace std;

int main()
{
    int x;
    int suma = 0;
    int cnt = 0;

    cin >> x;

    while (x != 0) {
        suma = suma + x;
        cnt++;
        cin >> x;
    }

    cout << "Am citit " << cnt << " numere" << endl;
    cout << "Suma lor este " << suma;

    return 0;
}
Input:
3 7 2 9 0
Output:
Am citit 4 numere
Suma lor este 21

Cum funcționează?

  • citim un număr;
  • dacă nu este 0, îl prelucrăm și citim altul;
  • când întâlnim 0, ne oprim.
De ce citim x de două ori?

Prima citire (cin >> x de dinaintea buclei) este necesară pentru a avea o valoare pe care să o verificăm înainte de a intra în buclă.

Dacă primul număr este chiar 0, bucla nu se execută deloc - ceea ce este corect.

Citirea din interiorul buclei pregătește următoarea valoare pentru a fi verificată la condiția while.

Greșeli frecvente

1. Inițializarea greșită a maximului

int maxim = 0; // GREȘIT dacă numerele pot fi negative

Dacă toate numerele sunt negative, maximul ar rămâne 0, ceea ce e incorect.

Soluția corectă: inițializăm maximul cu primul număr citit.

2. Bucla pornește de la 1 în loc de 2 la maxim/minim

Dacă am citit deja primul număr înaintea buclei, bucla trebuie să pornească de la i = 2:

cin >> x;        // citim primul
int maxim = x;

for (int i = 2; i <= n; i++) { // de la al doilea
    cin >> x;
    ...
}

Dacă pornim de la 1, vom citi n + 1 numere în total.

3. Uitarea contorului la numărare

if (x % 2 == 0) {
    // lipsește cnt++;
}

Dacă verificăm o condiție dar nu incrementăm contorul, rezultatul va fi mereu 0.

4. Împărțire la zero la media aritmetică

Dacă n = 0, operația suma / n va da eroare. Trebuie verificat:

if (n > 0) {
    cout << suma / n;
}

Ce să reții

  • Putem prelucra un șir de numere fără vectori, citind fiecare valoare pe rând.
  • Folosim o variabilă x pe care o recitim la fiecare pas.
  • Suma, maximul, minimul, numărarea - toate se pot face într-o singură parcurgere.
  • Maximul și minimul se inițializează cu primul element, nu cu 0.
  • Bucla pornește de la 2 dacă am citit deja primul element separat.
  • Totul se bazează pe cunoștințele anterioare: for, while, if, cin.

Probleme

pbinfoN Maxim→

pbinfoN Minim→

pbinfoSummaxmin→

pbinfoProdusmaxime→

pbinfoPrimaciframinima→

Cuprins Inapoi Inainte