Invatare Atomica

Vectori si liste: tablouri unidimensionale

Declarare, indexare, parcurgere — Python list si C++ array

0%

Scopul lectiei

Intelegem ce este un tablou unidimensional (vector / lista), cum se declara si initializeaza, cum accesam elementele prin index si cum le parcurgem eficient. Invatam algoritmi de baza (suma, maxim) cu complexitate O(n) si — la nivel intensiv — echivalentul in C++.

La finalul lectiei vei stii sa:

Incearca inainte sa inveti!

Cum ai stoca 5 note de concurs intr-un singur program? O idee: note1, note2, ... note5. Dar daca sunt 100 de note? Vectorul rezolva asta elegant.

Intrebare rapida: Daca ai o lista cu 10 elemente si vrei sa accesezi ultimul element fara sa stii lungimea, ce index folosesti in Python?

Hint: Python permite indexuri negative...

01

Ce este un tablou unidimensional?

Definitie: Un tablou unidimensional (vector / lista) este o structura de date care stocheaza o secventa de valori de acelasi tip, accesibile printr-un index numeric.
Analogie sigura

Gandeste-te la un sir de cutii numerotate 0, 1, 2, ... n-1. Fiecare cutie contine o valoare. Cunosti numarul cutiei → accesezi direct valoarea.

In Python tipul corespunzator este list. Poate contine valori de tipuri diferite, dar in algoritmice folosim de regula liste omogene (toate numerele, sau toate string-urile).

In C++ echivalentul este tabloul static: int v[n] — fix n elemente, acelasi tip.

Avantaj cheie: In loc de 100 de variabile (nota1, nota2, ..., nota100) avem o singura lista cu 100 de elemente. Accesul la oricare element se face in O(1).
02

Declarare si indexare in Python

O lista se creeaza cu paranteze drepte. Indexarea incepe de la 0.

Index negativ: -1 = ultimul element, -2 = penultimul etc.

Exemplu Python — verificat
# Declarare si initializare
numere = [10, 20, 30, 40, 50]

print("Lista:", numere)
print("Lungime:", len(numere))
print("Primul element:", numere[0])
print("Ultimul element:", numere[-1])
print("Al treilea element (index 2):", numere[2])
Output (real):
Lista: [10, 20, 30, 40, 50]
Lungime: 5
Primul element: 10
Ultimul element: 50
Al treilea element (index 2): 30
Regula de aur: Indexul valid merge de la 0 la len(lista)-1 (sau de la -len(lista) la -1 pentru indexuri negative).
03

Parcurgerea unei liste

Doua stiluri principale de parcurgere:

  • for x in lista — parcurge valorile direct
  • for i, x in enumerate(lista) — parcurge perechi (index, valoare)
Exemplu Python — verificat
numere = [5, 12, 7, 3, 18]

print("--- Parcurgere cu for ---")
for x in numere:
    print(x)

print("--- Parcurgere cu index (enumerate) ---")
for i, x in enumerate(numere):
    print(f"numere[{i}] = {x}")
Output (real):
--- Parcurgere cu for ---
5
12
7
3
18
--- Parcurgere cu index (enumerate) ---
numere[0] = 5
numere[1] = 12
numere[2] = 7
numere[3] = 3
numere[4] = 18
04

Algoritmi de baza: suma si maximul — O(n)

Suma si maximul unui vector se calculeaza intr-un singur pass: complexitate O(n).

Initializam acumulatorul (suma=0, maxim=primul element), parcurgem si actualizam.

Exemplu Python — verificat
numere = [5, 12, 7, 3, 18]

# Suma — O(n)
suma = 0
for x in numere:
    suma += x
print("Suma elementelor:", suma)

# Maxim — O(n)
maxim = numere[0]
for x in numere:
    if x > maxim:
        maxim = x
print("Maximul:", maxim)
Output (real):
Suma elementelor: 45
Maximul: 18
Nota: Python ofera sum(lista) si max(lista) ca functii built-in — la fel O(n) intern. In algoritmica, scrierea explicita a buclei demonstreaza intelegerea algoritmului.
05

Lista goala, append() si list comprehension

Uneori construim lista dinamic, element cu element, folosind append().

List comprehension ofera o sintaxa compacta pentru liste calculate dintr-o formula.

Exemplu Python — verificat
# Construire dinamica cu append
patrate = []
for i in range(1, 6):
    patrate.append(i * i)
print("Patrate:", patrate)

# Echivalent cu list comprehension
patrate2 = [i * i for i in range(1, 6)]
print("Patrate (comprehension):", patrate2)
Output (real):
Patrate: [1, 4, 9, 16, 25]
Patrate (comprehension): [1, 4, 9, 16, 25]
append() are complexitate amortizata O(1) — adaugarea unui element la sfarsit este eficienta. Construirea intregii liste din n elemente: O(n).
06

Tablouri in C++ EXCLUSIV INTENSIV

Nivel intensiv — C++

In C++ un tablou static se declara cu dimensiunea fixa la compilare. Indexarea este identica cu Python: incepe de la 0.

Diferenta critica: C++ nu verifica automat marginile — accesul in afara tablou = comportament nedefinit.

Exemplu C++ — compilat si rulat cu g++ -std=c++17
#include <iostream>
using namespace std;

int main() {
    int v[5] = {10, 20, 30, 40, 50};
    int n = 5;

    cout << "Tablou: ";
    for (int i = 0; i < n; i++)
        cout << v[i] << " ";
    cout << endl;

    cout << "v[0] = " << v[0] << endl;
    cout << "v[4] = " << v[4] << endl;

    // Suma — O(n)
    int suma = 0;
    for (int i = 0; i < n; i++) suma += v[i];
    cout << "Suma: " << suma << endl;

    // Maxim — O(n)
    int maxim = v[0];
    for (int i = 1; i < n; i++)
        if (v[i] > maxim) maxim = v[i];
    cout << "Maxim: " << maxim << endl;

    return 0;
}
Output (real):
Tablou: 10 20 30 40 50
v[0] = 10
v[4] = 50
Suma: 150
Maxim: 50
Atentie: Accesul v[5] pe un tablou de dimensiune 5 este undefined behavior in C++. Spre deosebire de Python care arunca IndexError, C++ nu garanteaza nicio eroare vizibila — bug-ul poate ramane ascuns.

Exerseaza

Minim

Suma si lungime

Ai lista v = [3, 7, 2, 9, 5]. Scrie cod Python care afiseaza:

  • Lungimea listei
  • Suma elementelor (cu bucla explicita)
  • Primul si ultimul element
Hint: Lungime = len(v). Suma: initializeaza suma=0, parcurge cu for.
Vezi rezolvarea

Rezolvare pentru v = [3, 7, 2, 9, 5]:

  1. Lungimea: len(v) da 5.
  2. Suma cu bucla explicita: pornesti cu suma = 0, apoi for x in v: suma += x. Rezultat: 3+7+2+9+5 = 26.
  3. Primul element: v[0] = 3.
  4. Ultimul element: v[-1] = 5.

Cod complet: declari v = [3, 7, 2, 9, 5] si suma = 0, rulezi bucla for x in v: suma += x, apoi afisezi cu print() valorile len(v), suma, v[0] si v[-1].

Standard

Minim si pozitia sa

Scrie o functie Python gaseste_minim(v) care returneaza un tuplu (valoare, index) — valoarea minima si indexul primei sale aparitii.

Testeaza cu v = [8, 3, 5, 1, 6, 1]. Rezultat asteptat: (1, 3).

Hint: Porneste cu minim=v[0], idx=0. Foloseste enumerate() pentru a tine evidenta indexului.
Vezi rezolvarea

Rezolvare pentru gaseste_minim(v), testat cu v = [8, 3, 5, 1, 6, 1]:

  1. Initializezi minim = v[0] (adica 8) si idx = 0.
  2. Parcurgi cu for i, x in enumerate(v): ca sa ai perechea (index, valoare) la fiecare pas.
  3. Compari x < minim — STRICT mai mic, ca sa pastrezi indexul PRIMEI aparitii a minimului, nu al ultimei.
  4. Cand conditia e adevarata: actualizezi minim = x si idx = i.
  5. La final return (minim, idx).

Traseu pe date: minim scade la 3 (i=1), apoi la 1 (i=3). La i=5 apare tot 1, dar nu e strict mai mic decat minimul curent, deci idx ramane 3. Rezultat final: (1, 3) — coincide cu asteptarea din cerinta.

Performanta

Inversarea unui vector — fara slice

Scrie o functie Python inverseaza(v) care inverseaza in-place elementele listei primite, fara sa folosesti v[::-1] sau v.reverse(). Complexitate: O(n).

Testeaza cu v = [1, 2, 3, 4, 5]. Rezultat: [5, 4, 3, 2, 1].

Hint: Schimba elementele simetrice: v[i] cu v[n-1-i], pana la mijloc.
Vezi rezolvarea

Nu iti dau codul gata — doar schema si capcanele. Obiectiv: inversare in-place, O(n), fara v[::-1] sau v.reverse().

  1. Ideea de baza: foloseste doi indici care se apropie din capete: i pornind de la 0, j pornind de la len(v)-1. Opreste-te cand i ajunge la mijloc.
  2. La fiecare pas, schimba valorile de pe pozitiile i si j intre ele, apoi avanseaza i si retrage j.
  3. Capcana 1: daca parcurgi tot vectorul (nu te opresti la mijloc), inversezi de doua ori si ajungi inapoi la vectorul original.
  4. Capcana 2: functia trebuie sa MODIFICE lista primita ca parametru, nu sa construiasca si sa returneze o lista noua — altfel nu respecta cerinta de in-place.

Criterii de evaluare: (1) functioneaza corect si pentru n par si pentru n impar; (2) nu foloseste slicing sau .reverse(); (3) modifica lista originala, nu creeaza alta; (4) numarul de schimburi este jumatate din lungimea vectorului, nu lungimea intreaga — altfel complexitatea nu mai e optima.

Rezumat lectie

  • Un tablou unidimensional (vector/lista) stocheaza valori indexate de la 0
  • In Python: lista = [v1, v2, ...]; acces cu lista[i]; lungime cu len()
  • Index negativ: lista[-1] = ultimul element
  • Parcurgere cu for x in lista sau cu enumerate(lista) pentru perechi (index, val)
  • Suma si maximul in O(n): un singur pass, fara sortare
  • Lista goala + append(): constructie dinamica; list comprehension = sintaxa compacta
  • [INTENSIV] In C++: int v[n]; indexare de la 0; acces out-of-bounds = undefined behavior

Vrei mai mult?

Provocare: Ai vectorul v = [7, 2, 9, 4, 9, 1, 5] (retine, 9 apare de doua ori). Scrie un program Python care gaseste al doilea cel mai mare element DISTINCT (nu al doilea din lista, ci a doua valoare diferita ca marime) — aici raspunsul corect e 7, nu 9. Nu sorta lista; parcurge o singura data si tine doar doua variabile.

Intrebare de gandit: Codul cu list comprehension [i*i for i in range(1,6)] face exact aceleasi 5 inmultiri ca bucla cu append(), si totusi ruleaza mai repede in Python. De ce? Cauta ce se intampla "in spate" la fiecare apel append() fata de o comprehension.

Deschidere: O fotografie digitala este, la baza, un vector urias de numere — valorile pixelilor, unul dupa altul. Cand un filtru de pe telefon "lumineaza" o poza, de fapt parcurge acest vector si aduna o valoare la fiecare element, exact bucla de suma pe care ai scris-o azi, aplicata la milioane de elemente in loc de 5.

Urmatoarea lectie: Operatii pe vectori →