Maximul/minimul unui număr fix de valori

Pentru a determina maximul a două valori trebuie să facem o comparație. Pentru a determina maximului a trei, patru sau mai multe valori va trebui să realizăm mai multe comparații. Scopul acestui articol este să clarifice modul de determinare a maximului/minimului unui număr fix de valori cu cât mai puține comparații.

Să presupunem că dorim să determinăm maximul valorilor a trei variabile: n, m și p. Evident, o singură comparație nu este suficientă! Putem scrie mai multe variante de program C++ care să determine maximul lor. Iată una dintre ele:

#include <iostream>
using namespace std;
int main(){
    int n , m, p;
    cin >> n >> m >> p;
    if(m > n)
        if(m > p)
            cout << m;
        else
            cout << p;
    else
        if(n > p)
            cout << n;
        else
            cout << p;
    return 0;
}

Programul de mai sus rezolvă problema dată, dar face 3 comparații. Nu pare mult, dar pentru a determina cu aceeași idee maximul a patru valori vom avea nevoie de 7 comparații, iar pentru 5 valori vom face 15 comparații, ceea ce devine complicat, iar riscul de a greși editarea programului este foarte mare!

Secretul stă în faptul că nu trebui să știm care dintre cele trei variabile (m, n sau p) este maximul, ci doar valoarea maximului. Putem folosi următoarea variantă:

#include <iostream>
using namespace std;
int main(){
    int m , n , p;
    cin >> m >> n >> p;
    int max;
    max = m;
    if(n > max)
        max = n;
    if(p > max)
        max = p;
    cout << max;
    return 0;
}

În programul de mai sus s-au făcut numai două comparații. Dezavantajul, nesemnificativ de altfel, este că nu mai știm care dintre cele trei variabile are valoarea mai mare.

Calculul maximului/minimului a 4 variabile devin banal. Pur și simplu mai facem o comparație, cu a patra valoare.

Programul următor determină minimul a patru numere naturale. Mai mult, evită folosirea a patru variabile. Procedăm astfel:

• citim prima valoarea pentru x
• inițializăm max cu valoarea lui x
• de trei ori:
  • citim valoarea lui x
  • comparăm pe x cu max, și, dacă este cazul, actualizăm valoarea lui max.

#include <iostream>
using namespace std;
int main(){
    int max;
    int x;
    cin >> x;
    max = x;
    cin >> x;
    if(x > max)
        max = x;
    cin >> x;
    if(x > max)
        max = x;
    cin >> x;
    if(x > max)
        max = x;
    cout << max;
    return 0;
}

Programul de mai sus este echivalent cu următorul, mai scurt:

#include <iostream>
using namespace std;
int main(){
    int max;
    int x;
    cin >> x; max = x;
    for(int i =1 ; i <= 3 ; i ++)
    {
        cin >> x;
        if(x > max)
            max = x;
    }
    cout << max;
    return 0;
}