3. Programmazione strutturata
(testo di riferimento: Bellini-Guidi)
Ing. Simona Colucci
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Linguaggi di programmazione
Un programma è un algoritmo espresso in un
linguaggio formale, detto linguaggio di
programmazione:
• Interpretabile ed eseguibile da un calcolatore
• Non ambiguo perchè governato da regole
grammaticali precise
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Linguaggi di programmazione
Classificazione:
• linguaggi di basso livello
(linguaggi macchina e
linguaggi assembler):
dipendono dalla struttura
fisica del tipo di computer
per cui sono stati progettati
• linguaggi di alto livello:
più vicini alla forma mentis
dell’uomo, ma da tradurre in
codice di basso livello per
l’interpretazione da parte
dell’elaboratore(come il C)
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Linguaggio Macchina
• Linguaggio formale che il computer è in grado di
interpretare ed eseguire senza mediazioni
• Programmi, codice oggetto, rappresentati da una
sequenza di cifre binarie che codificano le istruzioni e i
dati su cui lavora la CPU
• istruzioni fortemente correlate all’architettura del calcolatore,
perché corrispondenti ad operazioni direttamente eseguibili
dall’hardware
• esempio di istruzione ad un solo operando :
codice operativo dell’istruzione
00000010
operando
000000000011100
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Linguaggio assembler
• Le singole istruzioni binarie sono rappresentate con un
codice mnemonico
LOAD 220
SUM 252
MEM 220
• Traduzione in linguaggio macchina ad opera di
programmi detti assemblatori, forniti dai costruttori
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Microlinguaggi
• Usati per i microprogrammi:
– corrispondono ad ogni istruzione del linguaggio macchina
– costituiti da insiemi di microistruzioni:
• sequenze di bit che costituiscono i segnali di controllo per pilotare i
componenti del processore ed eseguire le istruzioni
• cablate dal costruttore nelle unità di controllo(fisicamente delle
memorie) della CPU per eseguire le operazioni corrispondenti alle
istruzioni del linguaggio macchina
• Obbediscono alla necessità di mediazione tra linguaggio
macchina e macchina: lo stesso processore può essere
programmato per finalità diverse
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Linguaggi di alto livello
• Più simili al linguaggio naturale dei linguaggi macchina o
assembler
• Utilizzano simboli matematici e parole tipiche delle lingue
naturali(inglese)
• Usati per scrivere le istruzioni che compongono il codice
sorgente
• appositi software, detti compilatori, provvedono a
tradurre il codice sorgente nell’equivalente codice
eseguibile dalla macchina
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Linguaggi di alto livello
• Esempio di codifica: somma precedente in linguaggio C
a =6;
b =31;
a =a+b;
– a e b non sono registri o locazioni di memoria ma variabili
identificate da:
• Nome(possibilità di usare nomi simbolici del contenuto, per facilitare
la leggibilità del programma)
• Insieme di valori che può assumere
• Vantaggi
– Programma portabile su ogni macchina con compilatore per il
linguaggio in cui è scritto il programma
– Gestione indirizzi di memoria totalmente delegata al calcolatore
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Algoritmi come sequenze di stati
Esempio: determina il Massimo Comune Divisore (MCD)
a. prendi i due numeri
b. calcola il resto della divisione intera del num. più grande
per il più piccolo
c. sostituisci il numero più grande con il resto della
divisione
d. finché tale resto è diverso da zero torna all’istruzione b
e. il numero più grande (quello non nullo) è il MCD cercato
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Algoritmi come sequenze di stati
Flusso di esecuzione dell’algoritmo MCD con i numeri 924 e 120
passo
passo
passo
passo
passo
passo
passo
passo
passo
passo
passo
passo
passo
passo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
924 e 120
84 è il resto della divisione intera di 924 per 120
120 e 84
il resto è diverso da zero, torna all’istruzione b
36 è il resto della divisione intera di 120 per 84
84 e 36
il resto è diverso da zero, torna all’istruzione b
12 è il resto della divisione intera di 84 per 36
36 e 12
il resto è diverso da zero, torna all’istruzione b
0 è il resto della divisione intera di 36 per 12
12 e 0
il resto è uguale a zero, prosegui con l’istruzione successiva
12 è il MCD
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Algoritmi come sequenze di stati
Sequenza di stati
nel flusso
dell’algoritmo per
il calcolo del
MCD(924,120)
•
•
•
•
Istruzioni all’interno dei cerchi
Passi in esecuzione dell’istruzione all’esterno del relativo cerchio
Passaggio da un’istruzione all’altra tramite archi
L’esecuzione di un passo determina uno stato: fotografia della
situazione attuale
• Il susseguirsi dei passi di esecuzione determina una sequenza di
stati
• Il flusso è sequenziale ed ordinato perché l’algoritmo segue le
regole della programmazione strutturata
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Programmazione non strutturata
Esempio: Algoritmo equivalente per il calcolo del Massimo
Comune Divisore (MCD)
a. prendi i due numeri
b. calcola il resto della divisione intera del num. più grande
per il più piccolo
c. Se il resto è uguale a zero vai all’istruzione f
d. sostituisci il numero più grande con il resto della
divisione
e. vai all’istruzione b
f. il numero più piccolo è il MCD cercato
Salto
incondizionato
Salto
condizionato
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Programmazione non strutturata
Flusso di esecuzione dell’algoritmo MCD con i numeri 924 e 120
passo
passo
passo
passo
passo
passo
Passo
Passo
passo
passo
Passo
passo
passo
passo
passo
passo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
13
14
924 e 120
84 è il resto della divisione intera di 924 per 120
il resto è diverso da zero(prosegui in sequenza)
120 e 84
vai all’istruzione b
36 è il resto della divisione intera di 120 per 84
il resto è diverso da zero(prosegui in sequenza)
84 e 36
vai all’istruzione b
12 è il resto della divisione intera di 84 per 36
il resto è diverso da zero(prosegui in sequenza)
36 e 12
vai all’istruzione b
0 è il resto della divisione intera di 36 per 12
il resto è uguale a zero, vai all’istruzione f
12 è il MCD
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Sequenza di stati
nel flusso
dell’algoritmo per
il calcolo del
MCD(924,120)
Programmazione non strutturata
5,9,13
e
d
a
b
1
2,6,10,14
c
4,8,12
3,7,11,15
f
16
• Si parte dal nodo iniziale e poi si passa ai nodi successivi
selezionando il cammino in base allo stato che si viene a creare dopo
l’esecuzione delle operazioni specificate nel nodo
• L’arco e-b corrisponde ad un salto incondizionato (goto)
• L’uso dei goto :
– porta a sequenze non lineari di stati, molto contorte, note come
programmi a “spaghetti”, specie per programmi complessi
– ha un numero di istruzioni minori e riusa parti di programma tramite salti
– porta a programmi difficili da correggere manutenere ed estendere
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Programmi strutturati
• L’obiettivo della programmazione strutturata è di rendere un
flusso ordinato il passaggio tra le istruzioni dall’inizio alla fine dei
programmi
• Realizzazione:
– Condizione ideale: sequenza lineare di operazioni, senza alternative
possibili(limite: potenza algoritmi ridotta)
– Condizione reale: regole coerenti con il pensiero naturale che portano
ad effetti equivalenti all’esecuzione sequenziale di operazioni
• Costrutti consentiti (strutture di controllo del flusso):
– Sequenza: fai questo
– Selezione tramite strutture di controllo decisionali:
se è verificata una condizione fai questo altrimenti fai quello
– Ripetizioni cicliche tramite strutture di controllo iterative:
finché è verificata una condizione fai questo
• Costrutti non consentiti:
– Salto incondizionato (goto): ancora nella sintassi solo per compatibilità verso il
basso(era necessario nel linguaggio macchina e assembler)
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Programmi strutturati
TEOREMA DI BOHM-JACOPINI:
tutti i programmi possono essere scritti con l’utilizzo delle
sole strutture di controllo: sequenza, selezione e
iterazione (senza l’uso del salto goto)
• Corrado Böhm e Giuseppe Jacopini hanno dimostrato che la potenza
di calcolo dei programmi strutturati(più chiari, più facili da scrivere e
da modificare e più probabilisticamente esenti da errori) non è
inferiore a quella dei programmi che usano il goto
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Sequenza : flow-chart
• Operazioni:
- fai questo
- fai quello
• Esempio: a = 5;
a = a+b;
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
•
Operazioni:
–
–
•
Selezione : flow-chart
se è verificata una condizione fai questo
se è verificata una condizione fai questo altrimenti fai quello
Sintassi:
– if(espressione) istruzione
Esempio: prendi numero;
resto = numero % 2;
if(resto==0) scrivi "è pari";
– if(espressione) istruzione1 else istruzione2
Esempio: prendi numero;
resto = numero % 2;
if(resto==0) scrivi "è pari" else scrivi "è dispari";
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
Iterazione : flow-chart
DEE - Politecnico di Bari
espressio
ne
falso
vero
istruzione
• Operazioni:
– finchè è verificata una condizione fai questo
– esegui fai questo finchè è verificata una condizione
• Sintassi:
– while(espressione) istruzione;
Esempio: i=0;
while(i<101) i=i+1;
– do istruzione while(espressione);
Esempio: i=0;
do
i=i+1;
while(i<100);
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Programmi strutturati: flow-chart
• Si apre con un cerchio e finisce con un cerchio: tutti i
canali partono dal primo cerchio e terminano
nell’ultimo(un solo inizio ed una sola fine)
• Composto da più strutture di controllo del tipo sequenza
selezione o iterazione
• I cerchi sono i connettori tra le strutture di controllo: altri
punti di attacco non consentiti
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Blocco d’istruzioni
• Più strutture formano un blocco d’istruzioni:
– insieme d’istruzioni con una sola entrata, da dove
inizia sempre l’elaborazione, e una sola uscita, dove
termina sempre l’elaborazione del blocco(nessuna
uscita laterale con istruzioni di salto)
– Scatola nera per eseguire un compito: non possono
essere utilizzate delle sottoparti
– Sintassi: {blocco}
I blocchi possono contenersi l’un l’altro ma mai
intersecarsi
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
blocco
Sistemi Informativi
DEE - Politecnico di Bari
Programmazione strutturata: esempi
1. Calcolo della somma algebrica tra due numeri relativi
utilizzando le operazioni di somma e differenza tra
numeri senza segno
2. Calcolo della media
3. Calcolo dei valori massimo e minimo
4. Visualizzazione di caratteri letti da tastiera
5. Calcolo di una potenza
6. Visualizzazione di un quadrato
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Esempio 1
inizio
Problema: Calcolo della somma
algebrica tra due numeri relativi
utilizzando le operazioni di
somma e differenza tra numeri
senza segno
Algoritmo:
- acquisizione dei due numeri a,b
- se a,b sono concordi
|s|=|a|+|b|
- se a,b sono discordi
- se |a|<|b| si scambiano i
valori di a e b
- |s|=|a|-|b|
- la somma ha il segno di a e
modulo |s|
a,b
vero
falso
a, b concordi
vero
s a+b
t a
|a| < |b|
falso
a b
bt
s a-b
modulo di s e segno di a
fine
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Esempio 2
inizio
Problema: Acquisizione di 10
numeri interi e calcolo
della media
Algoritmo:
1. Azzerare la somma s
2. Se non si sono acquisiti
tutti i numeri:
2.1 Acquisire un numero n
2.2 Sommare n ad s e
tornare al passo 2
3. La media è s/10
4. Fine
s0
i 0
falso
i < 10
vero
n
ss+n
i i+1
m  s/10
m
fine
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Esempio 3
inizio
Problema: Acquisizione di 10
numeri interi; determinazione e
visualizzazione del numero
maggiore e minore
Algoritmo:
1. Leggi il primo numero n
2. Poni il massimo e il minimo
corrente(variabili max e min)
pari a n
3. Finché i numeri inseriti sono
meno di 10
3.1 Leggi un nuovo numero n
3.2 Se n<min min=n
altrimenti se n>max max=n
4. Visualizza min e max
5. Fine
n
min  n
max n
i<
10
i 1
falso
vero
n
falso
n<
min
vero
min  n
vero
n > max
falso
max n
i  i +1
min, max
fine
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Esempio 4
inizio
Problema: Scrivere un
programma che consenta,
acquisito un numero intero
n, di acquisire un carattere
c e visualizzarlo n volte
sulla stessa riga finché n è
maggiore di zero
Algoritmo:
1. Leggi il primo numero n
2. Finché n>0
2.1
2.2
2.3
2.3
3. Fine
Leggi c
Visualizza c n volte
Visualizza “a capo”
Leggi nuovo numero n
connettore
n
n>
0
falso
Inizio blocco 2.2
vero
i 0
falso
i< n
c
vero
c
blocco 2.2
i  i+1
a capo
Fine blocco 2.2
n
fine
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Problema: Calcolo e
visualizzazione di una
potenza(variabile pot),
acquisiti la base x e
l’esponente n
Algoritmo:
1. Acquisisci x ed n(intero)
2. Poni pot pari ad 1
3. Esegui per n volte
pot pot * x
4. Visualizza pot
5. Fine
Esempio 5
inizio
x, n
pot  1
i0
falso
i< n
vero
pot = pot * x
i  i+1
pot
fine
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
Sistemi Informativi
DEE - Politecnico di Bari
Esempio 6
inizio
n
Problema: acquisito un numero intero n,
si visualizzi una figura quadrata di
n*n con degli asterischi nella
diagonale principale, dei segni meno
al di sotto e dei segni più al di sopra
della diagonale principale
Algoritmo:
1. Leggi n
2. Finché le righe visualizzate sono
meno di n (indice i scorre le righe)
•
Finchè le colonne visualizzate sono
meno di n(indice j scorre le colonne)
•
•
•
3.
se j>i visualizza il carattere meno
se j=i visualizza il carattere asterisco
se i<j visualizza il carattere più
i0
falso
i< n
vero
j0
falso
j<n
vero
falso
j<i
falso
+
j =i
vero
vero
*
j  j+1
Esci
a capo
i  i+1
Fondamenti di Informatica CDL in Ingegneria Gestionale - A.A. 2011-2012
fine