Invatare Atomica

Operatii pe vectori

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei invata sa aplici cele mai importante operatii pe vectori: calculul sumei, gasirea minimului si maximului, cautarea unui element si modificarea structurii prin inserare si stergere.

Dupa aceasta lectie vei putea:

  • Sa calculezi suma elementelor unui vector si sa explici complexitatea O(n)
  • Sa gasesti minimul si maximul unui vector, retinand si pozitia lor
  • Sa implementezi cautarea secventiala si sa analizezi corect cazul cel mai defavorabil
  • Sa inserezi un element intr-un vector la o pozitie data, mutand elementele la dreapta
  • Sa stergi un element dintr-un vector, compactand spatiul ramas
  • Sa scrii aceleasi algoritmi in C++ cu tablouri unidimensionale (nivel intensiv)

Incearca singur!

Provocare:

Ai vectorul v = [3, 7, 2, 9, 5, 1, 8]. Fara calculator, raspunde: care este suma elementelor? Care este cel mai mic element si la ce pozitie se afla?

💡 Ai nevoie de un indiciu?

Aduna elementele unul cate unul: 3+7=10, 10+2=12, 12+9=21, 21+5=26, 26+1=27, 27+8=35.

Pentru minim, porneste cu v[0]=3 si compara cu fiecare urmator. Valoarea 1 de la pozitia 5 este mai mica decat toate. Maximul este 9 la pozitia 3.

1

1. Suma elementelor unui vector

Calculul sumei parcurge vectorul o singura data, acumuland fiecare element intr-o variabila suma initiata cu 0. Complexitate: O(n).
Idee (pseudocod):

suma ← 0
PENTRU i de la 0 la n-1 EXECUTA
    suma ← suma + v[i]
SCRIE suma

# Suma elementelor unui vector
v = [3, 7, 2, 9, 5, 1, 8]
n = len(v)

suma = 0
for i in range(n):
    suma += v[i]

print("Vectorul:", v)
print("Suma elementelor:", suma)
Output real (rulat cu python):
Vectorul: [3, 7, 2, 9, 5, 1, 8]
Suma elementelor: 35

Variabila suma este initiata la 0 inainte de bucla. Daca ar fi initiata cu alta valoare, rezultatul ar fi incorect — greseala frecventa la examen.

2

2. Minimul si maximul unui vector

Initializam minim si maxim cu primul element, apoi comparam fiecare element urmator. Retinem si pozitia pentru a indica unde se afla valoarea extrema. Complexitate: O(n). 
# Gasirea minimului si maximului dintr-un vector
v = [3, 7, 2, 9, 5, 1, 8]
n = len(v)

minim = v[0]
maxim = v[0]
poz_min = 0
poz_max = 0

for i in range(1, n):
    if v[i] < minim:
        minim = v[i]
        poz_min = i
    if v[i] > maxim:
        maxim = v[i]
        poz_max = i

print("Vectorul:", v)
print("Minim:", minim, "la pozitia", poz_min)
print("Maxim:", maxim, "la pozitia", poz_max)
Output real (rulat cu python):
Vectorul: [3, 7, 2, 9, 5, 1, 8]
Minim: 1 la pozitia 5
Maxim: 9 la pozitia 3
Trasarea pasilor (primele 4 iteratii):
iv[i]minimpoz_minmaximpoz_max
init—3030
173071
222271
392293
452293
3

3. Cautarea secventiala

Cautarea secventiala (liniara) verifica elementele unul cate unul, de la stanga la dreapta, pana gaseste valoarea dorita sau epuizeaza vectorul. Complexitate in cazul cel mai defavorabil: O(n). 
# Cautare secventiala intr-un vector
v = [3, 7, 2, 9, 5, 1, 8]
n = len(v)
target = 9

gasit = False
poz = -1
for i in range(n):
    if v[i] == target:
        gasit = True
        poz = i
        break

if gasit:
    print(f"Valoarea {target} gasita la pozitia {poz}")
else:
    print(f"Valoarea {target} nu a fost gasita")
Output real (rulat cu python):
Valoarea 9 gasita la pozitia 3
De ce break?

Instructiunea break opreste bucla imediat ce elementul a fost gasit. Fara ea, algoritmul ar continua sa caute inutil si, daca exista duplicate, ar returna pozitia ultimei aparitii, nu a primei.

4

4. Inserarea unui element

Inserarea unui element la pozitia k necesita mai intai sa mutam la dreapta toate elementele de pe pozitiile k, k+1, ..., n-1, astfel incat pozitia k sa devina libera. Complexitate: O(n) — in cazul cel mai defavorabil (k=0), mutam toate elementele.
Exemplu vizual — inseram valoarea 4 la pozitia 3:

Initial: [3, 7, 2, 9, 5, 1, 8] — n=7

Dupa mutare la dreapta: [3, 7, 2, _, 9, 5, 1, 8] — pozitia 3 e libera

Dupa inserare: [3, 7, 2, 4, 9, 5, 1, 8] — n=8

# Inserarea unui element intr-un vector la o pozitie data
v = [3, 7, 2, 9, 5, 1, 8]
n = len(v)
val_nou = 4
poz_ins = 3

print("Vectorul initial:", v)
print(f"Inseram valoarea {val_nou} la pozitia {poz_ins}")

v.append(0)  # extindem lista cu un element
n = n + 1
for i in range(n - 1, poz_ins, -1):
    v[i] = v[i - 1]
v[poz_ins] = val_nou

print("Vectorul dupa inserare:", v)
Output real (rulat cu python):
Vectorul initial: [3, 7, 2, 9, 5, 1, 8]
Inseram valoarea 4 la pozitia 3
Vectorul dupa inserare: [3, 7, 2, 4, 9, 5, 1, 8]

Atentie la directia buclei: bucla merge descrescator (de la n-1 spre poz_ins+1). Daca am parcurge crescator, am suprascrie elementele inainte de a le muta, pierzand date.

5

5. Stergerea unui element

Stergerea elementului de pe pozitia k necesita mutarea la stanga a tuturor elementelor de pe pozitiile k+1, k+2, ..., n-1. Dupa mutare, ultimul element devine duplicat si se elimina. Complexitate: O(n).
Exemplu vizual — stergem elementul de la pozitia 2 (valoarea 2):

Initial: [3, 7, 2, 9, 5, 1, 8] — n=7

Dupa mutare la stanga: [3, 7, 9, 5, 1, 8, 8] — ultimul e duplicat

Dupa eliminare: [3, 7, 9, 5, 1, 8] — n=6

# Stergerea unui element dintr-un vector la o pozitie data
v = [3, 7, 2, 9, 5, 1, 8]
n = len(v)
poz_sterg = 2

print("Vectorul initial:", v)
print(f"Stergem elementul de la pozitia {poz_sterg} (valoarea {v[poz_sterg]})")

for i in range(poz_sterg, n - 1):
    v[i] = v[i + 1]
v.pop()  # eliminam ultimul element (acum duplicat)
n = n - 1

print("Vectorul dupa stergere:", v)
Output real (rulat cu python):
Vectorul initial: [3, 7, 2, 9, 5, 1, 8]
Stergem elementul de la pozitia 2 (valoarea 2)
Vectorul dupa stergere: [3, 7, 9, 5, 1, 8]

Comparatie cu inserarea: la stergere bucla merge crescator (copiem din dreapta in stanga), la inserare mergea descrescator (copiem din stanga in dreapta). Directia conteaza pentru corectitudinea algoritmului.

6

6. Aceleasi operatii in C++ EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

La profilul intensiv lucram cu tablouri C++ (int v[MAX]). Spre deosebire de Python, dimensiunea tabloului este fixa la compilare si trebuie declarata suficient de mare. Variabila n retine numarul de elemente efectiv folosite. Algoritmii sunt identici ca logica.

Suma elementelor in C++:

#include <iostream>
using namespace std;
int main() {
    int v[] = {3, 7, 2, 9, 5, 1, 8};
    int n = 7;
    int suma = 0;
    for (int i = 0; i < n; i++) {
        suma += v[i];
    }
    cout << "Suma elementelor: " << suma << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
Suma elementelor: 35

Min/Max in C++:

#include <iostream>
using namespace std;
int main() {
    int v[] = {3, 7, 2, 9, 5, 1, 8};
    int n = 7;
    int minim = v[0], maxim = v[0];
    int poz_min = 0, poz_max = 0;
    for (int i = 1; i < n; i++) {
        if (v[i] < minim) { minim = v[i]; poz_min = i; }
        if (v[i] > maxim) { maxim = v[i]; poz_max = i; }
    }
    cout << "Minim: " << minim << " la pozitia " << poz_min << endl;
    cout << "Maxim: " << maxim << " la pozitia " << poz_max << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
Minim: 1 la pozitia 5
Maxim: 9 la pozitia 3

Inserare in C++ (tablou cu capacitate rezervata):

#include <iostream>
using namespace std;
int main() {
    int v[10] = {3, 7, 2, 9, 5, 1, 8};
    int n = 7;
    int val_nou = 4, poz_ins = 3;
    for (int i = n; i > poz_ins; i--) {
        v[i] = v[i - 1];
    }
    v[poz_ins] = val_nou;
    n++;
    cout << "Vectorul dupa inserare: ";
    for (int i = 0; i < n; i++) {
        cout << v[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
Vectorul dupa inserare: 3 7 2 4 9 5 1 8

Stergere in C++:

#include <iostream>
using namespace std;
int main() {
    int v[] = {3, 7, 2, 9, 5, 1, 8};
    int n = 7;
    int poz_sterg = 2;
    for (int i = poz_sterg; i < n - 1; i++) {
        v[i] = v[i + 1];
    }
    n--;
    cout << "Vectorul dupa stergere: ";
    for (int i = 0; i < n; i++) {
        cout << v[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
Vectorul dupa stergere: 3 7 9 5 1 8

Exercitii practice

Exercitiul 1 (Nivel minim) — Suma si extreme

Fie vectorul v = [10, 3, 8, 15, 6, 2, 11]. Calculeaza manual (pas cu pas) suma elementelor, minimul si maximul. Traseaza tabelul de variabile pentru bucla de min/max (coloane: i, v[i], minim, poz_min, maxim, poz_max).

Vezi rezolvarea

Suma: parcurgem vectorul o singura data si acumulam fiecare element. suma = 10+3+8+15+6+2+11 = 55.

Tabelul de variabile pentru bucla de minim/maxim (initializare cu v[0]=10, apoi i de la 1 la 6, ca in lectie):

  1. init: v[0]=10 -> minim=10, poz_min=0, maxim=10, poz_max=0
  2. i=1: v[1]=3 -> 3 e mai mic decat 10, deci minim=3, poz_min=1 (maxim neschimbat)
  3. i=2: v[2]=8 -> nu e nici sub minim, nici peste maxim, nimic nu se schimba
  4. i=3: v[3]=15 -> 15 e mai mare decat 10, deci maxim=15, poz_max=3
  5. i=4: v[4]=6 -> nimic nu se schimba
  6. i=5: v[5]=2 -> 2 e mai mic decat 3, deci minim=2, poz_min=5
  7. i=6: v[6]=11 -> nimic nu se schimba

Rezultat final: minim = 2 (pozitia 5), maxim = 15 (pozitia 3), suma = 55.

Exercitiul 2 (Nivel standard) — Cautare si inserare

Pornind de la vectorul v = [5, 12, 3, 8, 19, 7]: (a) Cauta valoarea 19 si indica pozitia (numarare de la 0). (b) Insereaza valoarea 10 la pozitia 2. Scrie vectorul rezultat si explica toti pasii de mutare.

Vezi rezolvarea

(a) Cautare secventiala: parcurgem v = [5, 12, 3, 8, 19, 7] de la stanga: pozitia 0 are 5, pozitia 1 are 12, pozitia 2 are 3, pozitia 3 are 8, pozitia 4 are 19 -> gasit, ne oprim (break). Valoarea 19 se afla la pozitia 4.

(b) Inserare la pozitia 2: ca in lectie, marim vectorul cu un loc (n devine 7) si mutam elementele la dreapta, de la ultima pozitie catre pozitia 3, ca sa nu suprascriem valori nemutate inca:

  1. v[6] devine v[5] = 7
  2. v[5] devine v[4] = 19
  3. v[4] devine v[3] = 8
  4. v[3] devine v[2] = 3
  5. v[2] devine 10 (valoarea noua, pozitia e acum libera)

Vectorul rezultat: [5, 12, 10, 3, 8, 19, 7].

Exercitiul 3 (Nivel performanta) — Stergere conditionata

Scrie un algoritm (in Python sau pseudocod) care sterge din vector toate aparitiile unei valori date. Atentie: dupa fiecare stergere pozitiile se decaleaza — gestioneaza corect indicele. Indica si justifica complexitatea algoritmului.

Vezi rezolvarea

Cerinta combina atomul 5 (stergere) cu o bucla care sterge TOATE aparitiile - asta nu apare exact asa in lectie, deci mai jos e o schita de rezolvare, nu codul gata scris.

  1. Capcana principala: daca stergi elementul de pe pozitia i si apoi faci i = i+1 necontrolat, sari peste elementul care tocmai a ajuns pe pozitia i (toate elementele de dupa s-au mutat cu un loc la stanga).
  2. Schema simpla (ca in atomul 5, repetata): parcurgi cu indicele i care NU creste automat; cand v[i] este egal cu valoarea cautata, muti la stanga si reduci n (ca la stergerea unui singur element) fara sa incrementezi i; cand v[i] e diferit, abia atunci treci la i+1.
  3. Alternativa mai buna: construiesti un vector nou, copiind doar elementele diferite de valoarea cautata, intr-o singura parcurgere.
  4. Complexitate: schema cu stergeri repetate este O(n^2) in cazul cel mai defavorabil (multe aparitii, fiecare stergere costa O(n)); schema cu vector nou este O(n).

Criterii de evaluare: gestionarea corecta a indicelui dupa stergere (fara elemente sarite, fara iesire din indici), complexitatea calculata si justificata, si testarea pe un caz cu aparitii consecutive ale valorii cautate.

Ce ai invatat astazi

  • Suma elementelor: initializare la 0, bucla O(n)
  • Min/Max: initializare cu primul element, retinerea pozitiei
  • Cautare secventiala: break la gasire, O(n) in cazul defavorabil
  • Inserare: mutare la dreapta descrescator, apoi asignare la pozitia k
  • Stergere: mutare la stanga crescator, apoi eliminare duplicat final
  • C++ (intensiv): aceeasi logica, tablou cu dimensiune maxima declarata la compilare

Vrei mai mult?

Provocare: Scrie o functie care elimina toate duplicatele dintr-un vector, pastrand DOAR prima aparitie a fiecarei valori, folosind tehnica de stergere invatata azi (mutare la stanga) — fara set() si fara alta structura auxiliara. Testeaza cu v = [3, 1, 3, 5, 1, 1, 7]; rezultatul trebuie sa fie [3, 1, 5, 7].

Intrebare de gandit: La inserare mutam elementele de la dreapta spre stanga (de la n-1 catre k), dar la stergere mutam de la stanga spre dreapta (de la k catre n-1). De ce conteaza ordinea asta? Ce s-ar strica daca ai inversa directia in oricare din cele doua cazuri?

Deschidere: Cand editezi un text si apesi Delete pe o litera din mijloc, editorul foloseste exact tehnica de mutare la stanga pe vectorul de caractere din memorie. Editoare precum Emacs folosesc insa o structura mai avansata, gap buffer, tocmai ca sa evite mutarea a mii de caractere la fiecare apasare de tasta.

Urmatoarea lectie

Continua cu Lectia 3 pentru a invata despre secvente in vectori: secventa maxima, subsiruri si algoritmi clasici de tip BAC.

Continua →