Trovare il maggiore e il secondo maggiore

Dato un vettore numerico di N posizioni caricato in memoria trovare il maggiore e il secondo maggiore, cioè determinare il valore più grande e quello immediatamente inferiore (il secondo), indicandone l’indice.

Per realizzare questo algoritmo occorre come al solito chiedere N e fare un controllo dell’input in modo da accettare solo valori maggiori o uguali a zero.

Dopo dichiariamo il vettore e con un ciclo for inseriamo tutti gli elementi.

Creiamo una variabile max per contenere il valore massimo dell’array e una variabile max2 per l’elemento immediatamente inferiore.

Dopo creiamo anche le variabili p e p2 che tengono traccia delle posizioni dei due valori che vogliamo trovare.

Inizializziamo poi che sia max che max2 al primo elemento dell’array e le due variabili p e p2 a 0, cioè all’indice del primo elemento dell’array.

Poi con un ciclo for scorriamo l’array e controlliamo se il valore contenuto nell’elemento a[i] è maggiore del massimo. Se è vero prima di scambiare il valore massimo assegniamo a max2 il valore di max e all’indice p2 il valore di p.

Questo perché qualunque valore contenesse max2 era comunque inferiore al max. Infatti se si trova un nuovo massimo comunque il vecchio massimo sarà maggiore del valore contenuto in max2.

Se invece a[i] non è maggiore del massimo, occorre con un altro if controllare se questo valore è maggiore di max2.

Funzionamento algoritmo per trovare il maggiore e il secondo maggiore

Dunque ipotizziamo di avere questo array:

max = a[0] = 6 e max2 = a[0] = 6

p = 0 e p2 = 0 cioè sono entrambi inizializzati al primo indice.

Prima iterazione: a[1] = 6

si valuta la condizione dell’if: a[1] > max cioè 12 > 6

L’espressione risulta vera allora possiamo eseguire le operazioni specificate all’interno dell’if e cioè:

max2 = max = 6 e p2 = 0  (in questo caso non cambia il valore precedentemente assegnato a max2).

Poi si avrà max = a[1] = 12

e si aggiorna anche p: p = 1

L’else if quindi non viene eseguita

Seconda iterazione: a[2] = 10

si valuta la condizione dell’if: a[2] > max cioè 10 > 12

L’espressione risulta falsa allora si valuta l’istruzione else if.

L’espressione else if risulta vera quindi:

max2 = a[2] = 10 e p2 = 2

Terza iterazione: a[3] = 23

si valuta la condizione dell’if: a[3] > max cioè 23 >12

L’espressione risulta vera allora possiamo eseguire le operazioni specificate all’interno dell’if e cioè:

max2 = max = 12 e p2 = p = 1

Poi si avrà max = a[3] = 23

e si aggiorna anche p: p = 3

L’else if quindi non viene eseguita.

Abbiamo terminato ottenendo:

max = 23 e p = 3

max2 = 12 e p2 = 1

 

Ecco quindi l’algoritmo per trovare il maggiore e il secondo maggiore in C++

#include <iostream>

using namespace std;

int main() {
    int N, max, max2, p, p2;
    
    do {
        cout << "Inserisci N: ";
        cin >> N;
    } while (N <= 0);
    
    int a[N];
    
    for (int i = 0; i < N; i++) {
        cout << "Inserisci un numero: ";
        cin >> a[i];
    }
    
    max = a[0];
    max2 = a[0];
    p = 0;
    p2 = 0;
    
    for (int i = 1; i < N; i++) {
        if (a[i] > max) {
            max2 = max;
            p2 = p;
            max = a[i];
            p = i;
        } else if (a[i] > max2) {
            max2 = a[i];
            p2 = i;
        }
        
        cout << max;
    }
    
    cout << "\nIndice: " << p << "\tvalore: " << max;
    cout << "\nIndice: " << p2 << "\tvalore: " << max2;
    
    return 0;
}

Si può anche ottimizzare in questo modo:

for (int i = 1; i < N; i++) {
    if (a[i] > max2) {
        if (a[i] > max) {
            max2 = max;
            p2 = p;
            max = a[i];
            p = i;
        } else {
            max2 = a[i];
            p2 = i;
        }
    }
}

Difatti se il primo test è falso possiamo proseguire senza fare altro.

Alcuni link utili

Indice argomenti linguaggio C++

Array o vettori in C++

Approfondimento vettori in C++

Esercitazione sugli array in C++

Massimo elemento di un vettore

Esercizi con gli array

Ricerca sequenziale in C++

Ricerca in un array ordinato

Array con numeri random

Ricerca binaria