Secvența maximă de valori egale la BAC: fișier și C++

Cea mai lungă secvență de valori egale consecutive se găsește într-o singură parcurgere, păstrând lungimea secvenței curente și cea mai bună lungime întâlnită. Când valoarea se schimbă, începe o secvență nouă. Nu trebuie să numeri toate aparițiile unei valori din fișier, deoarece cerința privește elemente vecine.

Vom calcula și poziția de început a primei secvențe de lungime maximă. Fișierul conține mai întâi numărul elementelor, apoi valorile întregi. Acest format este precizat pentru exemplul nostru; citește întotdeauna formatul concret din subiectul de BAC pe care îl rezolvi.

Secvență consecutivă sau apariții în întregul șir

În șirul doi, doi, cinci, doi, doi, doi, șapte, valoarea doi apare de cinci ori. Cea mai lungă secvență de valori doi consecutive are însă lungimea trei și începe la poziția a patra, dacă numerotăm de la unu.

Un vector de frecvență ar număra toate cele cinci apariții, pierzând informația despre ordine. Pentru problema noastră, trebuie să observăm dacă valoarea curentă continuă grupul imediat anterior. Relația cu vecinul este suficientă pentru această decizie.

O secvență de valori egale nu trebuie să conțină cel puțin două elemente. Dacă toate valorile vecine diferă, fiecare secvență maximală are lungimea unu. Acest caz stabilește inițializarea corectă pentru un șir nevid.

Variabilele necesare

Păstrăm valoarea precedentă, lungimea grupului curent, cea mai mare lungime și poziția de început a celei mai bune secvențe. Indicele de parcurgere arată poziția elementului nou, în convenția de la zero.

La citirea primei valori, lungimea curentă și cea mai bună lungime sunt unu. Cea mai bună secvență începe la indicele zero. Apoi prelucrăm elementele rămase, comparându-le cu valoarea precedentă.

Dacă noua valoare este egală cu precedenta, mărim lungimea curentă. Altfel, o resetăm la unu, fiindcă elementul curent începe singur o secvență nouă. Resetarea la zero ar uita să numere chiar elementul care a declanșat schimbarea.

Exemplu urmărit pe tabel

Folosim șirul patru, patru, unu, unu, unu, șase, șase. Cea mai lungă secvență are trei elemente egale cu unu.

Poziție de la unu	Valoare	Lungime curentă	Cea mai bună lungime
1	4	1	1
2	4	2	2
3	1	1	2
4	1	2	2
5	1	3	3
6	6	1	3
7	6	2	3

Când ajungem la poziția a cincea și lungimea curentă este trei, începutul secvenței este poziția cinci minus trei plus unu, adică trei. Aceeași relație funcționează și cu indici de la zero, dacă păstrezi consecvent convenția.

Program C++ cu citire din fișier

Fișierul bac.in conține un număr de elemente între unu și un milion, apoi exact atâtea valori întregi de cel mult un miliard în valoare absolută. Programul afișează lungimea maximă și poziția de început numerotată de la unu. Presupunem că fișierul există și respectă formatul.

#include <fstream>
#include <iostream>
using namespace std;

int main() {
    ifstream fin("bac.in");
    int n, precedent, x;
    fin >> n >> precedent;
    int curenta = 1, maxima = 1, inceput = 0;
    for (int i = 1; i < n; ++i) {
        fin >> x;
        if (x == precedent) ++curenta;
        else curenta = 1;
        if (curenta > maxima) {
            maxima = curenta;
            inceput = i - curenta + 1;
        }
        precedent = x;
    }
    cout << maxima << ' ' << inceput + 1;
    return 0;
}

Valoarea precedentă se actualizează după comparație. Dacă ai pune valoarea curentă în ea înainte de test, ai compara fiecare număr cu el însuși și ai extinde greșit secvența la fiecare pas.

Programul nu memorează vectorul. Citirea succesivă este suficientă deoarece decizia de continuare folosește doar ultima valoare, iar rezultatul global este rezumat prin câteva variabile.

Prima secvență maximă sau ultima

Actualizarea rezultatului folosește o comparație strictă. Dacă o secvență ulterioară ajunge la aceeași lungime maximă, poziția memorată nu se schimbă. Astfel, păstrăm prima secvență care atinge lungimea maximă finală.

Pentru șirul doi, doi, cinci, cinci, avem două secvențe de lungime doi. Programul afișează începutul primei, poziția unu. Dacă enunțul ar cere ultima secvență maximă, actualizarea ar trebui să permită și egalitatea.

Nu schimba comparația fără să verifici cerința de departajare. Ambele variante pot calcula aceeași lungime, dar poziții diferite. Un test care verifică doar lungimea nu descoperă această diferență.

De ce ultima secvență nu este pierdută

În varianta noastră, comparăm lungimea curentă cu maximul după fiecare element. Prin urmare, o secvență care ajunge până la finalul fișierului este evaluată la fiecare extindere, inclusiv la ultimul element.

Există și soluții care actualizează maximul doar când valoarea se schimbă. Acestea trebuie să evalueze separat ultima secvență după terminarea citirii, fiindcă nu mai apare o valoare diferită care să o închidă.

Ambele idei pot fi corecte, dar nu amesteca etapele lor. Dacă ai ales actualizarea la schimbare și ai uitat verificarea finală, un șir cu toate elementele egale poate produce un rezultat greșit, deși toate comparațiile dintre vecini sunt corecte.

Justificarea și eficiența

După prelucrarea unui element, lungimea curentă reprezintă numărul valorilor egale consecutive care se termină exact în acel element. Egalitatea cu precedentul extinde grupul, iar diferența începe un grup de lungime unu. Aceasta justifică actualizarea locală.

Maximul reprezintă cea mai mare lungime dintre toate secvențele evaluate până atunci. Compararea după fiecare pas păstrează această proprietate. La final, au fost evaluate toate pozițiile de sfârșit posibile, deci rezultatul este global.

Timpul este liniar în numărul elementelor, iar memoria suplimentară este constantă. Faptul că fișierul conține multe valori nu obligă programul să le păstreze simultan. Înainte de a alege un tablou, explică informația necesară pentru pasul următor, folosind principiul de învățare prin înțelegere.

Adaptări apropiate, dar diferite

Pentru cea mai lungă secvență strict crescătoare de elemente consecutive, condiția de extindere compară valoarea curentă cu precedenta printr-o inegalitate strictă. Pentru o secvență de valori pare, proprietatea privește valoarea curentă, iar resetarea poate avea alt sens când apare un element neacceptat.

Nu confunda o secvență consecutivă cu un subșir obținut prin alegerea unor elemente nevecine. Algoritmul de aici urmărește grupuri continue. O cerință despre elemente care pot fi sărite poate necesita altă metodă.

De asemenea, numărarea grupurilor este diferită de găsirea celui mai lung. Pentru numărul grupurilor, pornești de la unu într-un șir nevid și mărești contorul la fiecare schimbare de valoare. Acumulatorul reprezintă altceva decât lungimea curentă.

Exerciții cu răspunsuri

Pentru opt, opt, opt, opt, lungimea maximă este patru și începutul este poziția unu. Acest caz verifică evaluarea secvenței care ajunge la final.

Pentru unu, doi, trei, lungimea maximă este unu. Dacă se cere prima secvență, începutul este poziția unu. Nicio comparație dintre vecini nu extinde grupul.

Pentru trei, trei, cinci, șapte, șapte, șapte, maximul este trei și începutul este poziția a patra. Prima secvență, de lungime doi, trebuie înlocuită în rezultat.

Pentru un singur element minus șase, răspunsul este lungime unu și început unu. Valoarea negativă nu schimbă regula egalității.

Întrebări frecvente

Am nevoie de întregul vector pentru poziția de început?

Nu. Poziția curentă și lungimea secvenței determină începutul. Trebuie doar să păstrezi convenția de numerotare.

Ce se schimbă dacă fișierul nu oferă numărul elementelor?

Citirea trebuie controlată de succesul extragerii fiecărei valori. Primul element se tratează separat, iar cazul unui fișier gol trebuie definit prin cerință. Nu folosi neschimbat programul pentru alt format.

Cum verific o soluție proprie?

Testează toate valorile egale, valori toate diferite, două maxime egale și maximul aflat la final. Poți urmări aceste cazuri împreună cu un profesor de informatică.