De ce contează?
Prognoza meteo folosește media temperaturilor din ultimele 7 zile. Nu ține minte toată istoria — când vine ziua 8, uită ziua 1. Un buffer circular de 7 poziții face exact asta: ține mereu ultimele 7 valori, suprascriind cele mai vechi.
Ideea de buffer circular
Folosim un array de dimensiune p. La pasul i, scriem în poziția i % p — când ajungem la capăt, continuăm de la 0, suprascriind cele mai vechi valori.
| buf | 1 | 9 | 4 |
| index | 0 | 1 | 2 |
nou |
p = 3, sir: 5 2 8 1 9 4
i=0: buf[0]=5 → [5, -, -]
i=1: buf[1]=2 → [5, 2, -]
i=2: buf[2]=8 → [5, 2, 8] <- plin
i=3: buf[0]=1 → [1, 2, 8] (suprascrie cel mai vechi: 5)
i=4: buf[1]=9 → [1, 9, 8] (suprascrie 2)
i=5: buf[2]=4 → [1, 9, 4] (suprascrie 8)Implementare C++ — buffer circular
#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream fin("buf.in");
ofstream fout("buf.out");
int n, p;
fin >> n >> p;
int buf[1000]; // buffer de dimensiune p
long long suma = 0;
for (int i = 0; i < n; i++) {
int x;
fin >> x;
if (i >= p) {
suma -= buf[i % p]; // scoate cel mai vechi element
}
buf[i % p] = x; // pune noul element
suma += x;
if (i >= p - 1) {
// avem p elemente in buffer — putem raporta
fout << "Suma ultimelor " << p << ": " << suma << "\n";
}
}
return 0;
}Exemplu: n=6, p=3, șir 5 2 8 1 9 4 → suma la i=2: 15, i=3: 11, i=4: 18, i=5: 14
Trucul cheie: la pasul i, elementul care iese din fereastră este chiar buf[i % p] — exact slotul pe care urmează să-l suprascrii. Îl citești (și scazi din sumă) înainte de suprascriere, altfel valoarea veche e pierdută.
Varianta simplă (fără suma curentă)
Dacă vrei doar să afișezi ultimele p elemente la final, nu mai ai nevoie de suma glisantă — citești tot șirul în buffer și la sfârșit parcurgi circular:
for (int i = 0; i < n; i++) {
fin >> buf[i % p];
}
// start = primul element valid in ordinea circulara
int start = n % p;
for (int i = 0; i < p; i++) {
fout << buf[(start + i) % p] << " ";
}Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Buffer circular | O(n) | O(p) |
Greșeala 1: Citești buf[i % p] (cel care iese) după suprascriere. Îl suprascrii înainte să-l scazi din sumă — valoarea veche e pierdută. Ordinea: scade buf[i % p], suprascrie, adaugă.
Greșeala 2: Raportezi suma înainte ca buffer-ul să fie plin (i < p - 1). Suma primelor i+1 < p elemente nu e suma ultimelor p.
Greșeala 3: Declari buf[p] unde p e citit la runtime — în C++ clasic, dimensiunea array-ului static trebuie să fie o constantă la compilare. Folosește o constantă mare (int buf[1000]) sau un vector<int> buf(p).