G. Amodeo, C. Gaibisso Programmazione di Calcolatori Lezione V I Diagrammi di Flusso Programmazione di Calcolatori: I diagrammi di flusso 1 G. Amodeo, C. Gaibisso Nozione intuitiva di algoritmo • Nozione intuitiva di algoritmo • è una sequenza finita di istruzioni • ogni istruzione è costruita a partire da un alfabeto di dimensione finita • ogni istruzione nella sequenza è codificata con una quantità finita di informazione • deve esistere un agente di calcolo C capace di eseguire le istruzioni dell’algoritmo • C deve avere capacità di memorizzazione • ….. Programmazione di Calcolatori: I diagrammi di flusso 2 G. Amodeo, C. Gaibisso I diagrammi di flusso • Diagrammi di Flusso: • un formalismo grafico per la descrizione di algoritmi • un particolare simbolo grafico detto blocco è associato ad ogni tipo di istruzione elementare • i blocchi sono collegati tra loro da archi che definiscono l’ordine di esecuzione delle istruzioni Programmazione di Calcolatori: I diagrammi di flusso 3 G. Amodeo, C. Gaibisso Esempio • Calcolare la somma dei numeri 1 i N Start Nome: SommaN Variabili: int N, cont, somma Acquisizione del numero di valori da sommare Aggiornamento della somma parziale e del contatore Inizio della sequenza Inizializzazione della somma parziale e del contatore N somma 0 cont 0 Restituzione del valore calcolato cont cont+1 somma somma+cont true cont < N Verifica sul numero di somme effettuate false somma End Termine della sequenza Programmazione di Calcolatori: I diagrammi di flusso 4 G. Amodeo, C. Gaibisso Capacità di memorizzazione • Modello: descrizione della realtà limitatamente agli aspetti di interesse • Modello di memoria: • insieme di locazioni • ogni locazione può memorizzare un valore di tipo intero, carattere, o booleano • una locazione o è correntemente in uso o è disponibile intero A carattere B ‘c’ boleano in uso disponibile 3 C true • locazioni correntemente in uso sono dette variabili • ogni variabile è identificata da un nome e da un tipo Programmazione di Calcolatori: I diagrammi di flusso 5 G. Amodeo, C. Gaibisso Stato della Memoria • Molto informalmente: è una “foto” istantanea della memoria • E’ determinato: a) dal numero delle variabili b) dal loro nome, tipo e valore Programmazione di Calcolatori: I diagrammi di flusso 6 G. Amodeo, C. Gaibisso Stato della Memoria • Stato1 = Stato2 ? SI D 2 D 2 A ‘c’ A ‘c’ B 120 B 120 C ‘d’ C ‘d’ Stato1 Stato2 Programmazione di Calcolatori: I diagrammi di flusso 7 G. Amodeo, C. Gaibisso Stato della Memoria • Stato1 = Stato2 ? NO D 2 D 2 A ‘c’ A ‘c’ B 120 C ‘d’ C ‘d’ Stato1 Stato2 Programmazione di Calcolatori: I diagrammi di flusso 8 G. Amodeo, C. Gaibisso Stato della Memoria • Stato1 = Stato2 ? NO D 2 D 8 A ‘c’ A 12 B 120 B ‘m’ C ‘d’ C ‘d’ Stato1 Stato2 Programmazione di Calcolatori: I diagrammi di flusso 9 G. Amodeo, C. Gaibisso Stato della Memoria • Stato1 = Stato2 ? NO D 8 D 8 A 12 A 12 C ‘m’ E ‘m’ E ‘d’ C ‘d’ Stato1 Stato2 Programmazione di Calcolatori: I diagrammi di flusso 10 G. Amodeo, C. Gaibisso Stato della Memoria • Stato1 = Stato2 ? SI A A B B C C D D Stato1 Stato2 Programmazione di Calcolatori: I diagrammi di flusso 11 G. Amodeo, C. Gaibisso Stato della Memoria • Stato1 = Stato2 ? SI D 8 A 12 A 12 D 8 B true B true C ‘d’ C ‘d’ Stato1 Stato2 Programmazione di Calcolatori: I diagrammi di flusso 12 G. Amodeo, C. Gaibisso Tipologia dei blocchi • Blocchi di inizio e di termine Nome del diagramma Definizione delle variabili utilizzate Start Nome: SommaN Variabili: int N, somma, cont Tipo delle variabili N intero: -2, -1, 0, 1, 2 …. carattere: ‘c’, ‘2’, ‘!’ … booleano: true, false cont cont+1 somma somma+cont Inizio del diagramma 1 Nome delle variabili somma 0 cont 0 true + di 1 cont < N false Termine della sequenza somma End Programmazione di Calcolatori: I diagrammi di flusso 13 G. Amodeo, C. Gaibisso Definizione di una variabile • Blocco di inizio Per ognuna delle variabili elencate nel blocco 1. si individua una locazione di memoria disponibile 2. si riserva tale locazione 3. si associano a tale locazione il nome e il tipo specificati A B 2 120 StatoI A Start Nome: SommaN Variabili: int N, somma, cont intero 2 N B 120 StatoF Programmazione di Calcolatori: I diagrammi di flusso 14 G. Amodeo, C. Gaibisso Tipologia dei blocchi • Blocco di termine: si rilascia la memoria allocata ad ognuna delle variabili elencate nel blocco “Start” cont 4 cont 4 N 4 N 4 somma 10 somma 10 StatoI End StatoF Programmazione di Calcolatori: I diagrammi di flusso 15 G. Amodeo, C. Gaibisso Tipologia dei blocchi • Blocchi di acquisizione e di restituzione dati Start Nome: SommaN Variabili: int N, somma, cont Il dato acquisito è memorizzato nella variabile N N Blocco di acquisizione somma 0 cont 0 cont cont+1 somma somma+cont true cont < N Restituisce il contenuto della variabile somma false somma Blocco di restituzione End Programmazione di Calcolatori: I diagrammi di flusso 16 G. Amodeo, C. Gaibisso Tipologia dei blocchi • Blocco di elaborazione Start Nome: SommaN Variabili: int N, cont, somma Formato di un’operazione di assegnamento: nome espressione N Blocco di elaborazione cont cont+1 somma somma+cont true Blocco di elaborazione somma 0 cont 0 cont < N Contiene una sequenza di operazioni di assegnamento false Le operazioni di assegnamento vengono considerate nell’ordine in cui compaiono nel blocco dall’alto verso il basso somma End Programmazione di Calcolatori: I diagrammi di flusso 17 G. Amodeo, C. Gaibisso Operazioni di assegnamento • nome espressione 1. Si valuta il valore di espressione 2. Si aggiorna con tale valore il contenuto della variabile identificata da nome somma 3 N 3 cont 0 StatoI 1 cont cont+1 somma somma+cont 4 somma 0 4 N 3 cont 01 StatoF Programmazione di Calcolatori: I diagrammi di flusso 18 G. Amodeo, C. Gaibisso Tipologia dei blocchi • Blocco di decisione Start Nome: SommaN Variabili: int N, cont, somma N somma 0 cont 0 cont cont+1 somma somma+cont true cont < N Blocco di decisione Confronta due o più espressioni secondo diverse modalità Sulla base del risultato del confronto individua il prossimo blocco del flusso false somma End Programmazione di Calcolatori: I diagrammi di flusso 19 G. Amodeo, C. Gaibisso Riassumendo …. • Blocco di inizio int bool char Start Nome: Variabili: • Blocco di termine nome del diagramma tipo1 nome1 tipo2 nome2 …… End • Blocco di acquisizione nome1, nome2, … • Blocco di restituzione nome1, nome2, … • Blocco di elaborazione nome1 espressione1 nome2 espressione2 …… Programmazione di Calcolatori: I diagrammi di flusso 20 G. Amodeo, C. Gaibisso Riassumendo …. • Blocco di decisione true espressione a valore booleano Programmazione di Calcolatori: I diagrammi di flusso false 21 G. Amodeo, C. Gaibisso Operatori …. • Operatori aritmetici + : int x int int somma tra interi - : int x int int differenza tra interi * : int x int int prodotto tra interi / : int x int int divisione intera % : int x int int intera resto della divisione • Operatori logici not : bool bool negazione and : bool x bool bool and logico or : bool x bool bool or logico Programmazione di Calcolatori: I diagrammi di flusso 22 G. Amodeo, C. Gaibisso Operatori …. • Operatori di confronto tra interi = : int x int bool test di uguaglianza > : int x int bool strettamente maggiore ≥ : int x int bool maggiore o uguale < : int x int bool strettamente minore ≤ : int x int bool minore uguale Programmazione di Calcolatori: I diagrammi di flusso 23 Ordinamento lessicografico Tabella dei codici ASCII G. Amodeo, C. Gaibisso Programmazione di Calcolatori: I diagrammi di flusso 24 G. Amodeo, C. Gaibisso Operatori …. • Operatori di confronto tra caratteri = : char x char bool test di uguaglianza < : char x char bool precede lessicograficamente ≤ : char x char bool uguale o precede lessicograficamente > : char x char bool segue lessicograficamente ≥ : char x char bool uguale o segue lessicograficamente Programmazione di Calcolatori: I diagrammi di flusso 25 G. Amodeo, C. Gaibisso Condizioni di validità • Esiste un solo blocco di inizio ed ha un solo arco uscente; • esistono uno o più blocchi di termine • ciascun blocco di elaborazione, di acquisizione, di restituzione ha un solo arco entrante e un solo arco uscente; • ciascun blocco di decisione ha un solo arco entrante e due uscenti; • ciascun arco entra in un blocco o si innesta su un altro arco; • ciascun blocco è raggiungibile dal blocco iniziale; • da qualsiasi blocco è possibile raggiungere almeno uno dei blocchi di termine. Programmazione di Calcolatori: I diagrammi di flusso 26 G. Amodeo, C. Gaibisso Un semplice esempio Calcolare il massimo di una sequenza di N≥1 numeri interi Start Nome: MaxTraN Variabili: int N, count, max, val int count N, val max val count 1 count = N true max false false max val true val > max count count+1 End val Programmazione di Calcolatori: I diagrammi di flusso 27 G. Amodeo, C. Gaibisso Vettori • Vettore (monodimensionale) di n elementi: definisce una corrispondenza biunivoca tra un insieme omogeneo di n elementi e l’insieme di interi {0, 1, …, n-1} • Esempio: Vettore di 5 interi • Definizione 0 1 5 -1 2 32 3 -4 4 27 costante intera tipoVettore nomeVettore [dimVettore] Programmazione di Calcolatori: I diagrammi di flusso 28 G. Amodeo, C. Gaibisso Vettori • Effetto A 2 A 2 Start … Variabili: int Vett[3] intero B 120 B StatoI 120 Vett[0] Vett[1] Vett[2] StatoF • Accesso all’elemento di un vettore 0 espressione a valore intero dimVettore-1 nomeVettore [indice] Programmazione di Calcolatori: I diagrammi di flusso 29 G. Amodeo, C. Gaibisso Vettori • Esempio Start Nome: AcqVett Variabili: int index, int vett[K] Acquisizione del contenuto di un vettore di K interi index 0 index index+1 index < K false End true vett[index] Programmazione di Calcolatori: I diagrammi di flusso 30 G. Amodeo, C. Gaibisso Matrici • Matrice di n x m elementi: definisce una corrispondenza biunivoca tra un insieme omogeneo di n x m elementi e l’insieme di coppie di interi {(0,0), (0,1), …., (n-1, m-1)} • Esempio: Matricedi 5 x 2 interi • Definizione (0,0) (1,0) (2,0) (3,0) (4,0) 8 7 15 4 7 4 -1 12 -9 4 (0,1) (1,1) (2,1) (3,1) (4,1) costanti intere tipoMatrice nomeMatrice [dimRighe] [dimColonne] Programmazione di Calcolatori: I diagrammi di flusso 31 G. Amodeo, C. Gaibisso Matrici • Accesso all’elemento di una matrice 0 espressione a valore intero dimColonne-1 nomeMatrice [indiceRiga][indiceColonna] 0 espressione a valore intero dimRighe-1 Programmazione di Calcolatori: I diagrammi di flusso 32 G. Amodeo, C. Gaibisso Matrici • Esempio Start Nome: AcqMatRighe Variabili: int riga, col int mat[P][Q] Acquisizione del contenuto di una matrice di P x Q interi (per righe) riga 0 col 0 riga < P false End true riga riga+1 false col 0 col < Q true mat[riga][col] col col+1 Programmazione di Calcolatori: I diagrammi di flusso 33 G. Amodeo, C. Gaibisso Matrici Start Nome: AcqMatCol Variabili: int riga, col int mat[P][Q] • Esempio riga 0 col 0 Acquisizione del contenuto di una matrice di P x Q interi (per colonne) col < Q false End true riga 0 col col+1 false riga < P true mat[riga][col] riga riga+1 Programmazione di Calcolatori: I diagrammi di flusso 34 G. Amodeo, C. Gaibisso Matrici Start Nome: AcqMat Variabili: int riga, col, max int mat[P][Q] • Esempio riga 0 col 0 max mat[0][0] col < Q false End true riga 0 col col+1 false riga < P true mat[riga][col] > max Restituzione del massimo elemento di una matrice di P x Q interi, P ≥ 1, Q ≥ 1 false riga riga+1 true max mat[riga][col] Programmazione di Calcolatori: I diagrammi di flusso 35