Altro su diagrammi flusso e diagrammi strutturati PDF

Preview

Summary

appunti per preparazione esame informatica per vari argomenti algoritmo flowchart codifica trattazione numeri binari passaggio da vari sistemi...

Description

Informatica

Programmazione e diagrammi di flusso

La programmazione

Sviluppo del software problema idea (soluzione informale) algoritmo (soluzione formale) programma (traduzione dell’algoritmo in una forma comprensibile da un elaboratore elettronico) • test (su molti casi, con particolare attenzione ai casi limite) • documentazione (manuale utente + manuale del programmatore)

• • • •

© A.Lioy - Politecnico di Torino (1992-2011)

1

Informatica

Programmazione e diagrammi di flusso

Algoritmo Un algoritmo può essere considerato un insieme di regole per svolgere un dato compito (risolvere un problema). Il nome deriva dal matematico persiano Muhammad ibn Mūsa 'l-Khwārizmī (780-850). Un algoritmo deve: • terminare in un tempo finito • produrre un effetto osservabile • essere deterministico, ossia produrre gli stessi risultati a partire dalle stesse condizioni iniziali

Esecuzione di un algoritmo Vengono eseguite in sequenza le operazioni che lo costituiscono. Esistono algoritmi che prevedono: • una sequenza di esecuzione unica • sequenze di esecuzione multiple

© A.Lioy - Politecnico di Torino (1992-2011)

2

Informatica

Programmazione e diagrammi di flusso

Esempio: sequenza di esecuzione unica Dato il valore di X, calcolare: Y = 5 X + 3 Sequenza di esecuzione: 1. ricevo il valore di X 2. moltiplico X per 5 (sia Z il risultato) 3 sommo 3 a Z ((sia 3. i Y il risultato) i lt t ) 4. visualizzo Y

Esempio: sequenze di esecuzione multiple Dato il valore di X, calcolare la radice quadrata di X+5. Sequenza di esecuzione: 1. ricevo il valore di X 2. sommo 5 a X (sia Y il risultato) 3a. se Y è positivo o nullo, calcolo la sua radice quadrata e la visualizzo 3b. se Y è negativo, indico che è impossibile calcolare la sua radice quadrata

© A.Lioy - Politecnico di Torino (1992-2011)

3

Informatica

Programmazione e diagrammi di flusso

Formalizzazione di una soluzione • pseudo-linguaggio (o pseudo-codice) – –

vantaggi: immediato svantaggi: descrizione dell’algoritmo poco astratta, interpretazione più complicata

• diagrammi di flusso –

–

vantaggi: più intuitivi perché usano un formalismo grafico, grafico descrizione descri ione dell’algoritmo più astratta svantaggi: richiedono l’apprendimento della funzione dei vari tipi di blocco

Diagrammi di flusso (flow-chart) • metodo grafico per descrivere in modo formale un algoritmo • blocchi base per descrivere: – azioni – decisioni (solo binarie, ossia della logica Booleana)

• archi orientati per descrivere la sequenza di svolgimento delle azioni

© A.Lioy - Politecnico di Torino (1992-2011)

4

Informatica

Programmazione e diagrammi di flusso

Blocchi di inizio e fine START

STOP

Blocco di azione

azione

© A.Lioy - Politecnico di Torino (1992-2011)

5

Informatica

Programmazione e diagrammi di flusso

Blocco di Input/Output

azione di I/O

Blocco di inizializzazione

azione di inizializzazione

© A.Lioy - Politecnico di Torino (1992-2011)

6

Informatica

Programmazione e diagrammi di flusso

Blocco di decisione binaria

condizione Booleana

V

F

Connettore

© A.Lioy - Politecnico di Torino (1992-2011)

7

Informatica

Programmazione e diagrammi di flusso

Regole • uno ed un solo blocco START • uno ed un solo blocco STOP • tutti gli archi devono avere origine e fine in un blocco

Diagrammi di flusso strutturati Un diagramma di flusso è detto strutturato se contiene solo un insieme predefinito di strutture: • sequenze • decisioni – IF-THEN-ELSE – IF-THEN

• cicli – WHILE – REPEAT

© A.Lioy - Politecnico di Torino (1992-2011)

8

Informatica

Programmazione e diagrammi di flusso

Teorema di Böhm - Jacopini Qualunque diagramma di flusso è sempre trasformabile in un diagramma di flusso strutturato equivalente a quello dato.

Sequenza

azione-1

azione-2

© A.Lioy - Politecnico di Torino (1992-2011)

9

Informatica

Programmazione e diagrammi di flusso

If-Then-Else

V

condizione

struttura-1

F

struttura-2

If-Then

V

condizione

F

struttura-1

© A.Lioy - Politecnico di Torino (1992-2011)

10

Informatica

Programmazione e diagrammi di flusso

If-Else • non esiste un blocco If-Else … • … perché non è necessario! • basta usare un blocco If-Then in cui la condizione sia stata invertita (negata)

If-Else (esempio)

ho abbastanza soldi ? V

F

prelevo al Bancomat

NON ho abbastanza soldi ?

F

V prelevo al Bancomat

© A.Lioy - Politecnico di Torino (1992-2011)

11

Informatica

Programmazione e diagrammi di flusso

While-Do

condizione

F

V

struttura

While-Do • la parte ciclica viene eseguita quando la condizione è vera • se abbiamo un ciclo che viene eseguito quando la condizione è falsa, allora occorre trasformarlo in un While-Do mettendo la condizione negata • un ciclo i l While-Do Whil D puòò essere eseguito it zero o più volte • viene eseguito zero volte quando la condizione è subito falsa

© A.Lioy - Politecnico di Torino (1992-2011)

12

Informatica

Programmazione e diagrammi di flusso

Repeat-Until

struttura

condizione

F

V

Repeat-Until • un ciclo Repeat-Until viene sempre eseguito almeno una volta

© A.Lioy - Politecnico di Torino (1992-2011)

13

Informatica

Programmazione e diagrammi di flusso

Verifica di strutturazione P1. etichettare ogni blocco P2 sostituire ad ogni insieme strutturato un P2. un blocco avente come etichetta l’unione delle etichette dei blocchi che lo costituiscono P3. se al passo P2 si è fatta almeno una sostituzione, ripetere il passo P2 P4. se alla fine si ottiene un diagramma lineare (una sequenza), allora il diagramma originale è strutturato

Esempio: diagramma strutturato START

1

F

2

5 V

3

STOP

4

© A.Lioy - Politecnico di Torino (1992-2011)

14

Informatica

Programmazione e diagrammi di flusso

Esempio: diagramma strutturato START

1

F

2

5 V

3,4

STOP

Esempio: diagramma strutturato START

1

2, 3, 4

5

STOP

© A.Lioy - Politecnico di Torino (1992-2011)

15

Informatica

Programmazione e diagrammi di flusso

Esempio: diagramma strutturato START

1, 2, 3, 4, 5

STOP

Esempio: diagramma non strutturato

START

1

2

Il ciclo non ha un test all’inizio o alla fine

F

3

5

V

4

© A.Lioy - Politecnico di Torino (1992-2011)

STOP

16...