Fondamenti di Informatica: algoritmi e diagrammi di flusso

Algoritmi e Diagrammi di Flusso

Francesco Capezio
Francesco.capezio@gmail.com

Argomenti della Lezione

• Algoritmi e Istruzioni
• Istruzioni e dati in memoria
• Esempi
• Dati di ingresso e uscita
• Formalismo

Sviluppo del software

Programmi e Algoritmi

PRBLEMA
ALGORITMO
PROGRAMMA
DATI DI INGRESSO
PROGRAMMA
DATI IN USCITA

Algoritmo: Definizione

procedimento che risolve un determinato problema attraverso
un numero finito di passi elementari

Istruzioni: Esempio Cuocere la Pasta

1) Riempire una pentola d'acqua
2) Accendere un fornello
3) Mettere la pentola sul fornello
4) Attende che l'acqua arrivi ad ebollizione
5) Mettere il sale nell'acqua
6) Buttare 180gr di pasta
7) Attendere 11 minuti
8) Prendere un colapasta
9) Scolare la pasta
C'E' UN ERRORE!
Non abbiamo spento il fornello!

Algoritmo: Esempio Pesare la Pasta

ESEMPIO: Mettere in un piatto 180 gr di pasta
1) Prendere un piatto
2) Mettere della pasta nel piatto
3) Pesare
4) Se il peso è maggiore di 180 gr
togliere della pasta e tornare al punto 3)
5) Se il peso è minore di 180gr

aggiungere della pasta e tornare al punto 3)
6) Se il peso è uguale a 180gr ho risolto il problema
Alcune istruzioni vengono esegutie
solo se la condizione è quella
giusta
L'istruzione successiva può essere
· il passo successivo

• il passo indicato

Dati di Ingresso e Uscita

DATI DI INGRESSO
PROGRAMMA
(algoritmo)
DATI IN USCITA
· Pasta
Cuocere la
pasta

• Pasta cotta
• Acqua
• 1Kg pasta
  Pesare la pasta
  · 180gr di
  pasta

Algoritmo: Somma di Due Numeri

ESEMPIO: Eseguire la somma di due numeri forniti dall'utente
1) Leggere il numero A
2) Leggere il numero B
3) S = A + B
4) Stampare S sullo schermo
Notiamo che sia le istruzioni che i dati
Sono salvati nella RAM!
RAM
LEGGI A DA TASTIERA
LEGGI B DA TASTIERA
S = A + B
STAMPA S SULLO SCHERMO
A
B

Algoritmo: Sviluppo

Come procedere per sviluppare un algoritmo:
1) Definisco i dati di ingresso
2) Definisco i dati di uscita
3) Definisco le operazioni ELEMENTARI da svolgere
4) Do un ordine alla operazioni ELEMNTARI, in modo da modificare i
dati di ingresso per ottenere i dati di uscita

Esempio: Cassiera del Supermercato

ESEMPIO: Cassiera del supermercato fa il conto e imbusta la spesa.
Attenzione un sacchetto contiene al massimo 5 oggetti

Algoritmo: Cassiera del Supermercato (Dettagli)

ESEMPIO: Cassiera del supermercato fa il conto e imbusta la spesa. Attenzione un
sacchetto contiene al massimo 5 oggetti
Dati in ingresso:
· Il numero di prodotti oppure un
indicatore di «fine dei prodotti»
· Il costo dei prodotti
Dati in uscita:
· Il conto totale
· Le buste con i prodotti
Operazioni elementari
· Capire se ci sono altri prodotti
· Leggere il costo del prodotto
· Aggiornare il totale del conto
· Mettere il prodotto nella busta
· Prendere una nuova busta

Algoritmo: Cassiera del Supermercato (Formalizzazione)

ESEMPIO: Cassiera del supermercato fa il conto e imbusta la spesa. Attenzione un
sacchetto contiene al massimo 5 oggetti
Proviamo a formulare l'algoritmo (la serie di passi) in modo più formale
1) Metto il totale del conto a zero.
2) Guardo se ci sono altri prodotti
3) Se non si sono più prodotti

vado al passo 9)
4)
Leggo il costo del prodotto
5)
Sommo il costo al totale
6) Metto il prodotto nella busta
7)
Se ci sono 5 prodotti nella busta

prendo una nuova busta
8) Torno al punto 2)
9) Operazione finita, fornisco al cliente il conto e le buste

Variabili

Le variabili sono CONTENITORI LOGICI DI INFORMAZIONI.
Hanno un NOME che non cambia mai e un CONTENUTO che può cambiare
Possiamo immaginare una variabile come una scatola con una «scritta» (che è il nome)
e nella quale possiamo mettere quello che vogliamo: numeri, scritte e «indicatori
vero/falso»
RAM
NUMERI
Valore
CARATTERI (stringhe)
NOME
BOOLEANI: vero/falso
Nome
Valore
IMPORTANTE: Una volta scelto, il nome di una variabile non può
più cambiare

Algoritmo: Cassiera del Supermercato (Variabili Numeriche)

ESEMPIO: Cassiera del supermercato fa il conto e imbusta la spesa. Attenzione un
sacchetto contiene al massimo 5 oggetti
Proviamo a riformulare l'algoritmo della commessa scegliendo VARIABILI DI TIPO
NUMERICO
Variabili in ingresso:
· N: è il numero di prodotti
· COSTO: è il costo di ogni prodotto
Variabili in uscita:
· TOTALE: è il totale del conto
· BUSTE: è il numero delle buste usate
· P: sono i prodotti nella busta
Operazioni elementari
· Controllo quanti prodotti ci sono (ingresso della variabile N)
· Leggo il costo del prodotto (ingresso della variabile COSTO)
· Aggiorno il totale (sommo la variabile COSTO al TOTALE)
· Metto il prodotto nella busta (aumento di 1 la variabile P)
· Se ci sono 5 prodotti nella busta prendo un'altra busta (aumento di 1 la var BUSTA)
· Quando ho finito il prodotto (variabile N=0) fornisco in uscita le var. TOTALE e BUSTE

Algoritmo: Cassiera del Supermercato (Passi)

ESEMPIO: Cassiera del supermercato fa il conto e imbusta la spesa. Attenzione un
sacchetto contiene al massimo 5 oggetti
Algoritmo
1. Inizializzazione: T=0, B=1, P=0
2. Input N
3. Se N == 0

Vado al punto 10)
4. Input COSTO
5. TOTALE = TOTALE + COSTO
6. P = P + 1
7. N = N -1
8. Se P > 5

BUSTE = BUSTE + 1
P = 1
9. Torno al punto 3)
10. Output: TOTALE, BUSTE.
Algoritmo
1. Azzero il totale e prendo una busta vuota
2. Guardo quanti prodotti ci sono all'inizio
3. Se non ci sono più prodotti
Vado al punto 10)
4. Leggo il costo del prodotto
5. Sommo il costo al totale
6. Metto il prodotto nella busta
7. Tolgo il prodotto da quelli che rimangono
8. Se i prodotti nella busta sono più di 5
-
prendo un'altra busta
e inserisco il primo prodotto
8. Torno al punto 3)
9. Fornisco all'utente il consto e le buste

Algoritmo: Tracing delle Variabili

Esempio: abbiamo 6 prodotti. I prezzi sono, rispettivamente: 9, 4, 5, 2, 7, 6
Tracing delle variabili
Algoritmo
1. Inizializzazione: T=0, B=1, P=0
2. Input N
3. Se N == 0
6
9
9
1
5
4
13
2
4
5
18
3
3
2
20
4
2
7
27
5
1
6
33
6
2
0
1
9. Torno al punto 3)
10. Output: TOTALE, BUSTE.
N
C
T
P
B
0
0
1

Vado al punto 10)
4. Input COSTO
5. TOTALE = TOTALE + COSTO
6. P = P + 1
7. N = N -1
8. Se P > 5

BUSTE = BUSTE + 1
P = 1

Ripasso: Sviluppo Algoritmo

Come procedere per sviluppare un algoritmo:
1) Definisco le variabili di ingresso
2) Definisco le variabili di uscita
3) Definisco le operazioni ELEMENTARI da svolgere
4) Do un ordine alla operazioni ELEMNTARI, in modo da modificare i
dati di ingresso per ottenere i dati di uscita
5) Testo l'algoritmo facendo il tracing delle variabili
6) Modifico, eventualmente, algoritmo
Definire e Inizializzare le variabili è sempre il primo passo di ogni algoritmo

I Diagrammi di Flusso

Metodo grafico CANONICO per formalizzare un algoritmo
Si utilizzano 4 forme base utilizzate in base al tipo di operazione
INIZIO
V
F
SCELTA/CONDIZIONE (SE)
FINE
T
INPUT o OUTPUT
CALCOLO
I blocchi vengono collegati tra di loro utilizzando delle frecce

I Diagrammi di Flusso: Esempio Cassiera

Esempio: algoritmo della cassiera
Variabili di input
N: numero prodotti
C: costo prodotti
Variabili di uscita
T: totale conto
B: buste
P: prodotti nella busta
INIZIO
T = 0 ; B = 1; P = 0
In:
N
V
N == 0
F
V
Out:
T
IN:
C
V
Out:
B
T = T + C
V

FINE
P = P +1
N = N - 1
F
P> 5
IV
B= B + 1
P = 1

I Diagrammi di Flusso: Algoritmo Cassiera (Dettagli)

Algoritmo della cassiera
1. Azzero il totale e prendo una busta vuota
2. Guardo quanti prodotti ci sono all'inizio
3. Se non ci sono più prodotti
Vado al punto 10)
4. Leggo il costo del prodotto
5. Sommo il costo al totale
6. Metto il prodotto nella busta
7. Tolgo il prodotto da quelli che rimangono
8. Se i prodotti nella busta sono più di 5
prendo un'altra busta
e inserisco il primo prodotto
8. Torno al punto 3)
9. Fornisco all'utente il consto e le buste
INIZIO
T = 0 ; B = 1; P = 0
In:
N
V
N == 0
V
F
Out:
T
IN:
C
V
Out:
B
T = T + C
V

FINE
P = P +1
N = N - 1
F
P> 5
IV
B= B + 1
P = 1

I Diagrammi di Flusso: Esempio Bancomat

Esempio: Algoritmo del bancomat
Vogliamo implementare un algoritmo che simuli il funzionamento del bancomat.
Proviamo a definire le operazioni elementari da fare e le variabili di ingresso e uscita-

Operazioni Elementari (Istruzioni) Bancomat

• Inserire la carta
• Digitare il pin
• Controllare che il pin corrisponda a quello salvato
• Chiedere quale operazione fare: Prelievo o Versamento
• Chiedere l'importo (da prelevare o versare)
• Se l'importo è da versare aggiungerlo al saldo
• Se l'importo è da prelevare toglierlo al saldo ma solo se ci sono soldi a sufficienza

I Diagrammi di Flusso: Bancomat (Variabili e Logica)

VARIABILI DI INPUT
P > è il pin digitato (numero)
S -> è il SALDO (numero)
Op > è l'operazione da fare
(«V» versamento ; «P» prelievo
I > è l'importo (numero)
VARIABILI DI OUTPUT
RX
Ricevuta di operazione effettuata (Booleano)
vero - operazione conclusa con successo
falso - errore nell'operazioni
Serve una variabili da memorizzare:
PIN -> è il pin salvato
INIZIO
S = 0; PIN=35266
All'inizio il programma
decide un PIN e mette il
conto a zero
Inserire bancomat
In: P
L'utente inserisce il pin
F
P == PIN
Controllo se il pin digitato è
uguale a quello salvato, se
non lo è lo richiedo
In: Op
L'utente inserisce
l'operazione desiderata
T
F
Op == "V"
Se l'operazione
è il versamento,
altrimenti è un
prelievo!
In:
I
Inserisco l'importo
In:
-
Sommo
F
S = S+I
l'importo al
saldo
I<S
Se l'importo è
minore del
saldo
T
R = "true"
R = "false"
R = "true"
S = S - I
Sottraggo
l'importo al
saldo
Out:
R
Stampo la ricevuta
precedentemento configurata
e riconsegno il bancomat