Esercizio sugli algoritmi

Esercizio proposto alla classe IIIA liceo tecnico il 12 novembre 2008

Enunciato del problema Si vuole stampare il

nome delle città il cui numero di abitanti sia compreso tra 10.000 e 100.000

Queste informazioni sono su di una lista cartacea sottoforma di tabella

Città Numero Abitanti

Perugia 170000

Pisa 90000

Milano 3000000

Roma 4000000

Firenze 400000

Lucca 85000

Torgiano 6000

Marsciano 17000

Magione 12300

Ragionamento mentale1. Esaminiamo per ogni città il numero dei suoi

abitanti2. Se questo numero risulta compreso tra

10000 e 100000 3. scriviamo il nome di questa città ed il

numero dei suoi abitanti4. Ripetiamo le istruzioni ricominciando dalla

prima attività finchè non abbiamo esaurito tutte le righe della lista.

Gli elementi del ragionamento dal punto di vista del computer Leggiamo una alla volta le righe della lista Quindi ci occorrono due celle di memoria (due variabili), una per

memorizzare il nome della città ed un’altra per memorizzare il suo numero di abitanti Città Abitanti

Ci occorrono quindi due istruzioni di lettura ossia di input Ci dobbiamo porre due domande sul numero degli abitanti

abitanti maggiore di 10000 ? abitanti minori di 100000 ?

Ci occorrono quindi due costrutti di alternativa Quando la risposta è positiva ad entrambe le domande stampiamo

il nome della città ed il numero dei suoi abitanti Istruzione di output

In tutti i casi ripetiamo questa sequenza di istruzioni finchè ci sono città da esaminare

Pertanto c’è un costrutto di iterazione

Primo tentativo di soluzione Questa soluzione

correttamente legge esamina gli abitanti di una città per verificare se sono soddisfatte le due condizioni richieste dal problema e quando la risposta è positiva stampa i dati richiesti.

Tuttavia c’è un errore grave. Appena si trova la prima città che soddisfa le condizioni e la si stampa si finisce anche il lavoro.

Invece bisogna ripetere ancora le istruzioni per esaminare le altre città

Con questa soluzione si stampa solo la prima città con il numero di abitanti compreso tra diecimila e centomila.

Vediamo la correzione di questo errore

Secondo tentativo di soluzione Con questa soluzione

si risolve il problema precedente, ma…

E’ vero che adesso c’è la giusta ripetizione delle istruzioni per poter esaminare tutte le città, tuttavia manca la fine !

Manca un meccanismo che consenta l’uscita dalla iterazione.

Come si risolve questo ulteriore problema ?

Terzo tentativo di soluzione Adesso la soluzione può

anche andare da un punto di vista logico.

Abbiamo l’iterazione ed anche un meccanismo che ci consente di uscire da essa.

Tuttavia la domanda “hai esaminato tutte le città dell’elenco” non è comprensibile da parte del computer.

Il computer può fare operazioni aritmetiche e operazioni logiche di confronto tra due variabili

Quante volte devo ripetere l’esame delle città Se ho un elenco e conosco

il numero R delle sue righe, questo numero mi dice quante volte devo ripetere il blocco di istruzioni che esaminano gli abitanti di una città

Pertanto ogni qual volta eseguo questo blocco di istruzioni posso incrementare un contatore di uno e confrontare il suo valore con quello R delle righe dell’elenco.

Finchè il valore del contatore sarà inferiore a R ripeterò il lavoro altrimenti uscirò dall’iterazione!

Soluzione finale Questa soluzione è

quella migliore per motivi ancora da spiegare.

Per il momento diciamo semplicemente che il flowchart si presta ad essere tradotto nella programmazione strutturata

Comunque si vede anche ad occhio che questo disegno è più comprensibile del precedente

Fine di questo esercizio