Eserciziosuglialgoritmi Max

Trovare il numero più grandeLezione del 26 novembre 2008

Prof. Silvano Natalizi

Risolvere il seguente problema

trovare il numero massimo tra una lista di numeri interi e positivi.

Ragionamento mentale intuitivoConfronto i numeri tra di essi.Il confronto è un’operazione di disuguaglianza

(maggiore o minore).Da questa operazione di confronto stabilisco quale è il

maggiore.Quando faccio il confronto vedo (proprio con la vista)

simultaneamente molti numeri e quindi scelgo il maggiore tra di essi, gli altri li scarto perché già li ho usati.

Continuo a confrontare il numero massimo precedentemente scelto con i numeri rimanenti.

Nuovamente, servendomi della vista e dell’operazione di disuguaglianza scelgo il numero più grande

Quando ho esaminato tutti i numeri dati, ho la risposta al problema, ossia il numero più grande selezionato.

Lista di numeriHo una lista di numeri

Per determinare il numero più grande, ne prendo un po’ alla volta e…

1334651138020

Confronto i numeriScelgo il più grande tra quelli che vedo

40100

13

45133465

Scelgo il numero più grandeIn questo caso focalizzo l’attenzione sul

numero 100 che è il maggiore, gli altri tre numeri li posso togliere

133465

100

Confronto il numero più grande con gli altri numeriGuardo i numeri rimanenti e li confronto con il

numero 100, maggiore tra i numeri precedenti:

Si vede che il numero maggiore è 200!

100

25 80

200120

Dobbiamo trasformare il precedente ragionamento mentale per adattarlo al computer invece di confrontare tante cose insieme, ne

confrontiamo solo due alla volta. Scopro il primo numero.

Dal momento che è il primo non posso confrontarlo con nessun numero precedente, pertanto assumo che sia il maggiore.

3465113804013 100

Continuo a confrontare il numero scelto come maggiore con un altro numero della lista Scopro il successivo numero e lo confronto

con il numero maggiore

Scelgo il numero maggiore tra i due e non mi interesso più di quello minore

3465113804013

100

Continuo a confrontare il numero scelto come maggiore con un altro numero della listaConfronto il numero maggiore con il

successivo numero della lista

Scelgo il maggiore dei due e scarto il minore

346511345

40

100




3465125

45

100




346580

25

100




65120

80

100




200

120

100




200

120

Non ci sono altri numeri della lista per cui ho terminato il lavoro di confronto tra i numeri. L’unico numero rimasto è il numero

maggiore 200

Questo numero è il risultato del problema.

200

Le variabiliDal momento che confronto due cose tra di

loro, per far fare questo lavoro al computer ho bisogno di due celle di memoria, ossia di due variabili

Nella prima variabile memorizzo il numero correntemente letto

Nella seconda variabile memorizzo la scelta del numero maggiore

I nomi delle variabiliOgni variabile deve avere un tipo datoOgni variabile deve avere un nomeIn questo caso le due variabili sono

entrambre di tipo int (numero intero)I nomi sono una scelta del programmatorechiamiamo

numero (il numero correntemente letto)massimo (il numero scelto massimo)

L’operazione di confrontoL’operazione di confronto la facciamo tra le

due variabili precedentemente definite (numero, massimo)

numero>massimo

Che cosa dobbiamo fare ?Se (numero>massimo) è vero, il numero corrente

è maggiore del numero massimo (massimo tra tutti quelli precedentemente letti); pertanto devo sostituire il valore di massimo con il nuovo numero

Eseguo questa sostituzione assegnando numero a massimo con l’operatore =

numero>massimo

V

massimo=numero

Il lavoro precedente va ripetuto tante volte per quanti sono i numeri della lista“L’operazione di confronto e quando la sua

condizione è verificata l’assegnazione del numero corrente al massimo “ va ripetuta tante volte per quanti sono i numeri della lista

Occorre pertanto una struttura di controllo iterativa di tipo numerata.

La prima cosa da disegnare è la struttura iterativa numerataIl disegno della struttura iterativa non è una

difficoltà di natura concettuale, perché tutte le strutture di controllo sono dei componenti standard.

L’iterazione numerata ha come elementi:Un tipo: crescente o decrescenteUna variabile di controlloUn valore inizialeUn valore finaleUn incremento

La struttura di controllo iterativa numerata

La struttura di selezione all’interno dell’iterazione

Prima della selezione devo inserire la lettura del numero

Infine azzeriamo la variabile “massimo” prima dell’iterazione

Osservazione finale Nella prima iterazione

confrontiamo il primo numero con il valore zero di massimo

Questo algoritmo funziona se i numeri sono maggiori di zero.

Se avessimo numeri anche negativi dovremmo modificare la parte iniziale del flowchart: Leggiamo il primo numero

con l’istruzione di “leggi numero” inserita prima dell’iterazione

e come seconda istruzione assegniamo a massimo numero, sempre prima di entrare nell’iterazione

Per stampare il risultato inserisco la stampa dopo l’iterazione

Ultimo aggiustamentoNel precedente flowchart ho effettuato

l’operazione di lettura dei numeri 9 volte ! Una prima della iterazione, 8 volte dentro l’iterazione. Se i numero sono 8, ho commesso un errore.

Per correggere l’errore è sufficiente modificare la condizione di controllo dell’iterazione da i<=8 a i<8.

Eserciziosuglialgoritmi Max

Education

Transcript of Eserciziosuglialgoritmi Max