Maxime și minime / Maximul/minimul pentru un număr oarecare de valori


Editat de Candale Silviu (silviu) la data 2015-08-17

Dacă numărul de valori nu este constant, pentru a determina maximul sau minimul lor trebuie să folosim o structură repetitivă. Alegerea ei se face după cum este cunoscut sau nu numărul de valori care se prelucrează (cunoscut, nu constant !!):

  • dacă se cunoaște numărul de valori de la început, putem folosi instrucțiunea for: vezi problemele #n_maxim, #n_minim, #SumMaxMin, etc
  • dacă numărul de valori nu se cunoaște de la început, putem folosi instrucțiunea while: vezi #Maxim

Să rezolvăm următoarea problemă: Se dau n numere întregi. Calculaţi cel mai mic dintre cele n numere date.

Numărul de valori se cunoaște de la început. Algoritmul de rezolvare va fi:

  • inițializăm variabila min corespunzător
  • citim cele n numere
    • fiecare număr se compară cu min și dacă este cazul se actualizează min

Cu ce valoare putem inițializa min? Distingem două posibilități:

  • inițializăm min cu prima dintre cele n valori; celelalalte n-1 valori se vor compara cu min
  • inițializăm min cu o valoare foarte mare; fiecare dintre cele n valori citite se va compara cu min. Alegerea valorii inițiale a lui min depinde de restricțiile problemei; pentru problema #n_minim poate fi 1.000.000.000.

În secvențele care urmează, n este numărul de valori citite, în x se citesc pe rând valorile iar în min vom determina valoarea minimă:

Inițializare cu prima valoare
cin >> n >> x;
min = x;
for(int i =1 ; i < n ; i ++)
{
    cin >> x;
    if(x < min)
        min = x;
}

Inițializare cu o valoare mare
cin >> n;
min = 1<<30; //2^30 > 1000000000
for(int i =1 ; i <= n ; i ++)
{
    cin >> x;
    if(x < min)
        min = x;
}

Să rezolvăm următoarea problemă: Se citesc numere întregi până la apariția lui 0, care nu se ia în considerare. Calculaţi minimul lor.

Numărul de valori nu se cunoaște de la început. Algoritmul de rezolvare va fi:

  • inițializăm variabila min corespunzător
  • citim un număr în x
  • cât timp x este nenul
    • x se compară cu min și dacă este cazul se actualizează min
    • citim altă valoare pentru x

Și aici este semnificativă inițializarea variabilei min. Secvențele de mai jos surprind ambele situații:

Inițializare cu prima valoare
cin >> x;
min = x;
cin >> x;
while(x != 0)
{
    if(x < min)
        min = x;
    cin >> x;
}

Inițializare cu o valoare mare
min = 1<<30; //2^30 > 1000000000
cin >> x;
while(x != 0)
{
    if(x < min)
        min = x;
    cin >> x;
}

Problemă: Se dau n numere întregi. Să se determine valoarea minimă și de câte ori apare printre cele n numere.

Rezolvare:

  • fie min valoarea minimă și nr_min numărul de apariții ale valorii minime
  • citim n și primul dintre cele n numere, x
  • inițializăm min cu x și nr_min cu 1 – minimul a apăru o singură dată până acum
  • citim pe rând cele n-1 valori rămase în variabila x
    • dacă x < min, actuatalizăm min cu x și nr_min cu 1
    • dacă nu, verificăm dacă x == min. În caz afirmativ, îl incrementăm pe nr_min.

Problemă: Se citesc numere întregi, mai mici decât 1.000.000.000 până la apariția lui 0, care nu se ia în considerare. Să se determine cele mai mici două numere dintre ele.

Rezolvare:

  • fie min1 cel mai mic număr și min2 următorul cel mai mic număr
  • inițializăm min1 și min2 cu două valori mari, astfel: min1 = 1000000001, min2 = 1000000002
  • citim un număr x
  • cât timp x != 0
    • prelucrăm pe x; se disting cazurile:
      • x < min1: se actualizează ambele minime, astfel: min2 devine min1, iar min1 devine x
      • x >= min1, dar x < min2: se actualizează numai min2, min2 = x
    • citim următoarea valoare pentru x

Fișiere atașate


Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #0354 - n_maxim 9 ușoară consola
2 #0357 - Perechi1 9 medie consola
3 #0172 - difMin 9 medie consola
4 #0274 - 3minime 9 medie consola
5 #0119 - 2maxim 9 medie consola
6 #0346 - MaxAndAp 9 ușoară consola
7 #0054 - Maxim 9 ușoară consola
8 #0347 - SumMaxMin 9 ușoară consola
9 #0355 - n_minim 9 ușoară consola
10 #0358 - Plopi 9 medie consola

Vezi și: