Pseudo codice
Paolo Bison
Fondamenti di Informatica 1 A.A. 2004/05
Universit`a di Padova
Pseudo codice
linguaggio testuale
mix di linguaggio naturale ed elementi linguistici con sintassi ben definita e semantica univoca
elementi
espressioni
istruzioni
Espressioni
elementi del linguaggio la cui valutazione fornisce un determinato valore
costituite, in prima approssimazione, da operandi ed operatori
espressioni matematiche
consideriamo
operandi a valore intero
operatori aritmetici (espressioni numeriche) + − × /
operatori di confronto (espressioni logiche/predicati)
= 6= > ≥ < ≤
Come si scrivono le espressioni?
sintassi
descrizione di come si scrivono espressioni corrette combinando simboli base (cifre, operatori, parentesi)
notazioni
infissa op1 oper op2
5 + 3 / 9
postfissa op1 op2 oper
5 3 + 9 /
prefissa oper op1 op2
/ + 5 3 9
Come si valutano le espressioni? - I
TEST: Qual’è il valore di
5 + 3 / 2 1. 6
2. 6.5 3. 4
4. potrebbe essere uno qualunque dei punti 1, 2, 3.
5. nessuna delle precedenti è la risposta esatta
Come si valutano le espressioni? - II
semantica
regole per valutare una espressione
significato degli operatori
ordine di valutazione
Significato degli operatori
operazione matematica associata ai simboli di operatore
+ addizione
− sottrazione
× moltiplicazione
/ divisione - intera
- decimale
Ordine di valutazione
la sequenza in cui vengono applicati gli operatori agli operandi
ordine di scrittura
da sx a dx
5 + 3 / 2 = 4
da dx a sx
5 + 3 / 2 = 6
priorità predefinite
×,/ valutati prima di +,−
ordine esplicito
parentesi ( )
Do it yourself
Sviluppare un algoritmo per la conversione di
espressioni (senza parentesi) dalla notazione infissa a quella postfissa.
3+5*8-7 → 358*+7-
7/2*3-6+4*9 → 72/3*6-49*+
Istruzioni
elementi del linguaggio che definiscono le azioni da svolgere
istruzioni base
struttura sequenziale
struttura condizionale
struttura iterativa
istruzione di assegnazione
Struttura sequenziale
sequenza di passi da eseguirsi uno di seguito all’altro
sintassi
passi scritti uno per riga
semantica
passi eseguiti uno alla volta
ciascun passo è eseguito una sola volta e nessuno è omesso o ripetuto
l’ordine di esecuzione è quello di scrittura
algoritmo termina con il termine dell’ultimo passo
struttura rigida
esecuzione non può essere modificata
Es. struttura sequenziale
somma delle radici quadrate di tre numeri J, K, L calcola √
J calcola √
K calcola √
somma le tre radici quadrate L
Struttura di selezione
permette di eseguire istruzioni differenti al verificarsi o meno di una condizione (espressione logica)
sintassi
if predicato istr_1
else istr_2
semantica
se il predicato è vero si esegue istr_1, altrimenti istr_2
variante ad una sola via
if predicato
istr_1
Es. struttura di selezione
dati due numeri,sommare al primo il valore assoluto del secondo
if il secondo numero è negativo sottrai il secondo dal primo
else somma il primo con il secondo
Indentazione
rientranza a dx nella scrittura delle istruzioni
per indicare quali istruzioni sono sotto il controllo di una clausola if o else
dati quattro numeri A,B,C,D sommare A con B e moltiplicare C con D se A maggiore di B
if A > B
somma A con B
moltiplica C con D 6≡ if somma A con B A > B
moltiplica C con D
Gerarchie di selezione
sequenze in cascata di costrutti di selezione: if annidati (nested)
scelta del massimo tra tre numeri X,Y e Z
if X > Y
if X > Z
X è max
else
Z è max
else
if Y > Z
Y è max
else
Z è max
numero di vie selezionabili arbitrario ma finito
Es. ricerca
ricerca di un indirizzo in un archivio dato il nome leggi nome della prima scheda
if è il nome cercato estrai indirizzo
else leggi nome della seconda scheda
if è il nome cercato estrai indirizzo
else
if ...
non è possibile esprimere algoritmi la cui lunghezza
dipenda da fattori esterni
Strutture iterativa
ripetizione di istruzioni per un numero arbitrario, ma finito di volte
ciclo (loop)
permette di descrivere una elaborazione di durata
indeterminata con un numero finito di istruzioni
Tipi di iterazioni
definita
durata determinata e conosciuta prima dell’esecuzione
termine garantito
indefinita
durata indeterminata
termine dipende dal verificarsi o meno della
condizione di terminazione
Ciclo while
sintassi
while predicato istr
semantica
- si valuta il predicato - se vero
- si esegue istr
- e si torna a valutare il predicato altrimenti termina l’esecuzione
iterazione indefinita
Es. while
ricerca in un archivio di schede
leggi nome da prima scheda
while nome non è quello cercato e vi sono ancora schede
leggi nome da scheda successiva
if hai trovato il nome
leggi indirizzo da scheda
ciclo errato se archivio vuoto
Ciclo repeat
sintassi
repeat espressione istr
semantica
- si valuta l’espressione che deve ritornare un valore intero
- si esegue istr per un numero di volte pari a tale valore
iterazione definita
Es. repeat
stampa di 100 asterischi *
repeat 100
stampa *
Variabile
elemento che può assumere un qualunque valore ma che in ogni momento dell’esecuzione è associato ad uno ed uno solo valore
nome (identificatore)
sequenza di caratteri alfanumerici ris x0 st
etichetta di un contenitore ris -150
x0 3.67
st hello
operandi in espressioni
condivisione di dati tra istruzioni
Operazioni su variabile
accesso al valore attuale x0+ris-7
ris 34
x0 -10
valore dell’espressione: 17
modifica del valore associato
istruzione di assegnazione
Istruzione di assegnazione
sintassi
id ← espressione a
a