Analiză și rezolvare completă pentru o problemă din varianta de bac la informatică din 2009

Dragilor pasionați de informatică și viitori absolvenți, bine v-am găsit! 🚀 Astăzi ne aventurăm într-o călătorie în timp, explorând un subiect fascinant și relevant chiar și în prezent: o problemă din varianta de Bacalaureat la Informatică din anul 2009. De ce să ne întoarcem tocmai în 2009? Simplu! Principiile fundamentale ale algoritmicii și programării rămân aceleași, indiferent de anul calendaristic. Înțelegerea profundă a acestor exerciții clasice ne oferă o bază solidă și ne ajută să abordăm cu încredere provocările actuale. Haideți să analizăm împreună cum se construiește o soluție robustă, eficientă și corectă! 💪

Contextul Bacalaureatului la Informatică în 2009: O Privire Retrospectivă

În 2009, examenul de Bacalaureat la Informatică punea accent pe logica algoritmică, pe capacitatea de a scrie cod eficient și pe înțelegerea structurilor de date de bază. Limbajele de programare predominante erau C++ și Pascal, iar problemele vizau adesea manipularea șirurilor de caractere, a vectorilor, a matricelor sau a numerelor, cu un accent deosebit pe eficiența temporală și spațială a algoritmilor. Nu exista atunci aceeași diversitate de limbaje ca acum (de exemplu, Python nu era la fel de popular în învățământul preuniversitar), dar esența provocărilor era similară: să gândești o rezolvare ingenioasă și să o transpui în cod. 🧠

Prezentarea Problemei Selectate din 2009 (Exemplu Tipic)

Pentru analiza noastră, am ales o problemă reprezentativă pentru nivelul și cerințele din 2009. Aceasta combină elemente de prelucrare a unui șir de date cu proprietăți aritmetice ale numerelor, o temă recurentă în examenul de Bacalaureat. Iată enunțul: 📝

Se dă un șir de N numere naturale. Să se afișeze, în ordine crescătoare, numerele prime distincte care apar în șir.

Exemplu: Dacă N = 7 și șirul este [10, 3, 7, 2, 5, 7, 12], rezultatul va fi 2 3 5 7.

Restricții: 1 <= N <= 100.000; Numerele din șir sunt naturale și mai mici sau egale cu 1.000.000.

Analiza Inițială a Cerințelor și Restricțiilor

Primul pas, crucial, este să descompunem problema în componente mai mici și să înțelegem pe deplin cerințele: 🔍

1. Citirea datelor: Un număr N și apoi N numere naturale.
2. Identificarea numerelor prime: Va trebui să avem o modalitate eficientă de a verifica dacă un număr este prim.
3. Numere distincte: Dacă un număr prim apare de mai multe ori în șir, trebuie să-l afișăm doar o singură dată.
4. Ordine crescătoare: Numerele prime identificate trebuie sortate și afișate de la cel mai mic la cel mai mare.

Restricțiile sunt la fel de importante. Faptul că N poate fi până la 100.000 și numerele până la 1.000.000 ne indică necesitatea unei soluții eficiente. O abordare naivă ar putea depăși limita de timp de execuție, tipică pentru Bac (de obicei 1-2 secunde).

Strategii de Abordare: De la Naiv la Optimizat

Abordarea Naivă: Simplu, dar Lent 🐌

Cea mai simplă idee ar fi să parcurgem șirul, iar pentru fiecare element să verificăm dacă este prim printr-o funcție dedicată. Dacă este prim și nu l-am mai văzut, îl adăugăm într-o listă. La final, sortăm și afișăm lista. Dar unde e problema?

Funcția clasică de verificare a primalității (is_prime(num)) testează divizibilitatea cu numere de la 2 până la sqrt(num). Pentru un număr de 1.000.000, sqrt(1.000.000) = 1.000. Asta înseamnă 1.000 de operații pentru fiecare verificare. Dacă avem N = 100.000 numere, complexitatea totală ar fi O(N * sqrt(MaxVal)). Adică 100.000 * 1.000 = 100.000.000 operații, plus sortarea! Mult prea lent pentru 2009. ⏰

Optimizarea Verificării Primalității: Ciurul lui Eratostene 🧠

Deoarece valoarea maximă a numerelor este 1.000.000, putem precalcula toate numerele prime până la această limită folosind Ciurul lui Eratostene. Acest algoritm marchează eficient toate numerele compuse, lăsând nemarcate doar pe cele prime. Complexitatea sa este de aproximativ O(MaxVal * log log MaxVal), ceea ce înseamnă aproximativ 1.000.000 * log log 1.000.000, adică mult mai rapid decât N * sqrt(MaxVal).

După ce rulăm ciurul, avem un vector boolean (să zicem este_prim[MaxVal+1]) care ne spune instantaneu dacă un număr este prim. Verificarea devine O(1)!

Gestionarea Elementelor Distincte și Sortarea

Pentru a ne asigura că afișăm numerele prime doar o singură dată, putem folosi un alt vector boolean (să zicem aparut_in_sir[MaxVal+1]). Când parcurgem șirul de intrare:

1. Verificăm dacă numărul curent, x, este prim (folosind este_prim[x]).
2. Dacă este prim, verificăm dacă l-am mai întâlnit deja (folosind aparut_in_sir[x]).
3. Dacă este prim și nu a fost marcat ca apărut deja, îl marcăm (aparut_in_sir[x] = true) și îl adăugăm într-o listă auxiliară de rezultate.

La final, lista auxiliară de rezultate va conține toate numerele prime distincte. Pentru a le afișa în ordine crescătoare, pur și simplu le parcurgem de la început până la sfârșit. Ah, dar atenție! Dacă le adăugăm într-un std::vector sau o listă, va trebui să sortăm acea listă la final. Complexitatea sortării este O(K log K), unde K este numărul de prime distincte (maxim N, dar de obicei mult mai mic). O altă abordare, și mai simplă pentru afișare, ar fi să parcurgem intervalul de la 2 la MaxVal și să afișăm fiecare număr i pentru care atât este_prim[i] cât și aparut_in_sir[i] sunt adevărate. Aceasta elimină nevoia unei sortări explicite, deoarece parcurgerea se face deja în ordine crescătoare! Aceasta este calea cea mai eficientă pentru afișare.

Implementarea Soluției Optime (în C++)

Vom folosi C++ pentru a ilustra codul, limbaj predominant la Bac în acea perioadă.

#include <iostream> // Pentru citire/scriere
#include <vector>   // Pentru vectori
#include <algorithm> // Pentru sortare (daca era nevoie)

// Constanta pentru valoarea maxima posibila a numerelor din sir
const int MAX_VAL = 1000000; 

// Vector boolean pentru a marca numerele prime (true = prim, false = compus)
bool este_prim[MAX_VAL + 1];

// Vector boolean pentru a marca numerele care apar in sir si sunt prime
bool aparut_in_sir[MAX_VAL + 1];

// Functie pentru Ciurul lui Eratostene
void ciur() {
    // Initial, presupunem ca toate numerele sunt prime
    for (int i = 0; i <= MAX_VAL; ++i) {
        este_prim[i] = true;
    }

    // 0 si 1 nu sunt prime
    este_prim[0] = este_prim[1] = false;

    // Parcurgem numerele incepand cu 2
    for (int p = 2; p * p <= MAX_VAL; ++p) { // Optimizare: pana la sqrt(MAX_VAL)
        // Daca p este prim, atunci toti multiplii sai (mai mari decat p) sunt compusi
        if (este_prim[p]) {
            for (int i = p * p; i > N; // Citim numarul de elemente din sir

    // Parcurgem numerele din sir
    for (int i = 0; i > numar_curent; // Citim fiecare numar

        // Daca numarul curent este prim si nu l-am marcat deja ca aparut
        if (este_prim[numar_curent] && !aparut_in_sir[numar_curent]) {
            aparut_in_sir[numar_curent] = true; // Il marcam ca aparut
        }
    }

    // Afisam numerele prime distincte in ordine crescatoare
    // Parcurgem de la 2 pana la MAX_VAL
    for (int i = 2; i <= MAX_VAL; ++i) {
        // Daca numarul i este prim si a aparut in sir
        if (este_prim[i] && aparut_in_sir[i]) {
            std::cout << i << " "; // Il afisam
        }
    }
    std::cout << std::endl; // Afisam o linie noua la final

    return 0;
}

Explicația Codului

1. ciur(): Această funcție rulează Ciurul lui Eratostene. Inițial, toate numerele sunt considerate prime. Apoi, se elimină 0 și 1. Se iterează de la 2 până la sqrt(MAX_VAL). Pentru fiecare număr p care este prim, toți multiplii săi (începând cu p*p) sunt marcați ca fiind compuși. Această precalculare este cheia performanței.
2. main():
   • std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);: Aceste linii sunt standard pentru optimizarea intrărilor/ieșirilor în C++, extrem de utile când se citește un volum mare de date (cum ar fi N=100.000 numere).
   • Se apelează ciur() pentru a popula vectorul este_prim.
   • Se citește N.
   • Se parcurge șirul de N numere. Pentru fiecare numar_curent, se verifică rapid dacă este prim (folosind este_prim[numar_curent]) și dacă a fost deja procesat ca distinct (folosind aparut_in_sir[numar_curent]). Dacă îndeplinește ambele condiții, se marchează în aparut_in_sir.
   • În final, pentru a afișa rezultatele în ordine crescătoare și distincte, se parcurge intervalul de la 2 la MAX_VAL. Dacă un număr i este prim (este_prim[i] este adevărat) ȘI a apărut în șir (aparut_in_sir[i] este adevărat), atunci este afișat. Această buclă garantează ordinea crescătoare fără o sortare suplimentară explicită.

Analiza Complexității Soluției

Această soluție este mult superioară variantei naive din punct de vedere al complexității:

• Complexitate Temporală:
  • Ciurul lui Eratostene: O(MAX_VAL * log log MAX_VAL).
  • Citirea și procesarea șirului: N operații de citire și N verificări O(1). Deci O(N).
  • Afișarea rezultatelor: O parcurgere de la 2 la MAX_VAL. Deci O(MAX_VAL).
  • Total: O(MAX_VAL * log log MAX_VAL + N + MAX_VAL). Deoarece MAX_VAL este de obicei mai mare sau comparabil cu N, complexitatea dominanta este O(MAX_VAL * log log MAX_VAL). Pentru MAX_VAL = 1.000.000, acest lucru este foarte rapid.
• Complexitate Spațială:
  • Doi vectori booleani de dimensiunea MAX_VAL + 1. Fiecare element ocupă 1 octet (sau mai puțin, dacă se folosește un std::vector specializat).
  • Total: O(MAX_VAL). Pentru 1.000.000, înseamnă aproximativ 2MB de memorie, ceea ce este perfect acceptabil pentru restricțiile de memorie ale Bacalaureatului (de obicei 256MB). 💾

Puncte Cheie și Sfaturi pentru Pregătirea la Bacalaureat 💡

1. Citește cu atenție: Nu subestima niciodată importanța înțelegerii complete a enunțului. Omițând o cerință (ex: „distincte”, „ordine crescătoare”) poți pierde puncte esențiale.
2. Identifică restricțiile: Acestea sunt indicii cruciale pentru alegerea algoritmului. Valori mari de N sau ale elementelor indică necesitatea optimizării.
3. Gândește abordări multiple: Începe cu o soluție simplă (naivă) și apoi gândește cum o poți îmbunătăți. Așa se ajunge la cea mai eficientă variantă.
4. Antrenează-te cu algoritmi clasici: Ciurul lui Eratostene, căutarea binară, sortările de bază, algoritmii pe grafuri (dacă e cazul) sunt fundamentale.
5. Eficiența I/O: Nu uita de std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); în C++ pentru problemele cu citiri/scrieri masive.
6. Testează riguros: Folosește exemple simple, cazuri limită (N=1, toate numerele sunt prime, niciun număr prim, numere identice etc.).

O Opinie Personală și Perspectiva Asupra Bacalaureatului

Observând evoluția Bacalaureatului la informatică de-a lungul anilor, pot afirma cu tărie că, deși instrumentele și tehnologiile avansează, fundamentele algoritmice rămân pilonii esențiali. Problemele din 2009, precum cea analizată, solicită exact acele tipuri de gândire logică și de optimizare care sunt valoroase și astăzi. Conform datelor de promovabilitate și performanță, elevii care stăpânesc bine algoritmi precum Ciurul sau tehnicile de programare dinamică obțin rezultate semnificativ mai bune. Capacitatea de a descompune o problemă complexă în sub-probleme gestionabile și de a alege cea mai eficientă metodă de rezolvare este o competență cheie, nu doar pentru examen, ci și pentru o carieră de succes în domeniul IT. Prin urmare, studiul problemelor vechi de Bac nu este o pierdere de timp, ci o investiție inteligentă în dezvoltarea abilităților tale de gândire computațională. 🎓

Concluzie

Am parcurs împreună o problemă tipică de Bacalaureat din 2009, de la înțelegerea cerințelor până la implementarea unei soluții optime. Am văzut cum o analiză detaliată și alegerea judicioasă a algoritmilor pot transforma o problemă aparent dificilă într-o provocare rezolvabilă cu eleganță și eficiență. Sper ca această incursiune să te ajute să înțelegi mai bine nu doar cum se rezolvă o problemă specifică, ci și *felul de a gândi* necesar pentru a excela la informatică. Continuă să exersezi, să fii curios și să îți pui întrebări! Succes la viitoarele examene și în toate proiectele tale! 🎉