Prelucrări cu ultimele p elemente

Am învățat deja să prelucrăm un șir de numere „din mers” - fără a le stoca pe toate. Am calculat suma, maximul, minimul, am numărat valori.

Dar unele probleme cer să comparăm fiecare element cu elementul anterior (sau cu ultimele 2-3 elemente). Pentru asta trebuie să reținem ultimele valori citite.

De ce avem nevoie de elementele anterioare?

Exemple de probleme:

• câte perechi de numere consecutive sunt egale?
• câte numere sunt mai mari decât predecesorul lor?
• care este cea mai lungă secvență crescătoare consecutivă?
• primele două maxime din șir

Stocarea ultimului element

Problema: câte numere sunt mai mari decât predecesorul lor?

Avem nevoie să comparăm fiecare număr cu cel de dinainte.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

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

    int ant; // elementul anterior
    fin >> ant;

    int cnt = 0;

    for (int i = 2; i <= n; i++) {
        int x;
        fin >> x;
        if (x > ant) {
            cnt++;
        }
        ant = x; // actualizăm anteriorul
    }

    fout << cnt;

    return 0;
}

date.in:

7
3 5 2 8 8 1 4

date.out:

3

Pas cu pas

Ideea cheie

La fiecare pas, după ce prelucrăm x, facem ant = x. Astfel, la pasul următor, ant conține valoarea precedentă.

Cea mai lungă secvență crescătoare consecutivă

Vrem lungimea celei mai lungi porțiuni din șir în care fiecare element este strict mai mare decât cel de dinainte.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

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

    int ant;
    fin >> ant;

    int lung = 1;    // lungimea secvenței curente
    int maxLung = 1; // cea mai mare lungime găsită

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

        if (x > ant) {
            lung++;
        } else {
            lung = 1; // resetăm
        }

        if (lung > maxLung) {
            maxLung = lung;
        }

        ant = x;
    }

    fout << maxLung;

    return 0;
}

date.in:

10
3 5 7 2 4 6 8 9 1 3

date.out:

5

Explicație

Secvențele crescătoare sunt: 3,5,7 (lung 3), 2,4,6,8,9 (lung 5), 1,3 (lung 2).

Cea mai lungă are lungimea 5.

Numărarea perechilor de elemente consecutive egale

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

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

    int ant;
    fin >> ant;

    int cnt = 0;

    for (int i = 2; i <= n; i++) {
        int x;
        fin >> x;
        if (x == ant) {
            cnt++;
        }
        ant = x;
    }

    fout << cnt;

    return 0;
}

date.in:

8
3 3 5 5 5 2 2 1

date.out:

4

Perechile egale consecutive: (3,3), (5,5), (5,5), (2,2) → 4 perechi.

Stocarea ultimelor 2 elemente: primele două maxime

Vrem să aflăm cele mai mari două valori distincte din șir.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

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

    int x;
    fin >> x;
    int max1 = x; // cel mai mare
    int max2;      // al doilea cel mai mare

    fin >> x;
    if (x > max1) {
        max2 = max1;
        max1 = x;
    } else {
        max2 = x;
    }

    for (int i = 3; i <= n; i++) {
        fin >> x;
        if (x > max1) {
            max2 = max1;
            max1 = x;
        } else if (x > max2) {
            max2 = x;
        }
    }

    fout << max1 << " " << max2;

    return 0;
}

date.in:

6
3 7 2 9 4 8

date.out:

9 8

Pas cu pas

Cum funcționează?

• Dacă x > max1: noul maxim este x, iar fostul maxim devine al doilea (max2 = max1).
• Dacă x > max2 dar nu mai mare ca max1: actualizăm doar max2.
• Altfel: nu schimbăm nimic.

Primele două minime

Exact aceeași logică, dar cu < în loc de >:

if (x < min1) {
    min2 = min1;
    min1 = x;
} else if (x < min2) {
    min2 = x;
}

Stocarea ultimelor 3 elemente

Unele probleme cer să verificăm relația între trei elemente consecutive.

Problema: câte „vârfuri” are șirul?

Un element b este vârf dacă este strict mai mare decât vecinii săi: a < b > c.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

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

    int a, b;
    fin >> a >> b;

    int cnt = 0;

    for (int i = 3; i <= n; i++) {
        int c;
        fin >> c;

        if (b > a && b > c) {
            cnt++;
        }

        a = b;
        b = c;
    }

    fout << cnt;

    return 0;
}

date.in:

8
1 5 3 7 2 6 4 8

date.out:

3

Pas cu pas

Deplasarea la 3 variabile

La fiecare pas: - a = b (cel mai vechi se actualizează) - b = c (elementul din mijloc devine cel nou) - Citim un nou c la pasul următor

Schema generală

Greșeli frecvente

1. Uitarea actualizării variabilei anterioare

if (x > ant) {
    cnt++;
}
// lipsește: ant = x;

Fără ant = x, comparăm mereu cu primul element.

2. Ordinea greșită la primele două maxime

// GREȘIT:
max1 = x;
max2 = max1; // max2 primește noua valoare, nu vechea!

// CORECT:
max2 = max1; // salvăm mai întâi
max1 = x;    // apoi schimbăm

3. Bucla pornește greșit

Dacă citim primele k elemente separat, bucla trebuie să pornească de la k + 1:

• 1 element citit → for (int i = 2; ...)
• 2 elemente citite → for (int i = 3; ...)

4. Nu tratăm cazul n = 1 sau n = 2

Dacă avem mai puțin de 3 elemente, nu putem verifica vârfuri/văi. Programul trebuie să funcționeze corect și pentru n mic.

Ce să reții

• Putem rezolva multe probleme stocând doar ultimele câteva elemente.
• Cu 1 variabilă (ant): comparații consecutive, secvențe.
• Cu 2 variabile (max1, max2): primele două maxime/minime.
• Cu 3 variabile (a, b, c): vârfuri, văi, relații între trei consecutivi.
• La fiecare pas deplasăm variabilele: cel mai vechi primește valoarea celui din mijloc, cel din mijloc primește pe cel nou.
• Atenție la ordinea actualizărilor - salvăm mai întâi valorile vechi.