Terza Lezione
Introduzione alla
programmazione lll
Schema di iterazione

Schema di iterazione (ciclo o loop)

Modo conciso per descrivere azioni che devono
essere ripetute
Sub()
Sub()
S
S
C
falso
End Sub
C
vero
vero
End Sub
falso
Schema di iterazione
Nota:
1. I due schemi non sono equivalenti: in un
caso lo schema S è eseguito almeno una
volta e nell’altro potrebbe non essere mai
eseguito
2. La condizione vero/falso può essere
invertita: si parla di iterazione per vero
quando S è eseguito finché la condizione
su C è vera e iterazione per falso nell’altro
caso

Note sullo schema di
iterazione

Quando è necessario eseguire lo stesso
insieme di operazioni più volte si adotta
un particolare schema di iterazione:


una sequenza di azioni di assegnazione
dette istruzioni di inizializzazione
Una iterazione (ripetizione) di una
sequenza di azioni (iterazione) per un
numero specificato di volte
Note sullo schema di
iterazione
Inizializzazione
Inizializzazione
falso
Iterazione
Condizione
di fine ciclo
vero
Condizione
di fine ciclo
vero
falso
Iterazione
Uscita dal ciclo


La condizione di fine ciclo viene
controllata dopo l’esecuzione di ogni
blocco di iterazione
Può essere con controllo in coda al ciclo
o con controllo in testa
Ciclo enumerativo

Un ciclo è detto enumerativo quando è noto
a priori il numero di volte che deve essere
eseguito

Si usa la tecnica del contatore per controllarne
l’esecuzione, si usa cioè una variabile detta
contatore del ciclo che viene inizializzata
opportunamente prima di iniziare il ciclo e poi
viene incrementata (o decrementata) fino a
raggiungere un valore prefissato, permettendo
così di eseguire una iterazione un numero
specificato di volte
Ciclo indefinito

Un ciclo è detto indefinito quando non è
noto a priori il numero di volte che deve
essere eseguito

Questo accade quando la condizione di fine
ciclo dipende dal valore di una o più variabili
che o dipendono dall’interazione con
l’esterno o vengono modificate all’interno
dell’iterazione in modo complesso
Esempio: Diagramma di
flusso
Inizio: ingressi 1,2,1
RADICI:
Diagramma di Flusso
a : float
1
MESSAGGIO:
radici coincidenti = -1
Assegna ad a,b,c i
valori d’ingresso
b : float
2
c : float
Stato della memoria
Metti il valori di
b2-4ac in delta
1
delta : float
0
delta<0?
vero
MESSAGGIO:
“nessuna soluzione”
Fine
falso
delta=0?
vero
MESSAGGIO:
“radici coincidenti=”
-b/2a
falso
MESSAGGIO:
“radici distinte=”
(-b-radice(delta))/2a
(-b-radice(delta))/2a
Esercizi


Ricerca di un elemento in un vettore
Media di un vettore
Soluzione: Trova
Sub()
i=0
i=i+1
V(i)=k
i=100
insuccesso
end
successo
I programmi



Per fare sì che un algoritmo sia effettivamente
utilizzabile da un esecutore automatico occorre
eliminare le ambiguità circa la codifica dei dati e
l’interazione con gli esseri umani
In generale durante la stesura di un programma ci
si deve preoccupare dei limiti nell’intervallo di
rappresentazione dei numeri, della durata non nulla
delle operazioni, ecc.
La soluzione integrata di queste problematiche e di
quelle dell’algoritmo in sé risulta complessa e
richiede alta competenza
D. Il programma


Disegnato il diagramma di flusso e quindi
delineato in tutte le sue parti l’algoritmo
non resta che tradurlo in un programma
che il calcolatore sarà in grado di eseguire
Il programma verrà scritto usando un
linguaggio di programmazione (ad es. C,
Java, Matlab, ecc.)
Linguaggi di
programmazione

Linguaggi di Basso Livello.


Sono
linguaggi
di
programmazione
caratterizzati da istruzioni molto elementari
(ad es. l’Assembler). Richiedono uno sforzo
di codifica maggiore da parte del
programmatore.
Linguaggi di Alto Livello.

Sono linguaggi di programmazione in cui ad
ogni istruzione corrisponde un insieme di
azioni più articolato. Richiedono uno sforzo
di codifica inferiore.
Esempio

Il linguaggio L1 mette a disposizione i comandi:





Aggiungi_una_unità_al_dato_A
Leggi_dato_A
Leggi_dato_B
Esegui_per <numero di volte>
Il linguaggio L2 mette a disposizione i comandi:



Leggi_dato_A
Leggi_dato_B
Somma <addendo, addendo2>
Esempio (segue)

Vogliamo scrivere un programma per la somma di
due numeri memorizzati rispettivamente nei registri
A e B.
In L1:
Leggi_dato_A
Leggi_dato_B
Esegui_per B volte:
Aggiungi_una_unità_al_dato_A

In L2:
Leggi_dato_A
Leggi_dato_B
Somma (A,B)
L2 è un linguaggio di livello più alto rispetto a L1,
perché offre al programmatore la possibilità di
usare istruzioni che sono meno “vicine” al modo i
cui lavora il processore.
Il linguaggio macchina



Il processore è in grado è in grado di riconoscere
(e quindi di eseguire) solo programmi scritti in un
proprio linguaggio di basso livello.
Ogni modello di processore (es: Intel, Pentium,
Motorola, PowerPC) ha un proprio linguaggio
macchina diverso da quello degli altri processori.
Un programma scritto in un linguaggio diverso dal
linguaggio macchina deve essere quindi tradotto
nel linguaggio che il processore sa individuare
Linguaggi di
programmazione



Invece di codificare algoritmi in linguaggi
macchina si utilizzano linguaggi ad alto
livello.
Le istruzioni dei linguaggi ad alto livello sono
facilmente comprensibili ai programmatori.
Compilatore: (programma che) traduce
automaticamente un programma ad alto
livello in linguaggio macchina.
Linguaggi di alto livello

Per facilitare la stesura dei programmi sono
stati definiti linguaggi di programmazione di
alto livello che



permettono di descrivere le soluzioni dei
problemi ad un livello di astrazione di poco
inferiore a quanto visto fino ad ora per gli
algoritmi
permettono di descrivere le operazioni di
ingresso/uscita
sono traducibili automaticamente in linguaggio
macchina
Diversità dei linguaggi

Sono stati sviluppati diversi linguaggi


I linguaggi si caratterizzano per



Fortran, Lisp, Cobol, Basic, Pascal, C, C++, Java, Prolog
sintassi: l’insieme delle regole che specificano come
comporre istruzioni ben formate
semantica: l’insieme delle regole che specificano come
associare ad una istruzione una azione da compiere
La diversità fra i vari linguaggi può consistere nella
sintassi (le stesse azioni vengono descritte con
termini diversi) o nella semantica
L’arte della programmazione

La soluzione di un problema tramite un
programma è un procedimento che non
si esaurisce solo nello scrivere linee di
codice in un dato linguaggio di
programmazione, ma comprende una
fase di progetto che precede e una di
verifica che segue la scrittura del codice
L’arte della programmazione







Definizione del problema
Algoritmo per la soluzione del problema
Codifica
Debugging
Validazione
Documentazione
Manutenzione
Definizione del problema

Definizione degli ingressi e delle uscite




quali variabili
quale dominio per ogni variabile
Risoluzione delle ambiguità
Scomposizione in problemi più semplici
Algoritmo


Soluzione in pseudocodice
Soluzione in diagramma a blocchi
strutturato
Codifica

Traduzione dell’algoritmo in istruzioni
del linguaggio di programmazione
Debugging
Correzione degli
semantici:
 Errori sintattici


errori
sintattici
e
espressioni non valide o non ben formate
nel linguaggio di programmazione
Errori semantici

Comportamento
aspettative/alla
programmatore
non
aderente
intenzionalità
alle
del
Validazione


Test su tutte le condizioni operative del
programma
Caso degli input estremi (vettori di
dimensioni 0 o 1, variabili nulle, file
vuoti, ecc.)
Documentazione

Inserimento di commenti esplicativi
nelle varie parti del programma per
facilitarne la comprensione dopo molto
tempo dalla sua stesura per terze
persone
Manutenzione

Modifica del programma per soddisfare
il cambiamento delle specifiche con cui
deve operare
Commenti

L’importanza dei commenti e della
documentazione:

i programmi possono essere utilizzati più
volte nel corso di tempi lunghi (mesi, anni)



fare cambiamenti (aggiunta di caratteristiche)
risolvere errori
documentare il programma serve per
rendere chiaro ed evidente lo scopo delle
varie parti del codice
Scrittura del programma:
nozione di variabile




Come si indirizzano le celle di memoria?
Invece di usare gli indirizzi fisici si usano dei
nomi simbolici (es. x, y, nome, …) che
vengono mappati n indirizzi fisici attraverso
la fase di compilazione
Le variabili vanno dichiarate all’inizio del
programma (celle diverse, nomi diversi)
Valore di una variabile = contenuto corrente
della cella di memoria
associata alla
variabile
Scrittura del programma:
nozione di costante



Per esprimere direttamente valori prefissati
(cioè che non devono essere modificati dal
programma) si utilizzano le costanti
Una costante è una rappresentazione
simbolica di un numero, stringa, ecc. (es. 1,
“ciao”, 3.14, ecc.)
Il set di costanti disponibile dipende dal
linguaggio di programmazione
Scrittura del programma:
espressioni



Le espressioni servono per rappresentare
calcoli a livello simbolico
Un’espressione può coinvolgere nomi di
variabili, costanti, operatori aritmetico-logici,
ecc.
Es.
3+4
x+y-1 (dove x è una variabile)
x>0 and y>1
Programma VBA


La sintassi di un programma consiste di due blocchi
Dichiarazione di variabili e costanti:



Const pi As Single = 3,14, nome As String= “Beatrice”
Dim x As Integer, y As String, z As Variant
Sono liste di dichiarazioni introdotte rispettivamente
dalla keyword const e dim
Sequenza di istruzioni racchiusa tra le parole
chiave Sub (nome()) … End Sub e separate dal
punto e virgola “;”
Esecuzione di un
programma

Qual è il significato
programma?




(semantica)
di
un
Trasformazione da Input iniziale a Output finale
Un programma deve essere eseguito per poter
calcolare la trasformazione InputOutput
L’esecuzione modifica lo stato del programma.
Si parla di stato iniziale, corrente e finale
L’esecuzione dipende dalla semantica dei
singoli costrutti
Lettura e scrittura


Le operazioni di lettura e scrittura servono
per ottenere valori in input (es. tastiera) o
fornire valori in output (es. video)
Assumiamo che input e output siano
sequenze di valori:


write(Variabile): aggiunge il valore corrente di
Variabile all’output
read(Variabile): toglie il primo valore della lista
input e lo assegna a Variabile
Assegnamento

Si utilizza per assegnare il valore corrente di
un’espressione ad una variabile



Variabile = Espressione
Se nello stato corrente Espressione si valuta
in val allora Variabile varrà val dopo
l’esecuzione dell’assegnamento
Es. x=x+1
L’espressione x+1 va valutata nello stato
corrente. Il risultato dell’espressione è
assegnato nuovamente a x.
Istruzione condizionale

Sintassi:

If Condizione Then Lista Istruzioni1
Else Lista Istruzioni2
End If
Condizione = Espressione booleana
Se la condizione si valuta vero si esegue il
ramo then, altrimenti
vero
falso
si esegue il
Condizione
ramo else
Lista
Istruzioni1
Lista
Istruzioni2
Esempi
Leggi da tastiera Leggi due numeri, Trova il massimo
e scrivi su video: sommali e stampa tra 2 numeri:
il risultato:
Sub Es3()
Sub Es1()
Dim s As String
read(s)
write(s)
End Sub
Sub Es2()
Dim x As Integer, y
Dim x As Integer, y As Integer
As Integer, somma
read(x)
As integer
read(y)
read(x)
If x>y Then
read(y)
write(x)
somma=x+y
Else write(y)
write(somma)
End If
End Sub
End Sub
Istruzione ciclica

Sintassi:

Do While Condizione
Lista Istruzioni
Loop
Lista
Istruzioni
viene
eseguita
fintantoché
Condizione si valuta in vero.
Quando
Condizione
si
valuta in falso si passa
all’istruzione seguente del
programma.
- Iterazione
Condizione
vero
Lista
Istruzioni
falso
Esempio: somma di k
numeri
Problema: leggere k e quindi calcolare la somma di k
valori letti dall’input.
Memorizziamo k, la somma e i valori letti V1, V2, … ,Vk


poiché si usa ogni Vi una sola volta, bastano 3 variabili: k, x ed S
x manterrà il valore Vi corrente, S la somma progressiva
Sub Es4()
Dimr k As Integer,x As Integer,S As Integer
read(k)
S=0
Do While k>0
read(x)
S=S+x k=k-1
Loop
write(S)
End Sub
Esecuzione del while








Inizialmente: val(x),val(k)=indefiniti, val(S)=0
Si legge il valore 3: val(k)=3
Poiché val(k)>0, si entra nel ciclo
Si legge il primo valore in input V1 su cui fare la
somma e si memorizza in x
Si calcola S=S+x e si decrementa k
Quindi, dopo l’esecuzione delle istruzioni dentro il
ciclo, val(x)=3, val(S)=3, val(k)=2
Si prosegue con il ciclo fino a che val(k)=0
A questo punto si esce dal ciclo e si scrive il valore
finale di S
Esempio: Calcolo MCD

Calcolare il massimo comun divisore tra
due numeri interi letti da input,
utilizzando l’algoritmo di Euclide:



mcd(m,n)=m=n se n=m
mcd(m,n)=mcd(m-n,n) se m>n
mcd(m,n)= mcd(m,n-m) se n>m
Algoritmo di Euclide


Leggo m e n
(*) Fino a che m diverso da n




se m>n allora sottraggo n ad m
se n>m allora sottraggo m ad n
torno a (*)
Quando m=n stampo, ad esempio, n
Es. Calcolo MCD
Sub Es5()
Dim m As Integer,n As Integer
read(m)
read(n)
Do While m<>n
If m>n Then
m=m-n
Else
n=n-m
End If
Loop
write(n)
(Nota: a questo punto n=m!)
End Sub
Strutture dati complesse


Oltre a variabili di tipo intero, stringa, ecc.
può essere molto utile utilizzare dati
strutturati (ad es. liste, insiemi, ecc.)
Molti
linguaggi
di
programmazione
forniscono vari tipi di dato, quali:




array
record
list
Nel linguaggio didattico LP abbiamo solo
array e record
Array




Un array (vettore) rappresenta una sequenza di
celle consecutive contenenti dati omogenei (es.
interi)
Una variabile V di tipo array denota la sequenza di
celle
Per accedere direttamente alla cella i-esima si
utilizza il suo indice i come segue: V(i)
Sintassi dichiarazione:


Dim NomeVarArray(N) As Integer (N costante)
Nelle espressioni, assegnamenti, ecc. si utilizza
poi:

NomeVarArray(Exp) dove Exp è un espressione che si
valuta in un valore da 0…N-1
Esempio: Array
Leggere k<=10 valori e
stamparli in ordine inverso:
Dobbiamo leggere V1, … ,Vk,
memorizzarli e poi stamparli in
ordine Vk, … , V1.
Usiamo un array A di N>k
posizioni per memorizzare i
dati in input.
Dopo aver memorizzato i dati,
li scriviamo scorrendo l’array
dall’indice k all’indice 1.
Sub
Dim A(10) As Integer
Dim i As Integer, k As Integer
read(k)
i=1
Do While i≤k
read(A(i))
i=i+1
Loop
i=k
Do While i>0
write(A(i))
i=i-1
Loop
End Sub
Record


Tipo di dato per gestire dati strutturati di tipo
eterogeneo; ogni dato viene chiamato campo del
record
Sintassi:


Variabile: record
Campo1: Tipo1;
…
CampoN: TipoN;
end
Per accedere ai campi di un record si utilizza:

Variabile.Campoi (rappresenta l’i-esimo campo)
Esempio di record
Coordinate
var Punto:record x,y:int end;
z:int;
Punto.x=3;
Punto.y=2;
z=Punto.x*Punto.y;
Compilatore e Loader

Un compilatore è un programma che traduce
un programma scritto in linguaggio ad alto
livello in un programma scritto in linguaggio
macchina


Un compilatore produce quindi un programma
eseguibile (Es. .exe in Windows)
Il loader è il programma che carica un
programma in linguaggio macchina in
memoria centrale ( e quindi mappa indirizzi
logici in indirizzi fisici)
Come funziona la
compilazione

Un compilatore (che abbia anche la
funzione di loader) deve:



riconoscere la sintassi del linguaggio ad alto
livello
associare uno spazio in memoria centrale per
poter gestire le variabili dichiarate nel
programma
tradurre i costrutti di alto livello in sequenze di
istruzioni in linguaggio macchina