Problemi Con Scelte

Problemi con scelte Introduzione Al termine di questa lezione sarete in grado di:  risolvere semplici problemi che prevedono la possibilità di effettuare delle scelte, in base al verificarsi o meno di alcune condizioni;  rappresentare graficamente l’algoritmo risolutivo mediante diagrammi di flusso.

Un problema proposto Consideriamo il seguente problema: Dato un numero intero, stabilire se è divisibile per 2. Produrre in output il risultato (per esempio, "Il numero è divisibile per 2" o "Il numero non è divisibile per 2"). Risolviamo il problema attenendoci al seguente schema: 1. Analisi del problema mediante individuazione a. dei dati iniziali b. dei risultati attesi c. del procedimento risolutivo (algoritmo) 2. Formalizzazione dell’analisi (scrittura dell’algoritmo)

Analisi del problema a. Il dato iniziale è il numero intero, che chiameremo intero. b. Il risultato atteso è una stringa che ci dice se il numero è divisibile o meno per 2. c. Il problema può essere formulato anche in un altro modo. Chiedersi se un numero è divisibile per 2 equivale a domandarsi se è pari. La divisione di un numero pari per 2 restituisce sempre resto zero, mentre la divisione di un numero dispari per 2 restituisce sempre resto 1. Per trovare la soluzione dobbiamo quindi dividere il numero dato per 2 e controllare il resto ottenuto. Il procedimento risolutivo consiste nella seguente sequenza di passi: 1. acquisisco in input il numero, intero 2. divido intero per 2 e determino il resto 3. se resto è uguale a zero 4. allora produco in output la stringa “Il numero è divisibile per 2” 5. altrimenti produco in output la stringa “Il numero non è divisibile per 2” Formalizzazione dell’analisi ID intero resto

TABELLA DATI Descrizione I/O/L Il numero intero dato I Resto della divisione di L intero per 2

Tipo numero intero numero intero

Osservazione Come potete notare, nella tabella precedente è stata introdotta una variazione alla terza colonna: l’intestazione non contiene più le sole due voci input e output Autore: Bocchi Cinzia Ultimo aggiornamento: 05/10/2012

1

(I/O) ma anche una ulteriore voce L, che sta per lavoro. Fino ad ora abbiamo parlato solo di dati di input e di output. In realtà esiste un terzo tipo di dati che non sono acquisiti in input o prodotti in output, ma vengono utilizzati per contenere i risultati di elaborazioni intermedie. La variabile resto non viene acquisita in input (l’utente non conosce il resto) e non è richiesta in output (all’utente non interessa sapere il valore del resto ma solo se il numero dato è divisibile per 2). Di conseguenza, resto è una variabile di lavoro (o ausiliaria). E’ importante individuare le variabili di lavoro, distinguendole da quelle di I/O, perché una variabile di lavoro non sempre è necessaria e vedremo che talvolta è possibile eliminarla. La decisione di mantenere una o più variabili di lavoro è dettata dalla necessità di rendere il codice maggiormente “leggibile”. FLOW CHART Start

input(intero)

se resto è uguale a zero resto= resto divisione tra intero e 2

F

resto=0

output("Il numero non è divisibile per 2")

V

output("Il numero è divisibile per 2")

End

allora intero è divisibile per 2 altrimenti intero non è divisibile per 2

Osservazione Osservate che nel diagramma di flusso è presente un blocco contenente la descrizione di un’operazione non completamente specificata: resto= resto divisione tra intero e 2 Questo modo di procedere è perfettamente lecito, a patto che si vada a indicare, in un momento successivo, come si intende calcolare il resto della divisione tra intero e 2. Spesso capita di non riuscire a scendere al livello massimo di dettaglio durante la prima stesura dell’algoritmo, soprattutto quando il problema è complesso. Tutti i passaggi non dettagliati possono essere specificati meglio nei passaggi successivi (raffinamenti).

Raffinamento della soluzione Come calcolare il resto della divisione Possiamo agire in due modi diversi.

Autore: Bocchi Cinzia Ultimo aggiornamento: 05/10/2012

2

PRIMO MODO

Dividiamo il numero intero per due e calcoliamo la differenza tra il numero intero e il risultato della divisione (quoziente) moltiplicato per il divisore (2). Per esempio: intero quoziente (intero:2) resto (intero-quoziente*2)

10 5 0

intero quoziente (intero:2) resto (intero-quoziente*2)

11 5 1

A questo punto qualcuno potrebbe porsi la domanda: come mai la divisione tra 11 e 2 da come risultato 5 e non 5,5? La risposta è: perché stiamo eseguendo una divisione intera. Alcuni linguaggi di programmazione forniscono due diversi operatori, uno per la divisione intera e l’altro per la divisione non intera (per intenderci, quella che restituisce il risultato 5,5). Java, invece, ha un solo operatore per la divisione (“/”) e la distinzione tra divisione intera ed esatta dipende dal tipo del dividendo (intero) e del divisore (2). Quando dividendo e divisore sono entrambi interi, la divisione è sempre intera. SECONDO MODO

La maggior parte dei linguaggi di programmazione di ultima generazione forniscono uno speciale operatore, detto operatore modulo, che restituisce automaticamente il resto della divisione intera. Anche la rappresentazione adottata per tale operatore e quasi sempre la stessa: si usa il simbolo percentuale (“%”). Possiamo allora utilizzare tale simbolo all’interno del flowchart. FLOW CHART Start 1

input(intero)

2

resto= intero% 2

3 F

output("Il numero non è divisibile per 2")

resto=0

5

V

output("Il numero è divisibile per 2")

4

End

Autore: Bocchi Cinzia Ultimo aggiornamento: 05/10/2012

3

Verifica della correttezza dell’algoritmo Simuliamo l’algoritmo utilizzando la metodologia vista nel precedente macromodulo. Dopo aver numerato i blocchi del flow-chart, creiamo una tabella con tante colonne quante sono le variabili della tabella dati più una per l’output. In questo caso, trattandosi di un problema di scelta, dobbiamo aggiungere una colonna per il risultato della valutazione della condizione contenuta nel rombo (vero, falso). Verifichiamo la correttezza dell’algoritmo in due casi: con input 10 e input 11. Nel primo caso ci attendiamo in output la stringa “Il numero è divisibile per 2”; nel secondo caso l’output dovrà essere “Il numero non è divisibile per 2”. Verifica con input 10

azione 1

intero 10

resto

condizione

output

Viene acquisito in input il numero intero (10) e assegnato alla variabile intero.

azione 1 azione 2

intero 10

resto

condizione

output

0

Viene calcolato il resto della divisione intera tra intero e 2.

azione 1 azione 2 azione 3

intero 10

resto

condizione

output

0 vero

Viene valutata l’espressione logica contenuta nel blocco 3, che risulta vera in quanto resto è uguale a zero. A questo punto si segue il ramo vero e si tralascia il ramo falso.

azione 1 azione 2 azione 3 azione 4

intero 10

resto

condizione

output

0 vero Il numero è divisibile per 2

In output viene prodotta la stringa “Il numero è divisibile per 2”.

Autore: Bocchi Cinzia Ultimo aggiornamento: 05/10/2012

4

Verifica con input 11

azione 1

intero 11

resto

condizione

output

Viene acquisito in input il numero intero (11) e assegnato alla variabile intero.

azione 1 azione 2

intero 11

resto

condizione

output

1

Viene calcolato il resto della divisione intera tra intero e 2.

azione 1 azione 2 azione 3

intero 11

resto

condizione

output

1 falso

Viene valutata l’espressione logica contenuta nel blocco 3, che risulta falsa in quanto resto è diverso da zero. A questo punto si segue il ramo falso e si tralascia il ramo vero.

azione 1 azione 2 azione 3 azione 4

intero 11

resto

condizione

output

1 falso Il numero non è divisibile per 2

In output viene prodotta la stringa “Il numero non è divisibile per 2”. L’algoritmo è corretto poiché si comporta nel modo desiderato in tutti i casi considerati.

Eliminazione della variabile di lavoro Come accennato in precedenza, vi mostrerò che è possibile eliminare la variabile resto. La scelta di eliminare una variabile perché superflua può essere necessaria ai fini dell’ottimizzazione dello spazio di memoria occupato da un programma. Ovviamente, data la semplicità dell’algoritmo, non è il nostro caso. Ritengo comunque che sia utile fornirvi un esempio. La variabile resto può essere eliminata modificando la condizione contenuta nel rombo, nel modo seguente: (intero % 2) = 0 L’espressione logica è valutata andando prima a calcolare il risultato di (intero %2) e confrontando il valore ottenuto con 0. Le parentesi tonde non sono necessarie ma aumentano la leggibilità.

Autore: Bocchi Cinzia Ultimo aggiornamento: 05/10/2012

5

La modifica apportata produce alcuni cambiamenti nella tabella dei dati e nel flow-chart.

ID intero

TABELLA DATI Descrizione I/O/L Il numero intero dato I

Tipo numero intero

FLOW CHART Start 1

input(intero)

3 F

output("Il numero non è divisibile per 2")

(intero%2) = 0

5

V

output("Il numero è divisibile per 2")

4

End

Quest'opera è stata rilasciata con licenza Creative Commons Attribution-ShareAlike 3.0 Unported. Per leggere una copia della licenza visita il sito web http://creativecommons.org/licenses/by-sa/3.0/ o spedisci una lettera a Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.

Autore: Bocchi Cinzia Ultimo aggiornamento: 05/10/2012

6