Ricerca del valore massimo in una sequenza (array) di interi



E’ il primo post che scrivo su questo sito e vorrei iniziare a proporvi piccoli problemi di informatica che molti studenti non riescono a trovare su internet.

La ricerca del valore massimo:

La ricerca di un valore massimo (e di conseguenza di un valore minimo) di una sequenza di numeri è uno dei primi problemi che un informatico si trova a dover risolvere.

Il concetto è semplice:

si prende un valore X e supponiamo che questo sia il massimo. X deve avere il valore di uno dei numeri della sequenza.. per semplicità prendiamo il primo.

Ora quello che dovremo fare è confrontare questo X (e non il primo elemento) con gli altri elementi.

Se assegnamo ad X il valore del primo elemento ovviamente sarebbe inutile confrontare X anche col primo elemento. Faremmo solo un operazione in più che sarebbe inutile. E’ vero che non fondiamo il computer con una sola operazione in più ma, QUANDO E’ POSSIBILE, è meglio trovare le operazioni inutili ed eliminarle.

Per adesso lasciamo perdere questo e torniamo alla ricerca del massimo.

Quindi, ogni volta che confronteremo X con ogni numero ci comporteremo così:

Se X è minore del numero messo a confronto, allora X non può essere sicuramente il MASSIMO (è già minore di uno dei numeri).

Quindi possiamo supporre che il numero massimo possa essere quello che abbiamo appena confrontato. Di conseguenza assegnamo ad X il valore di questo numero.

OVVIAMENTE se X è maggiore o uguale al numero messo a confronto passiamo avanti senza far niente.

Facciamo un esempio:

Prendiamo la sequenza A: [1,30,4,206,0,-1000,73]

Ogni numero (anche se preferisco chiamarli elementi) è separato da una virgola.

Ora prendiamo un valore X uguale al primo elemento.

Quindi X=A[0].

(Gli elementi vanno da 0 a n-1, con “n” il numero degli elementi della sequenza. Quindi in questo caso n=7 e gli elementi vanno dal primo che è A[0] all’ultimo che è A[6]..

Per essere ancora più chiari:

A: [ A[0], A[1], A[2], A[3], A[4], A[5], A[6] ] )

Iniziamo a confrontare X con il secondo elemento.

Abbiamo detto che se X<A[1] allora X non può essere il valore del numero massimo contenuto nella sequenza, però possiamo supporre che lo sia il valore di A[1].

In questo caso aggiorniamo X assegnandogli A[1].

Quindi d’ora in avanti X=A[1]. se invece X>A[1] o X==A[1] passiamo avanti senza far niente.

Vediamo sulla nostra sequenza:

A: [1,30,4,206,0,-1000,73]

X=1 e A[1]=30. X<A[1] è vero poichè 1 è minore di 30.

Allora possiamo assegnare il valore di A[1] ad X e continuare il confronto con gli altri elementi.

Potremmo scrivere così:

– Sia A una sequenza di numeri interi e N un numero intero, con N il numero degli elementi della sequenza;

– Sia X un intero, con X=A[0];

– Sia i un intero, con i=0;

– Fin quando i<N è vero:

– Se X<A[i] allora: X=A[i] e incrementa i di 1;

– Se X>=A[i] allora non fare niente; (operazione inutile, ma giusto per capire che è ovvio che

il massimo può essere maggiore o uguale al numero trovato dato che è il massimo)

– Quando i>=N determina il valore di X come valore massimo tra gli elementi della sequenza.

Ho usato i come contatore per evitare di scrivere ogni volta A[0], A[1], ecc.

Dato che all’inizio i=0 A[i] sarà come scrivere A[0]… se vado avanti e scrivo A[i] con i incrementato di 1, quindi i=0+1 e quindi i=1, A[i] sarà come scrivere A[1] e così via…

Se arrivo a i=7, dato che ho detto fin quando i<N, con N=7 nel nostro caso, 7<7 è falso (perchè 7 è UGUALE a 7) quindi quello che faccio nel “Fin quando” non lo posso più fare.

Infatti sotto ho scritto, per essere più specifico, Quando i>=N (maggiore o uguale), in questo caso è vero perchè 7 è uguale ma non maggiore e, dato che vale o uno o l’altro o tutti e due, questo, ripeto, risulta vero, determino il valore di X come il valore massimo tra gli elementi contenuti nella sequenza.

In C++ potremmo scrivere una cosa simile:

//INIZIO CODICE METODO

int max_value(int A[],int N)

{

int X=A[0];

int i=0;

while(i<n)

{

if(X<A[i]) X=A[i];

i++;   //COMMENTO: oppure “i=i+1;”, è uguale.

}

return X;

}

//FINE CODICE METODO

L’ho scritto come metodo e non ho fatto il main come molti fanno per semplicità, ma se è necessario posso aiutarvi anche per implementarlo in un programma.

Il concetto è lo stesso per il minimo. Solo che X cambia quando è MAGGIORE di A[i] e non cambia quando è MINORE o UGUALE.

Spero che questo articolo vi sia stato utile e se così fosse mi piacerebbe scrivere altri articoli per chiarire dubbi o aiutarvi in queste cose che molto spesso vengono date per scontate ma altrettanto spesso molti non riescono a capire subito o, semplicemente, non le hanno mai viste.

Oltre questo vi ringrazio per aver dedicato attenzione a questo articolo. Ho cercato di essere più chiaro possibile ma, se ci dovesse essere qualcosa di non chiaro fatemelo sapere.

Annunci sponsorizzati:

Ricerche effettuate:

  • trovare massimo di una sequenza c
Condividi su Facebook Condividi su Twitter!
  • D4n13le

    Un classico for con un banale if, senza troppi giri di parole che complicano la comprensone no? In ogni caso ti consiglio, sopratutto quando lo scopo è fare un prodotto disponibile a tutti, di usare nomi un po’ più esplicativi per le tue variabili.

    Un’altra cosa: verso l’inizio consigli di cominciare il confronto dal secondo elemento per guadagnare in tempo di esecuzione, ma poi non lo fai.

  • phab8x

    Hai ragione! Mentre scrivevo ero un po’ indaffarato a fare altro e avevo un po’ di gente intorno che faceva avanti e indietro.. e perciò ho dovuto lasciare per un po’ l’articolo e riprenderlo dimenticando questo particolare (in effetti ho specificato che non è qualcosa che appesantisce la macchina più di tanto ma è sempre meglio evitarlo). Ma in effetti non sono stato coerente ^_^’. Chiedo scusa ;) Anzi grazie per avermelo fatto notare.
    Per quanto riguarda il semplice for… So benissimo che è un semplice for ma molte persone non sanno perchè fare il for con l’if e quindi ho cercato di inserire nell’articolo tutti i chiarimenti possibili del perchè eseguire certi processi.
    Molte persone che conosco scrivono senza pensare. Poi quando devono usare un algoritmo del genere in problemi più complessi (magari utilizzando il massimo tra più sequenze o utilizzando gli oggetti) si perdono come niente ;)
    Ho preferito non usare nomi troppo complicati per le variabili per spiegare il concetto in modo più semplice.. ma in effetti ero in dubbio se usare nomi per le variabili o lettere.
    Comunque grazie ancora per il commento. Se avete consigli sul come migliorare l’articolo o se lo trovate poco comprensibile sono accetti tutti i tipi di consiglio ;)

  • phab8x

    Credevo si potesse aggiornare l’articolo modificandolo.
    Scusate sono un po’ alle prime armi su questo sito ;)

    L’aggiornamento che avrei voluto fare è:
    //INIZIO CODICE METODO

    int max_value(int A[],int N)

    {

    int X=A[0];

    int i=1; //Come dicevo prima, partiamo col confronto dal secondo elemento (Grazie D4n13le ;))

    while(i<n)

    {

    if(X<A[i]) X=A[i];

    i++; //COMMENTO: oppure “i=i+1;”, è uguale.

    }

    return X;

    }

    //FINE CODICE METODO

Pinterest