Lecții de informatică pentru bacalaureat
42 de lecții din programa de bacalaureat, grupate în 9 capitole. Le poți citi fără cont.
Primii pași în programare
De la „ce înseamnă un algoritm" până la primul program C++ care citește date și afișează un rezultat. Dacă abia începi, pornește de aici.
- Ce este un algoritm — Ce face ca o listă de pași să fie un algoritm și de ce contează diferența la examen.
- Pseudocodul, citit și scris — Notația în care sunt date subiectele I și II: cele trei structuri și cum urmărești pe hârtie ce afișează un algoritm.
- Primul program C++ — Structura unui program, ce face fiecare linie din scheletul obligatoriu și erorile pe care le vei vedea în prima…
- Tipuri de date și variabile — Ce încape într-un int, când ai nevoie de long long și de ce împărțirea a două numere întregi dă un întreg.
- Citirea datelor și afișarea rezultatelor — cin, cout, fișiere text și tiparele de citire care apar în aproape orice problemă.
- Operatori și expresii — Operatori aritmetici, de comparație și logici, ordinea în care se evaluează și capcanele care schimbă rezultatul fără…
Structuri de control
Deciziile și buclele. Datorită lor, programul nu execută mereu aceleași instrucțiuni, în aceeași ordine.
- Decizia: if și else — Cum alegi între două drumuri, cum înlănțui mai multe cazuri și de ce acoladele lipsă strică programe care par corecte.
- Instrucțiunea switch — Când o listă de valori fixe se scrie mai bine decât un lanț de if și de ce un break lipsă nu este întotdeauna o…
- while și do-while — Buclele pentru când nu știi de câte ori: condiția de oprire, capcana buclei infinite și diferența dintre testul…
- Instrucțiunea for — Bucla pentru când știi de câte ori: cele trei părți ale antetului, pasul și greșelile de margine care schimbă…
- break, continue și ieșirea din bucle — Cum ieși dintr-o buclă mai devreme, ce face break într-o buclă imbricată și când e mai bine să nu le folosești deloc.
Lucrul cu numere
Cifre, divizori, numere prime și șiruri recurente. Pe aceste tehnici se sprijină jumătate din subiectele de la examen. Toate pornesc de la aceleași două operații: împărțirea întreagă și restul.
- Prelucrarea cifrelor unui număr — Cum descompui un număr în cifre, cum îl reconstruiești și tiparele care apar în aproape orice subiect de la II și III.
- Divizibilitate și divizori — Testul de divizibilitate, cum găsești toți divizorii în √n pași și de ce jumătate din problemele de la examen se reduc…
- Numere prime — Testul de primalitate corect, cazurile limită care se uită mereu și cum îl folosești în probleme mai mari.
- Descompunerea în factori primi — Algoritmul care scoate factorii primi și exponenții lor, de ce merge fără test de primalitate și ce faci cu restul…
- Cel mai mare divizor comun — Algoritmul lui Euclid prin scăderi și prin restul împărțirii, cmmmc-ul care se deduce din el și fracțiile ireductibile.
- Șiruri definite prin recurență — Fibonacci și rudele lui: cum calculezi termenul n fără vector, de ce contează ordinea atribuirilor și unde depășește…
Tablouri
Vectori și matrice: cum reții multe valori deodată, cum le parcurgi, cum cauți și cum sortezi. De aici încolo, aproape orice problemă de la Subiectul III are un tablou în ea.
- Tablouri unidimensionale — Declararea unui vector, indicii, citirea și afișarea, plus cele două greșeli care depășesc limitele fără să dea eroare.
- Prelucrări pe vectori — Minim, maxim, sume, frecvențe, ștergere și inserare, adică tiparele scurte din care se compun problemele mari.
- Căutarea într-un vector — Căutarea secvențială, căutarea binară pe vector sortat și de ce a doua schimbă ordinul de mărime al problemei.
- Metode elementare de sortare — Sortarea prin selecție, prin interschimbare și prin inserție, plus sortarea prin numărare. Cum funcționează și când o…
- Tablouri bidimensionale — Declararea unei matrice, cei doi indici, citirea pe linii și parcurgerile de bază.
- Transformări pe matrice — Interschimbări de linii și coloane, transpusa, rotații și parcurgerea în spirală, adică problemele de geometrie a…
Subprograme și recursivitate
Cum împarți un program în bucăți cu nume, cum circulă datele între ele și ce se întâmplă când o funcție se apelează pe sine. Subiectul III cere aproape întotdeauna un subprogram.
- Subprograme: definire și apel — Antetul, corpul, valoarea returnată și cum citești o cerință de tip „scrieți subprogramul" din enunțul de bac.
- Transmiterea parametrilor — Prin valoare și prin referință: care face copie și care nu, cum returnezi mai multe rezultate, și cum se transmit…
- Recursivitate — Ce se întâmplă când o funcție se apelează pe sine, cum arată condiția de oprire și cum urmărești pe hârtie un apel…
- Recursivitate pe tablouri — Aceleași parcurgeri, scrise recursiv: cum alegi parametrul care se micșorează și cum returnezi un rezultat construit…
Șiruri de caractere
Texte păstrate în tablouri de caractere, așa cum se cere la examen. Fără tipul string, pentru că programa de bac nu îl conține, iar o soluție care îl folosește nu primește punctaj.
- Tipul char — Un caracter este un număr. De aici vin toate trucurile: conversia cifrelor, schimbarea literelor mari în mici și…
- Șiruri de caractere — Tabloul de caractere, terminatorul nul, citirea unei linii întregi și de ce nu folosim tipul string la bac.
- Funcțiile din cstring — strlen, strcpy, strcat, strcmp, strchr și strstr: ce face fiecare, ce capcane are și cum se combină.
- Prelucrarea cuvintelor dintr-un text — Cum împarți un text în cuvinte, cu strtok și fără, cum le numeri, le compari și refaci textul din ele.
Structuri și fișiere
Cum ții la un loc date de tipuri diferite despre același lucru și cum citești și scrii în fișiere text. De obicei, ultima problemă de la Subiectul III îți dă datele într-un fișier.
- Tipul struct — Cum grupezi mai multe câmpuri sub un singur nume, cum lucrezi cu vectori de structuri și cum sortezi după un câmp.
- Fișiere text — ifstream și ofstream, citirea până la sfârșitul fișierului și greșelile care costă puncte deși programul e corect.
Metode de programare
Backtracking și metoda greedy sunt două scheme generale care rezolvă familii întregi de probleme. Prima încearcă sistematic totul. A doua alege pe loc și nu se mai întoarce.
- Backtracking — Schema generală, ce înseamnă fiecare parte din ea, și cum o adaptezi de la o problemă la alta.
- Aplicații ale backtracking-ului — Aranjamente, combinări, submulțimi, produs cartezian și problema damelor, toate cu aceeași schemă și alt valid.
- Metoda greedy — Alegerea local optimă, de ce funcționează uneori și eșuează alteori, și cum recunoști o problemă potrivită.
Grafuri și arbori
Noțiuni, reprezentări și parcurgeri. Un graf arată pur și simplu „cine e legat cu cine". Cele mai multe cerințe de la examen se reduc la a număra sau a parcurge.
- Grafuri neorientate: noțiuni — Vârfuri, muchii, grade, lanțuri și cicluri: vocabularul fără de care nu poți citi enunțurile.
- Reprezentarea grafurilor — Matricea de adiacență, listele de vecini și lista de muchii: ce afli ușor din fiecare și câtă memorie cer.
- Parcurgerea grafurilor — Parcurgerea în adâncime și în lățime: cum funcționează, ce ordine dau și la ce folosești fiecare.
- Componente conexe — Cum numeri bucățile unui graf, cum le etichetezi, și problemele care se reduc la asta fără să spună „graf".
- Grafuri orientate — Ce se schimbă când muchiile au sens: grade interioare și exterioare, drumuri, și de ce matricea nu mai este simetrică.
- Arbori — Grafurile fără cicluri: proprietățile care se cer la teorie, arborele cu rădăcină și vectorul de tați.