Minim și maxim

Minimul este cea mai mică valoare dintr-un șir, iar maximul cea mai mare. Dacă temperaturile din trei zile sunt 12, 8 și 15 grade, minimul este 8, iar maximul 15. Un algoritm le poate găsi parcurgând valorile pe rând, fără să le ordoneze.

Pornește cu prima valoare ca minim și maxim provizorii. Pentru șirul $[12,8,15]$ ambele sunt inițial 12. Apoi compari fiecare valoare nouă cu ele:

1. Citești 12: minimul este 12 și maximul este 12.
2. Citești 8: valoarea 8 este mai mică decât 12, deci minimul devine 8; maximul rămâne 12.
3. Citești 15: valoarea 15 este mai mare decât 12, deci maximul devine 15; minimul rămâne 8.

La sfârșit ai verificat toate valorile, deci poți da răspunsul: minim 8, maxim 15. Scrie această urmărire într-un tabel dacă te încurci.

De ce nu pornești mereu cu minimul 0? Dacă toate temperaturile ar fi 5, 7 și 9, ai răspunde greșit „0”, deși 0 nu apare în șir. Prima valoare este un punct de pornire sigur când știi că șirul nu este gol. Dacă nu există nicio valoare, problema trebuie să spună ce răspuns se dorește; „minimul șirului gol” nu este o valoare obișnuită pe care o poți ghici.

Pentru fiecare valoare nouă, pui două întrebări: „Este mai mică decât minimul de până acum?” și „Este mai mare decât maximul de până acum?” O valoare repetată nu schimbă nimic. Metoda merge și pentru numere negative. De exemplu, în $[-4,-9,-2]$ minimul este $-9$, iar maximul $-2$; nu confunda „mai mic” cu „mai aproape de zero”.

Uneori nu te interesează valoarea, ci ziua în care a apărut. Ținând minte, pe lângă minim, numărul zilei, afli că în șirul $[12,8,15]$ cea mai rece zi este a doua, iar cea mai caldă a treia. Dacă o valoare extremă apare de mai multe ori, ai de ales dacă vrei prima sau ultima apariție; enunțul spune care.

Invarianta parcurgerii este: după primele $k$ elemente, mn și mx sunt minimul și maximul acelui prefix. Inițializarea din primul element o face adevărată pentru $k=1$; comparațiile o păstrează la fiecare pas. Algoritmul face $n-1$ comparații pentru minim și $n-1$ pentru maxim, deci timpul este proporțional cu $n$, iar memoria auxiliară este constantă; șirul nu trebuie memorat, ci poate fi prelucrat pe măsură ce este citit.

Exemplul 1 — minimul și maximul unui șir citit. Se citește $n\ge 1$, apoi cele $n$ valori. Pentru intrarea 4 12 8 15 9 stările $(\text{mn};\text{mx})$ după fiecare valoare sunt $(12;12)$, $(8;12)$, $(8;15)$ și $(8;15)$.

#include <iostream>
using namespace std;
int main() {
    int n, x;
    cin >> n >> x;
    int mn = x, mx = x;
    for (int i = 1; i < n; ++i) {
        cin >> x;
        if (x < mn) mn = x;
        if (x > mx) mx = x;
    }
    cout << mn << ' ' << mx;
    return 0;
}

Programul afișează 8 15. Prima valoare este citită înainte de ciclu, de aceea ciclul pornește de la $i=1$ și face $n-1$ repetări. Pentru $n=1$ ciclul nu se execută și programul afișează aceeași valoare de două ori. Pentru valori negative nu apare nicio schimbare de metodă: cu intrarea 3 -4 -9 -2 rezultatul este -9 -2.

Exemplul 2 — poziția primului minim și numărul apariților. Pentru șirul $7,3,9,3,5$ se ține, pe lângă minim, poziția primei apariții (numerotare de la 1) și un contor. Când o valoare este mai mică decât minimul, se actualizează minimul, poziția și contorul devine 1. Când este egală cu minimul, contorul crește, dar poziția rămâne.

1. $7$: minim 7, poziție 1, contor 1.
2. $3<7$: minim 3, poziție 2, contor 1.
3. $9$: nu schimbă nimic.
4. $3=3$: contorul devine 2, poziția rămâne 2.
5. $5$: nu schimbă nimic.

v = [7, 3, 9, 3, 5]
mn = v[0]
poz = 1
cnt = 1
for i in range(1, len(v)):
    if v[i] < mn:
        mn = v[i]
        poz = i + 1
        cnt = 1
    elif v[i] == mn:
        cnt += 1
print(mn, poz, cnt)

Programul afișează 3 2 2: minimul 3 apare de două ori, prima dată pe poziția 2. Indicele din Python pornește de la 0, de aceea poziția de la 1 este i + 1.

Exemplul 3 — extremul valorilor care respectă o condiție. Pentru cel mai mic număr par dintr-un șir nu poți inițializa minimul cu primul element, fiindcă acesta poate fi impar. Folosești un indicator exista, la început fals: primul număr par găsit îl fixează ca minim, iar următoarele îl pot îmbunătăți. Pentru șirul $7,9,4,10,6$ rezultatul este 4. Dacă șirul este $7,9,5$, indicatorul rămâne fals și programul afișează un mesaj, de exemplu „nu există”.

Exemplul 4 — amplitudinea unui șir. Amplitudinea este diferența dintre maxim și minim; de exemplu, ea arată cu câte grade a variat temperatura într-o zi. Se citesc $n$ și cele $n$ valori, iar programul determină ambele extreme într-o singură parcurgere și le scade abia la sfârșit:

#include <iostream>
using namespace std;
int main() {
    int n, x;
    cin >> n >> x;
    int mn = x, mx = x;
    for (int i = 1; i < n; ++i) {
        cin >> x;
        if (x < mn) mn = x;
        if (x > mx) mx = x;
    }
    cout << mx - mn;
}

Pentru intrarea 5 14 9 17 9 12 stările $(\text{mn};\text{mx})$ sunt $(14;14)$, $(9;14)$, $(9;17)$, $(9;17)$ și $(9;17)$. Se afișează $17-9=8$. Caz-limită: pentru șirul $6,6,6$ minimul și maximul sunt egale, deci amplitudinea este 0, iar pentru $n=1$ rezultatul este tot 0. Diferența nu poate fi negativă, deoarece mx nu coboară sub mn.

Nu presupune că inițializarea cu zero este sigură. La șirul $-4,-9,-2$, dacă mx pornește de la 0, programul raportează 0, valoare care nu apare în șir; inițializarea din primul element dă $-2$. Pentru $n=1$ aceeași valoare este și minim, și maxim. Dacă șirul este citit până la un marcaj (de exemplu 0), marcajul nu face parte din șir și nu trebuie comparat. Tipul variabilelor mn și mx trebuie să fie cel al valorilor citite. Dacă secvența inițializează minimul cu o valoare „foarte mare” (de pildă 1000) și valorile pot depăși această limită, rezultatul este greșit; limita se alege din domeniul dat în enunț. Pentru a afla în aceeași parcurgere și minimul, și maximul, se folosesc două comparații independente, nu un else între ele: la primul element ambele condiții pot fi adevărate.

Exemplu în formatul examenului. Se citesc, în această ordine, numerele $-4,-9,-2,-7$. Ce se afișează în urma executării secvenței de mai jos?

int x, mx = 0;
for (int i = 1; i <= 4; i++) {
    cin >> x;
    if (x > mx)
        mx = x;
}
cout << mx;

• a) -2
• b) 0
• c) -9
• d) -4

Răspunsul corect este b). Variabila mx pornește de la 0 și rămâne 0, pentru că nicio valoare citită nu este mai mare decât 0: $-4>0$, $-9>0$, $-2>0$ și $-7>0$ sunt false. Valoarea afișată, 0, nu apare în șir. Varianta a) ar fi răspunsul corect dacă mx ar fi fost inițializat cu prima valoare citită, iar varianta c) este minimul șirului.

Greșeli frecvente

• Greșit: minimul poate fi inițializat mereu cu zero.
  Corect: pornește de la prima valoare a unui șir nevid.
• Greșit: pentru $[-4,-9,-2]$ maximul este $-9$.
  Corect: $-2$ este mai mare decât celelalte două valori.
• Greșit: trebuie sortat întregul șir pentru a afla extremele.
  Corect: o singură parcurgere este suficientă.

Înainte și după