Minim, maxim și poziții în vector la BAC: C++

Minimul și maximul unui vector se determină comparând pe rând fiecare element cu cel mai bun rezultat găsit până atunci. Dacă trebuie să afișezi și pozițiile, păstrezi separat valoarea extremă și indicele ei. La BAC, cele mai importante capcane sunt inițializarea, valorile negative și alegerea primei sau ultimei apariții.

Vom lucra cu un vector nevid, cu cel mult o mie de numere întregi. În memorie, indicii încep de la zero, dar pozițiile afișate vor fi numerotate de la unu. Această convenție va rămâne aceeași în exemple și în program, așa cum trebuie să procedezi și în rezolvările de BAC.

Inițializarea cu primul element

Pentru un șir nevid, primul element este atât minimul, cât și maximul prefixului format doar din el. De aceea, o inițializare naturală pune ambele extreme la valoarea primului element și ambele poziții la indicele zero.

Inițializarea maximului cu zero este greșită dacă toate valorile pot fi negative. Pentru șirul minus opt, minus trei și minus cinci, maximul este minus trei. Zero nu apare în șir și nu trebuie să fie afișat doar fiindcă toate comparațiile cu el au eșuat.

În mod asemănător, inițializarea minimului cu zero este greșită pentru un șir cu toate valorile strict pozitive. O constantă foarte mare sau foarte mică poate funcționa numai dacă este aleasă justificat din domeniul datelor. Primul element evită această dependență pentru șirurile nevide.

Exemplu urmărit pas cu pas

Considerăm vectorul șapte, minus doi, nouă, minus doi, nouă și patru. Căutăm minimul și maximul, împreună cu prima poziție la care apare fiecare.

Poziție citită	Valoare	Minim și prima poziție	Maxim și prima poziție
1	7	7 la poziția 1	7 la poziția 1
2	-2	-2 la poziția 2	7 la poziția 1
3	9	-2 la poziția 2	9 la poziția 3
4	-2	-2 la poziția 2	9 la poziția 3
5	9	-2 la poziția 2	9 la poziția 3
6	4	-2 la poziția 2	9 la poziția 3

La egalitate, poziția rămâne neschimbată. Astfel păstrăm prima apariție. Dacă am actualiza și când valoarea curentă este egală cu extrema, poziția ar avansa la ultima apariție întâlnită.

Valoarea și poziția trebuie actualizate împreună

Când găsești un nou minim, schimbi atât valoarea minimului, cât și poziția lui. Dacă actualizezi doar valoarea, poziția poate rămâne asociată unui element vechi. Programul va afișa două informații care nu se mai potrivesc.

O verificare simplă este să controlezi la final că elementul de pe poziția reținută are chiar valoarea extremei. Această condiție nu dovedește singură că extrema este corectă, dar descoperă o categorie importantă de erori de sincronizare.

Poți păstra și numai indicele extremei, comparând valorile prin tablou. Atunci valoarea se obține accesând elementul de la indicele reținut. Ambele variante sunt corecte dacă menții consecvent semnificația variabilelor.

Program C++ complet

Programul afișează pe prima linie minimul și prima lui poziție, iar pe a doua linie maximul și prima lui poziție. Datele respectă limita de capacitate a tabloului și condiția că există cel puțin un element.

#include <iostream>
using namespace std;

int main() {
    int n, v[1000];
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> v[i];

    int minim = v[0], maxim = v[0];
    int pmin = 0, pmax = 0;
    for (int i = 1; i < n; ++i) {
        if (v[i] < minim) {
            minim = v[i];
            pmin = i;
        }
        if (v[i] > maxim) {
            maxim = v[i];
            pmax = i;
        }
    }
    cout << minim << ' ' << pmin + 1 << '\n';
    cout << maxim << ' ' << pmax + 1;
    return 0;
}

Bucla începe de la al doilea element, deoarece primul a fost deja folosit la inițializare. Pentru un singur element, bucla nu se execută. Minimul și maximul sunt acel element, ambele la poziția unu.

Cele două condiții sunt scrise independent pentru claritate. Fiecare exprimă o proprietate diferită. Parcurgerea are timp liniar, iar variabilele pentru extreme ocupă memorie constantă în plus față de tabloul citit.

Prima apariție, ultima apariție sau toate aparițiile

Pentru prima apariție a minimului, actualizezi doar când găsești o valoare strict mai mică. Pentru ultima apariție, actualizezi când găsești o valoare mai mică sau egală. La maxim, comparațiile se schimbă în direcția corespunzătoare.

Dacă se cer toate pozițiile minimului, o metodă simplă are două parcurgeri. În prima determini valoarea minimă. În a doua afișezi fiecare poziție al cărei element este egal cu ea. Timpul rămâne liniar, deoarece aduni două parcurgeri de aceeași lungime.

Nu afișa imediat toate pozițiile care egalează minimul provizoriu fără o strategie de corectare. Mai târziu poate apărea un minim mai mic, iar pozițiile deja afișate nu mai sunt răspunsuri valide. Afișarea este dificil de retras; calcularea completă a extremei înainte de listarea pozițiilor rezolvă problema.

Numărul aparițiilor extremei

Poți număra aparițiile minimului în aceeași parcurgere. Contorul pornește de la unu pentru primul element. Când apare un minim strict mai mic, schimbi minimul și resetezi contorul la unu. Când apare o valoare egală cu minimul curent, mărești contorul.

Resetarea este esențială. Pentru șirul cinci, cinci, doi, doi, doi, primele două valori ar da temporar două apariții ale minimului cinci. Când apare doi, numărătoarea pentru cinci nu mai are relevanță și trebuie înlocuită, nu continuată.

În această variantă, ordinea ramurilor trebuie să împiedice numărarea de două ori a unui minim nou. După resetare, nu mai aplici încă o dată și ramura de egalitate pentru același element. O structură cu ramuri exclusive exprimă clar această intenție.

Extreme doar dintre elementele care respectă o condiție

Dacă se cere minimul valorilor pozitive, primul element al vectorului nu este neapărat un candidat valid. Ai nevoie de o inițializare cu primul element care îndeplinește condiția sau de un indicator care arată dacă ai găsit deja un candidat.

În lipsa valorilor pozitive, trebuie afișat mesajul sau rezultatul cerut de enunț. Nu inventa un minim zero și nu presupune existența lui dacă problema nu o garantează. Domeniul selecției poate fi gol chiar dacă vectorul însuși este nevid.

Această diferență între șirul complet și submulțimea candidaților este un bun exercițiu de înțelegere a algoritmului. Inițializarea rezultă din ceea ce cauți, nu dintr-o rețetă aplicată mecanic.

Exerciții cu răspunsuri explicate

Pentru minus șapte, minus unu, minus patru, minimul este minus șapte la poziția unu, iar maximul este minus unu la poziția a doua. Testul verifică dacă ai folosit incorect zero la inițializare.

Pentru trei, trei, trei, prima poziție a ambelor extreme este unu, iar ultima este trei. Valoarea minimă și cea maximă coincid. Cerința despre apariții decide ce poziție afișezi.

Pentru opt, doi, cinci, doi, minimul este doi și apare de două ori. Toate pozițiile lui sunt a doua și a patra. Prima parcurgere găsește valoarea, iar a doua poate lista pozițiile în ordine.

Pentru zero, minus doi, minus cinci, nu există un minim al valorilor strict pozitive, fiindcă nu există asemenea valori. Dacă enunțul cere tratarea absenței, acest caz trebuie recunoscut explicit.

Întrebări frecvente

De ce adaug unu la poziție doar la afișare?

În program folosim indici de la zero. Adăugarea lui unu transformă indicele în poziția cerută, fără să schimbe convenția internă a accesărilor. Nu adăuga unu și când accesezi elementul corespunzător.

Trebuie neapărat să memorez vectorul?

Nu pentru determinarea unei extreme și a primei poziții. Poți prelucra valorile la citire. Tabloul este util dacă trebuie să revii asupra elementelor, de exemplu pentru afișarea tuturor pozițiilor după calcul.

Ce teste sunt obligatorii în verificarea mea?

Folosește un singur element, toate valori egale, toate negative și o extremă repetată. Pentru cerințe cu selecție, adaugă și absența candidaților. Poți verifica împreună aceste cazuri la meditații de informatică.