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).

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.

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.

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

Urmatoarea lectie

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

Continua →