Maxim si minim - Gasim extremele!

Maximul este cea mai mare valoare din sir, iar minimul este cea mai mica valoare. Aceste doua valori se numesc extreme si sunt printre cele mai importante informatii pe care le putem extrage dintr-un sir de numere.

In viata de zi cu zi, cautam maxime si minime tot timpul. Care este cea mai mare nota din catalog? Care este cea mai mica temperatura din saptamana? Care jucator a marcat cele mai multe goluri? Care este cel mai ieftin produs din magazin? Toate aceste intrebari cer gasirea maximului sau minimului dintr-o lista de valori.

Cand sirul are putine elemente, poti gasi maximul si minimul dintr-o privire. Dar imagineaza-ti un sir cu temperaturile din fiecare zi a unui an (365 de valori) sau notele tuturor elevilor dintr-o scoala (sute de valori). In aceste cazuri, ai nevoie de un algoritm care sa parcurga sirul sistematic si sa gaseasca extremele automat.

O observatie importanta: maximul si minimul sunt intotdeauna elemente ale sirului. Nu sunt valori inventate sau calculate - sunt valori care exista efectiv in sir. De exemplu, daca sirul este [3, 7, 2, 9], maximul este 9 (nu 10 sau alta valoare) si minimul este 2 (nu 0 sau 1).

Strategia pentru a gasi maximul este simpla si intuitiva. Gandeste-te cum ai cauta cel mai inalt elev din clasa ta: te uiti la primul, retii inaltimea lui ca "cel mai inalt de pana acum". Apoi te uiti la al doilea - daca e mai inalt, acela devine noul "cel mai inalt". Continui pana termini toata clasa.

Algoritmul face exact acelasi lucru, in trei pasi:

1. Presupunem ca primul element este maximul
2. Parcurgem restul sirului (de la al doilea element)
3. La fiecare pas, comparam elementul curent cu maximul - daca gasim un element mai mare, acela devine noul maxim

De ce presupunem ca primul element este maximul si nu initializam cu 0? Pentru ca sirul ar putea contine doar numere negative (de exemplu, [-5, -3, -8]). Daca am initializa maximul cu 0, la final am obtine 0 ca maxim, dar 0 nu exista in sir! Initializarea cu primul element garanteaza ca maximul final va fi intotdeauna un element real din sir.

Aceasta strategie se numeste presupune si verifica : presupunem un raspuns initial (primul element) si apoi verificam daca exista un raspuns mai bun parcurgand restul sirului. Este un tipar foarte puternic in algoritmistica si il vei intalni in multe alte contexte.

Sa scriem algoritmul complet in pseudocod. Observa ca parcurgerea incepe de la pozitia 2, nu de la 1, deoarece primul element a fost deja luat ca valoare initiala pentru maxim:

Sa urmarim traseul complet pentru sirul v = [7, 3, 12, 5, 9] cu n=5:

Observa ca maximul s-a schimbat o singura data (la pasul i=3, cand am gasit 12). In cel mai bun caz, maximul nu se schimba deloc (cand primul element este deja cel mai mare). In cel mai rau caz, maximul se schimba la fiecare pas (cand sirul este sortat crescator: [1, 3, 5, 7, 9]).

Nota tehnica: bucla poate incepe si de la i=1 in loc de i=2. In acest caz, la primul pas comparam v[1] cu v[1] (maxim cu el insusi), ceea ce este inutil dar nu gresit. Inceperea de la i=2 este mai eficienta (cu o comparatie mai putin), dar ambele variante dau acelasi rezultat.

Algoritmul pentru minim este aproape identic cu cel pentru maxim. Singura diferenta este conditia de comparatie : in loc de > (mai mare), folosim < (mai mic). Cautam valori mai mici decat minimul curent.

Sa facem traseul pentru acelasi sir v = [7, 3, 12, 5, 9] cu n=5:

Observa simetria perfecta intre algoritmii de maxim si minim. Structura este identica, doar conditia difera: > pentru maxim, < pentru minim. Aceasta simetrie face foarte usor sa scrii un algoritm daca il cunosti pe celalalt - trebuie doar sa schimbi sensul comparatiei.

Un exercitiu util: daca ai deja algoritmul de maxim scris si ai nevoie de minim, fa urmatoarele modificari: (1) schimba numele variabilei din maxim in minim , (2) schimba conditia din > in < . Atat! Restul ramane identic.

La fel ca la maxim, initializarea se face cu primul element al sirului, nu cu 0 sau alta valoare arbitrara. Daca sirul contine doar numere pozitive mari (de exemplu, [100, 200, 300]) si am initializa minimul cu 0, am obtine 0 ca minim - dar 0 nu exista in sir!

Uneori nu este suficient sa stim doar valoarea maximului - vrem sa stim si unde se afla in sir (pe ce pozitie). De exemplu, daca avem notele elevilor si gasim nota maxima 10, vrem sa stim si care elev a luat nota 10 (adica pe ce pozitie in sir se afla aceasta nota).

Observa ca am adaugat o variabila noua: poz_max . O initializam cu 1 (pozitia primului element, pe care l-am presupus maxim). In interiorul conditiei DACA, cand actualizam maximul, actualizam simultan si pozitia: poz_max = i . Astfel, la orice moment, poz_max contine pozitia elementului maxim gasit pana acum.

Acelasi principiu se aplica pentru pozitia minimului. Adaugam variabila poz_min initializata cu 1 si o actualizam in interiorul conditiei de minim: poz_min = i .

Daca maximul apare de mai multe ori in sir (de exemplu, v = [5, 12, 8, 12, 3]), algoritmul va retine pozitia primei aparitii (poz_max=2). Daca vrem ultima aparitie, schimbam conditia din > in >= . Daca vrem toate pozitiile, trebuie o abordare diferita: parcurgem sirul, gasim maximul, apoi parcurgem din nou si afisam toate pozitiile unde valoarea este egala cu maximul.

O intrebare fireasca: putem gasi atat maximul cat si minimul intr-o singura parcurgere? Raspunsul este da ! Punem ambele conditii in aceeasi bucla FOR, una dupa alta. La fiecare pas, verificam daca elementul curent este mai mare decat maximul SI daca este mai mic decat minimul.

Observa ca ambele variabile (maxim si minim) sunt initializate cu v[1]. La fiecare pas al parcurgerii, se fac doua verificari independente: una pentru maxim si una pentru minim. Un element nu poate fi simultan mai mare decat maximul SI mai mic decat minimul, deci la fiecare pas cel mult una dintre conditii este adevarata.

Aceasta abordare este eficienta : parcurgem sirul o singura data si obtinem ambele rezultate. Alternativa ar fi sa parcurgem sirul de doua ori (o data pentru maxim, o data pentru minim), dar aceasta ar fi mai lenta. In programare, eficienta conteaza - cu cat facem mai putine parcurgeri, cu atat programul ruleaza mai repede.

Putem extinde aceasta idee si mai mult: intr-o singura parcurgere putem calcula suma, media, maximul si minimul. Toate aceste operatii se pot face simultan, adaugand instructiunile corespunzatoare in corpul aceleiasi bucle FOR.

Aceasta este una dintre cele mai importante lectii de retinut: nu initializa niciodata maximul sau minimul cu 0 (sau cu orice alta valoare arbitrara). Initializeaza intotdeauna cu primul element al sirului. Sa vedem de ce prin doua exemple concrete.

Exemplul 1: Maxim gresit cu numere negative

Daca initializam maximul cu 0 si sirul contine [-5, -3, -8, -1], la fiecare pas verificam daca elementul este mai mare decat 0. Niciun element nu este mai mare decat 0, deci maximul ramane 0. Dar 0 nu exista in sir! Raspunsul corect este -1 (cel mai mare numar din sir), pe care l-am fi gasit daca am fi initializat cu v[1]=-5.

Exemplul 2: Minim gresit cu numere pozitive

Daca initializam minimul cu 0 si sirul contine doar numere pozitive, niciun element nu va fi mai mic decat 0, deci minimul ramane 0. Dar raspunsul corect este 8 (cel mai mic numar din sir).

La teste si examene, aceasta greseala de initializare este una dintre cele mai penalizate. Multi elevi scriu algoritmul perfect dar pierd puncte deoarece initializeaza cu 0 in loc de v[1]. Retine aceasta regula si nu o uita niciodata: maxim si minim se initializeaza cu primul element.

Amplitudinea este diferenta dintre maximul si minimul unui sir. Ne arata cat de "raspandite" sau "variabile" sunt valorile din sir. O amplitudine mare inseamna valori foarte diferite, iar o amplitudine mica inseamna valori apropiate.

Amplitudinea este un indicator statistic important. In meteorologie, amplitudinea termica zilnica (diferenta dintre temperatura maxima si minima a zilei) ne arata cat de mult variaza temperatura. O amplitudine de 5 grade inseamna o zi stabila, iar o amplitudine de 20 de grade inseamna diferente mari intre zi si noapte.

Amplitudinea se calculeaza dupa ce am gasit maximul si minimul. Deci algoritmul complet este: parcurgem sirul pentru a gasi maxim si minim (intr-o singura parcurgere), apoi calculam amplitudinea ca maxim - minim. Rezultatul este intotdeauna un numar pozitiv sau zero (zero doar daca toate elementele sunt egale).

In sport, amplitudinea scorurilor unui jucator (diferenta dintre cel mai bun meci si cel mai slab meci) ne arata cat de constant este: o amplitudine mica inseamna un jucator stabil, iar o amplitudine mare inseamna un jucator imprevizibil. La fel, amplitudinea notelor unui elev (diferenta dintre cea mai mare nota si cea mai mica nota) ne spune daca elevul este constant sau are rezultate foarte variabile.

La fel ca la suma si media, putem cauta maximul sau minimul doar printre elementele care indeplinesc o anumita conditie. De exemplu: care este cel mai mare numar par din sir? Care este cel mai mic numar pozitiv? Aceasta combina algoritmul de maxim/minim cu o conditie de filtrare.

Pasul 1 — problema initializarii. Pana acum am initializat maximul cu v[1] (primul element). Dar acum vrem doar elementele pare. Ce facem daca v[1] este impar? Nu putem folosi v[1] ca punct de start, pentru ca el nu indeplineste conditia noastra. Avem nevoie de o alta strategie.

Pasul 2 — ideea fanionului. Gandeste-te la un fanion (steag) care semnalizeaza daca am gasit sau nu primul element care ne intereseaza. Initializam variabila gasit cu 0 (nu am gasit inca niciun element par). Cand gasim primul element par, ridicam fanionul: gasit = 1. Orice al doilea, al treilea element par se compara normal cu maximul curent.

Pasul 3 — logica completa in doua ramuri. La fiecare element par din sir avem exact doua situatii posibile: fie gasit = 0 (e primul par — il punem direct ca maxim_par), fie gasit = 1 (mai avem cel putin un par deja — comparam cu maxim_par si pastram cel mai mare). Aceasta este toata complexitatea: doua situatii, doua ramuri DACA-ALTFEL.

Algoritmul este mai complex deoarece nu putem initializa max_par cu v[1] - ce se intampla daca v[1] nu este par? Am initializa cu o valoare care nu indeplineste conditia! De aceea, folosim variabila gasit (fanion): cand gasim primul element par, il retinem ca maxim initial. Pentru urmatoarele elemente pare, aplicam comparatia normala.

La final, trebuie sa verificam daca gasit este 1. Daca ramane 0, inseamna ca nu exista niciun element par in sir si nu putem afisa un maxim. Aceasta verificare este la fel de importanta ca verificarea contor>0 la media cu conditie - protejeaza algoritmul impotriva situatiilor imposibile.

Acesta este unul dintre cei mai complexi algoritmi pe care i-ai invatat pana acum, deoarece combina trei concepte: parcurgerea, conditia de filtrare si gasirea maximului. Exerseaza-l pe mai multe exemple pentru a-l stapani.

Sa recapitulam toate regulile si tiparele invatate in aceasta lectie. Algoritmii de maxim si minim sunt fundamentali si ii vei folosi in combinatie cu suma, media si parcurgerea in lectia urmatoare (proiectul final).

Algoritmii de baza:

Regulile de aur:

• Maximul si minimul se initializeaza cu v[1] , niciodata cu 0
• Pozitia (poz_max, poz_min) se initializeaza cu 1
• Conditia pentru maxim: v[i] > maxim
• Conditia pentru minim: v[i] < minim
• Maxim si minim se pot calcula in aceeasi parcurgere
• La maxim/minim cu conditie, folosim variabila fanion (gasit)

Observa tiparul comun: toti algoritmii au o initializare (inainte de bucla), o parcurgere (bucla FOR) si o operatie (in interiorul buclei). Diferenta este doar in valoarea de initializare si in operatia efectuata. Aceasta uniformitate face algoritmii usor de invatat si de combinat.

In lectia urmatoare (proiectul final), vei combina toti acesti algoritmi intr-un singur program care analizeaza complet un sir de numere: citire, afisare, suma, media, maxim, minim, amplitudine si clasificare. Va fi momentul in care tot ce ai invatat in acest modul se leaga intr-un intreg coerent!