Ce vei învăța astăzi?
După această lecție, vei putea identifica și implementa algoritmii pentru găsirea elementului minim și maxim dintr-un vector.
Ce înseamnă minim și maxim?
Definiție: Într-o mulțime de valori, minimul este cea mai mică valoare, iar maximul este cea mai mare valoare.
Exemplu: Pentru vectorul [7, 3, 9, 2, 5], minimul este 2, iar maximul este 9.
Analogii pentru a înțelege minimul și maximul:
Într-o clasă, cel mai scurt elev este "minimul", cel mai înalt este "maximul".
La un test, cea mai mică notă este minimul, cea mai mare este maximul.
Într-o săptămână, cea mai scăzută temperatură este minimul, cea mai ridicată este maximul.
În multe probleme, profesorul (sau enunțul) îți cere „scrie algoritmul”. Uite traducerea corectă, ca să știi exact ce copiezi în C++.
int minVal = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < minVal) minVal = v[i];
}
cout << minVal;
int maxVal = v[0];
for (int i = 1; i < n; i++) {
if (v[i] > maxVal) maxVal = v[i];
}
cout << maxVal;
int minVal = v[0];
int pozMin = 0;
for (int i = 1; i < n; i++) {
if (v[i] < minVal) {
minVal = v[i];
pozMin = i;
}
}
cout << minVal << " " << pozMin;
// după ce ai minVal:
for (int i = 0; i < n; i++) {
if (v[i] == minVal) cout << i << " ";
}
Două situații diferite: „poziția minimului” poate însemna prima apariție (un singur index), sau toate aparițiile (mai multe indexuri). În enunț, caută cuvântul „toate”.
Inițializarea corectă: de ce min = v[0] și nu 0?
La minim/maxim, inițializarea e cheia. Dacă pornești cu o valoare „la întâmplare”
(de exemplu 0), algoritmul se strică pe unele teste.
De aceea, metoda sigură este: pornești cu primul element al vectorului și compari restul.
| Greșeală frecventă | De ce e greșit | Corect |
|---|---|---|
int minVal = 0; |
Dacă toate valorile sunt pozitive, minimul rămâne 0 deși 0 nu există în vector. | int minVal = v[0]; |
int maxVal = 0; |
Dacă toate valorile sunt negative, maximul rămâne 0 deși 0 nu există în vector. | int maxVal = v[0]; |
Buclă de la i=0 |
Îl compari pe v[0] cu el însuși (nu e o tragedie, dar e inutil). |
Inițializezi cu v[0] și începi de la i=1. |
int minVal = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < minVal) minVal = v[i];
}
#include <climits>
int minVal = INT_MAX; // cel mai mare int posibil
int maxVal = INT_MIN; // cel mai mic int posibil
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x < minVal) minVal = x;
if (x > maxVal) maxVal = x;
}
Metoda cu v[0] e perfectă când ai citit vectorul.
Metoda cu INT_MAX/INT_MIN e utilă când citești valorile una câte una și nu ai nevoie să le păstrezi.
Algoritmii pentru minim și maxim
Regula de aur: Întotdeauna inițializezi minimul cu primul element al vectorului (v[0]). Dacă ai un vector gol, trebuie să tratezi acest caz special.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
const int MAX = 1000;
int v[MAX];
// Citire vector
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// Găsire minim
int min = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < min) {
min = v[i];
}
}
cout << "Minimul este: " << min << endl;
return 0;
}
Observație: Algoritmul pentru maxim este identic cu cel pentru minim, doar semnul de comparație se schimbă (< devine >).
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
const int MAX = 1000;
int v[MAX];
// Citire vector
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// Găsire maxim
int max = v[0];
for (int i = 1; i < n; i++) {
if (v[i] > max) {
max = v[i];
}
}
cout << "Maximul este: " << max << endl;
return 0;
}
Optimizare: Putem verifica ambele condiții în aceeași buclă, fără a fi nevoie de două bucle separate. Aceasta este mult mai eficient!
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
const int MAX = 1000;
int v[MAX];
// Citire vector
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// Găsire simultană min și max
int min = v[0];
int max = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < min) {
min = v[i];
}
if (v[i] > max) {
max = v[i];
}
}
cout << "Minimul este: " << min << endl;
cout << "Maximul este: " << max << endl;
return 0;
}
Exercițiu de completare - Găsirea minimului:
Completează codul C++ pentru găsirea minimului într-un vector:
Bancă de cuvinte:
Test de înțelegere: Cum funcționează algoritmul?
Test rapid - algoritmul minimului:
Avem vectorul: v = [8, 3, 10, 2, 7]
Simulare algoritm minim:
Care este valoarea inițială corectă pentru variabila min?
De ce începem bucla de la i=1 și nu de la i=0?
Sfaturi practice pentru algoritmii min/max
Ținta: un cod care merge corect pentru orice date (pozitive, negative, egale).
| Sfat | De ce e important | Exemplu |
|---|---|---|
Inițializează cu v[0] |
Funcționează pentru orice valori | int minVal = v[0]; |
Începe bucla de la i=1 |
Evită comparația inutilă cu primul element | for (int i=1; i<n; i++) |
Tratează cazul n=0 |
Altfel accesezi v[0] și apare eroare |
if (n==0) return 0; |
| Testează cu negative și cu valori egale | Îți validează inițializarea și comparațiile | -5 0 -2 / 7 7 7 |
| Ai nevoie de min și max? caută-le simultan | O singură parcurgere | if (v[i]<min) ...; if (v[i]>max) ...; |
Capcane comune și soluții pentru min/max
și soluții pentru min/maxGreșeli frecvente la algoritmii min/max:
Soluție: Întotdeauna inițializează cu primul element al vectorului.
Dacă n=0, atunci accesarea v[0] este eroare.
Ineficient - parcurgi vectorul de două ori.
Best Practices pentru algoritmii min/max:
int min = v[0];
minVal, maxVal nu doar min, max
Încălzire (2 minute)
Test rapid - identificare minim/maxim: Care sunt minimul și maximul pentru următoarele vectori?
[5, 2, 9, 1, 7]→ Minim: verifică, Maxim: verifică[-3, 0, 8, -5, 4]→ Minim: verifică, Maxim: verifică[10, 10, 10, 10]→ Minim: verifică, Maxim: verifică
Hint: Minimul este cea mai mică valoare, maximul este cea mai mare.
PbInfo #20 - Minimul a n numere
Enunț:
Cerință: Se citește un număr n și apoi n numere întregi. Să se determine cel mai mic număr dintre cele n numere date.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere întregi.
Date de ieșire:
Programul va afișa pe ecran cel mai mic număr dintre cele n numere citite.
Exemplu:
Intrare:
5 10 20 5 30 15
Ieșire:
5
Explicație: Cel mai mic număr dintre 10, 20, 5, 30, 15 este 5
Cum gândim soluția:
- Citim numărul n (dimensiunea vectorului)
- Declarăm un vector cu dimensiunea n sau cu dimensiune maximă
- Citim cele n elemente în vector
- Inițializăm minimul cu primul element:
min = v[0] - Parcurgem vectorul de la al doilea element până la ultimul:
for (int i = 1; i < n; i++)- Dacă
v[i] < min, atuncimin = v[i]
- Afișăm minimul
Execuție pentru n=4 cu valori 7, 2, 9, 4:
Ce trebuie să verifici mereu?
- Cazul n=0 (vector gol) - trebuie tratat special
- Numere negative - algoritmul trebuie să funcționeze corect
- Toate numerele egale - minimul va fi acea valoare
- Dimensiunea vectorului să fie suficient de mare
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
// Verificăm cazul special n=0
if (n == 0) {
cout << "Vectorul este gol!" << endl;
return 0;
}
const int MAX = 1000;
int v[MAX];
// Citire elemente
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// Găsire minim
int min = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < min) {
min = v[i];
}
}
// Afișare rezultat
cout << min << endl;
return 0;
}
Ce învățăm din această problemă:
- Algoritmul de bază pentru minim: inițializare + parcurgere + comparație
- Tratarea cazurilor speciale: vector gol (n=0)
- Importanța inițializării corecte: cu primul element
- Eficiența algoritmului: O(n) - o singură parcurgere
- Robustețea codului: funcționează pentru orice n și orice valori
PbInfo #21 - Maximul a n numere
Problemă care afișează cel mai mare număr dintr-un șir
Enunț:
Cerință: Se citește un număr n și apoi n numere întregi. Să se determine cel mai mare număr dintre cele n numere date.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere întregi.
Date de ieșire:
Programul va afișa pe ecran cel mai mare număr dintre cele n numere citite.
Exemplu:
Intrare:
5 10 20 5 30 15
Ieșire:
30
Explicație: Cel mai mare număr dintre 10, 20, 5, 30, 15 este 30
Cum gândim soluția:
- Citim n și cele n elemente (ca la problema anterioară)
- Inițializăm maximul cu primul element:
max = v[0] - Parcurgem vectorul de la al doilea element până la ultimul:
for (int i = 1; i < n; i++)- Dacă
v[i] > max, atuncimax = v[i]
- Afișăm maximul
- Diferența față de minim: schimbăm semnul de comparație (< devine >)
Cum funcționează pentru n=4 cu valori 7, 2, 9, 4:
De ce semnul > și nu
Pentru că vrem să găsim cel mai mare număr, deci comparăm pentru a vedea dacă elementul curent este mai mare decât maximul curent.
Formula cheie pentru maxim: if (v[i] > max) max = v[i];
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
// Verificăm cazul special n=0
if (n == 0) {
cout << "Vectorul este gol!" << endl;
return 0;
}
const int MAX = 1000;
int v[MAX];
// Citire elemente
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// Găsire maxim
int max = v[0];
for (int i = 1; i < n; i++) {
if (v[i] > max) {
max = v[i];
}
}
// Afișare rezultat
cout << max << endl;
return 0;
}
Varianta combinată cu minimul:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 0) {
cout << "Vectorul este gol!" << endl;
return 0;
}
const int MAX = 1000;
int v[MAX];
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// Găsim simultan minimul și maximul
int min = v[0];
int max = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < min) {
min = v[i];
}
if (v[i] > max) {
max = v[i];
}
}
cout << "Minimul este: " << min << endl;
cout << "Maximul este: " << max << endl;
return 0;
}
Ce învățăm din această problemă:
- Algoritmul pentru maxim: identic cu minimul, dar cu semnul >
- Importanța semnului de comparație: < pentru minim, > pentru maxim
- Optimizarea prin găsire simultană: o singură parcurgere pentru ambele
- Reutilizarea codului: structura este aceeași ca la minim
- Abstracția algoritmului: același pattern pentru diverse tipuri de căutări
PbInfo #22 - Minimul și maximul simultan
Problemă care afișează atât minimul cât și maximul dintr-un șir
Enunț:
Cerință: Se citește un număr n și apoi n numere întregi. Să se determine simultan cel mai mic și cel mai mare număr dintre cele n numere date.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere întregi.
Date de ieșire:
Programul va afișa pe ecran două numere: mai întâi minimul, apoi maximul, separate printr-un spațiu.
Exemplu:
Intrare:
5 10 20 5 30 15
Ieșire:
5 30
Explicație: Minimul este 5, maximul este 30
Cum gândim soluția:
- Citim n și cele n elemente
- Inițializăm atât minimul cât și maximul cu primul element:
min = v[0]max = v[0]
- Parcurgem vectorul o singură dată:
for (int i = 1; i < n; i++)- Dacă
v[i] < min, atuncimin = v[i] - Dacă
v[i] > max, atuncimax = v[i]
- Afișăm minimul și maximul
- Avantaj: o singură parcurgere, nu două!
Execuție pentru n=4 cu valori 7, 2, 9, 4:
De ce este mai eficient să găsim simultan?
Pentru că parcurgem vectorul o singură dată (O(n)), în loc de două ori (O(2n)). Pentru vectori mari, această optimizare este semnificativă.
Regula de eficiență: Întotdeauna când ai nevoie de mai multe informații dintr-un vector, încearcă să le obții într-o singură parcurgere.
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
// Verificăm cazul special n=0
if (n == 0) {
cout << "Vectorul este gol!" << endl;
return 0;
}
const int MAX = 1000;
int v[MAX];
// Citire elemente
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// Găsire simultană minim și maxim
int min = v[0];
int max = v[0];
for (int i = 1; i < n; i++) {
// Verificăm pentru minim
if (v[i] < min) {
min = v[i];
}
// Verificăm pentru maxim
if (v[i] > max) {
max = v[i];
}
}
// Afișare rezultate
cout << min << " " << max << endl;
return 0;
}
Varianta optimizată (cu else if):
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 0) {
cout << "Vectorul este gol!" << endl;
return 0;
}
const int MAX = 1000;
int v[MAX];
for (int i = 0; i < n; i++) {
cin >> v[i];
}
int min = v[0];
int max = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < min) {
min = v[i];
} else if (v[i] > max) {
max = v[i];
}
}
cout << min << " " << max << endl;
return 0;
}
Ce învățăm din această problemă:
- Optimizarea algoritmilor: o singură parcurgere pentru multiple operații
- Gândirea eficientă: evitatea parcurgerilor inutile
- Structura de control: if-else pentru a evita verificări inutile
- Importanța cazurilor de margine: n=0, n=1, toate elementele egale
- Abordarea practică: în aplicații reale, mereu încercăm să optimizăm
Exercițiul Practic: Aplicarea algoritmilor min/max
Sarcini de lucru
Completează următoarele sarcini pentru a-ți consolida cunoștințele despre algoritmii minim și maxim
Sarcina 1: Analiză și corectare cod
Analizează următorul cod și găsește greșelile:
#include <iostream>
using namespace std;
int main() {
int n = 5;
int vector[5] = {8, 3, 10, 2, 7};
// Găsire minim
int min = 0;
for (int i = 0; i < n; i++) {
if (vector[i] < min) {
min = vector[i];
}
}
// Găsire maxim
int max = 0;
for (int i = 0; i < n; i++) {
if (vector[i] > max) {
max = vector[i];
}
}
cout << "Min: " << min << ", Max: " << max << endl;
return 0;
}
Soluție pentru Sarcina 1:
Greșeli identificate și corecții:
- 1. Inițializare greșită a minimului:
int min = 0;este greșit dacă vectorul conține numere pozitive.
Corect:int min = vector[0]; - 2. Inițializare greșită a maximului:
int max = 0;este greșit dacă vectorul conține numere negative.
Corect:int max = vector[0]; - 3. Parcurgere ineficientă:
Se parcurge vectorul de două ori pentru min și max separat.
Corect: Găsește ambele într-o singură parcurgere. - 4. Buclele încep de la 0 în loc de 1:
Dacă inițializăm cu vector[0], nu mai trebuie să îl verificăm din nou.
Corect:for (int i = 1; i < n; i++)
Cod corectat:
#include <iostream>
using namespace std;
int main() {
int n = 5;
int vector[5] = {8, 3, 10, 2, 7};
// Găsire simultană minim și maxim
int min = vector[0];
int max = vector[0];
for (int i = 1; i < n; i++) {
if (vector[i] < min) {
min = vector[i];
}
if (vector[i] > max) {
max = vector[i];
}
}
cout << "Min: " << min << ", Max: " << max << endl;
return 0;
}
Sarcina 2: Implementare completă
Cerință: Scrie un program care citește n, apoi n numere. Programul afișează: 1. Minimul și maximul 2. Pozițiile pe care apar minimul și maximul (toate pozițiile) 3. Diferența dintre maxim și minim
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 0) {
cout << "Vectorul este gol!" << endl;
return 0;
}
const int MAX = 1000;
int v[MAX];
// 1. Citire elemente
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// 2. Găsire minim și maxim
int min = v[0];
int max = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < min) {
min = v[i];
}
if (v[i] > max) {
max = v[i];
}
}
cout << "Minimul este: " << min << endl;
cout << "Maximul este: " << max << endl;
// 3. Pozițiile minimului
cout << "Minimul apare pe pozitiile: ";
for (int i = 0; i < n; i++) {
if (v[i] == min) {
cout << i << " ";
}
}
cout << endl;
// 4. Pozițiile maximului
cout << "Maximul apare pe pozitiile: ";
for (int i = 0; i < n; i++) {
if (v[i] == max) {
cout << i << " ";
}
}
cout << endl;
// 5. Diferența
int diferenta = max - min;
cout << "Diferenta dintre maxim si minim este: " << diferenta << endl;
return 0;
}
Explicații importante:
- Găsirea pozițiilor: După ce am găsit min și max, parcurgem vectorul din nou pentru a găsi toate pozițiile unde apar.
- Eficiența: Prima parcurgere O(n) pentru min/max, a doua parcurgere O(n) pentru poziții. Total O(2n) = O(n).
- Tratarea cazurilor: Dacă min și max sunt aceeași valoare, atunci ambele bucle pentru poziții vor afișa aceleași poziții.
- Teste recomandate:
- n=5, valori: 1 2 3 4 5 (min=1 pe poziția 0, max=5 pe poziția 4)
- n=4, valori: 5 2 5 2 (min=2 pe pozițiile 1,3; max=5 pe pozițiile 0,2)
- n=3, valori: 7 7 7 (min=max=7 pe toate pozițiile)