Pseudo codice
Paolo Bison
Fondamenti di Informatica 1 A.A. 2004/05
Universit`a di Padova
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.1/44
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= > ≥ < ≤
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.3/44
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
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.5/44
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
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.7/44
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*+
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.9/44
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
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.11/44
Es. struttura sequenziale
somma delle radici quadrate di tre numeri J, K, L calcola √
calcola √ J 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
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.13/44
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
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.15/44
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
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.17/44
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
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.19/44
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
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.21/44
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
Es. repeat
stampa di 100 asterischi *
repeat 100 stampa *
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.23/44
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
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.25/44
Istruzione di assegnazione
sintassi
id ← espressione a
a
altri simboli := =
semantica
al termine dell’esecuzione alla variabile id è associato il valore ottenuto valutando l’espressione
esempio
Significato identificatori
cnt ← cnt + 1
lato destro
accesso al valore corrente
cnt 17
lato sinistro
riferimento al contenitore
cnt 17
risultato
cnt 18
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.27/44
Ordine di esecuzione
n ← m
m ← r 6≡ m ← r n ← m
dati
m 17 n 23 r 31
n ← m
m ← r ⇒ m 31 n 17 r 31
m ← r
n ← m ⇒ m 31 n 31 r 31
Scambio tra due variabili
scambio di valori tra m e n
ERRATO
• scambio diretto m ← n
n ← m
CORRETTO
• uso di una terza variabile per salvare il valore di una delle due da scambiare
t ← m m ← n n ← t
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.29/44
Algoritmi
moltiplicazione
divisione intera
somma di n numeri
somma di n numeri pari
fattoriale
massimo comun divisore
Moltiplicazione
calcolo di m × n, m,n ≥ 0, come addizioni ripetute m × n = m + m + · · · + m | {z }
n
ciclo repeat
ris ← 0
repeat n
ris ← ris + m
ciclo while
ris ← 0 i ← 1
while i ≤ n
ris ← ris + m i ← i + 1
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.31/44
Divisione intera
calcolo di m/n, m ≥ 0, n > 0, come sottrazioni ripetute m/n = q, qn + r = m, q ≥ 0, 0 ≤ r < n
m − n − n − · · · − n
| {z }
q
< n q ← 0
while m ≥ n
m ← m - n
q ← q + 1
Somma di n numeri
calcolo della somma dei primi n numeri interi naturali 1 + 2 + 3 + · · · + (n − 1) + n
s ← 0 i ← 1
while i ≤ n s ← s + i i ← i + 1
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.33/44
Somma di n numeri pari
calcolo della somma dei primi n numeri naturali pari 2 + 4 + 6 + · · · + 2(n − 1) + 2n
s ← 0 i ← 2
while i ≤ 2 × n
if i - i / n × n = 0
Fattoriale
n! =
( n(n − 1)(n − 2) · · · 2 · 1 n > 0
1 n = 0
Ciclo che moltiplica tutti i numeri tra n e 1
1 × n × (n − 1) × (n − 2) × · · · × 2 fat ← 1
while n > 1
fat ← fat × n n ← n - 1
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.35/44
Massimo Comun Divisore - I
Dati due numeri m,n > 0 trovare MCD
metodo 1
Sia m ≥ n, con ciclo da 2 a n si verifica quali sono i numeri che dividono esattamente sia m che n. Il MCD è il massimo di tali numeri.
Nota: un numero è divisibile per un altro se il resto
della divisione è zero.
Massimo Comun Divisore - II
algoritmo 1
if m < n t ← m m ← n n ← t i ← 2
mcd ← 1
while i ≤ n
if m - m / i × i = 0
if n - n / i × i = 0
if i > mcd mcd ← i i ← i + 1
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.37/44
Massimo Comun Divisore - III
metodo 2 - Metodo di Euclide
Dato m ≥ n, qualunque numero che divide sia m che n divide anche il resto della divisione m/n
m = qn + r
m - qn = r ≥ 0
q m k - qq n k = r
k(q m - qq n ) = r
Massimo Comun Divisore - IV
algoritmo 2
if m < n t ← m m ← n n ← t
r ← m - m / n × n
while r 6= 0 m ← n n ← r
r ← m - m / n × n
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.39/44
Massimo Comun Divisore - V
metodo 3 - Metodo di Euclide (senza divisione)
Se m=n il MCD è m, altrimenti se m >n m diventa m-n altrimenti è n che diventa n - m, e si ricontrolla
l’eventuale uguaglianza di m con n
algoritmo 3
while m 6= n
if m > n
m ← m - n
else n ← n - m
Numero primo
Dato un numero intero n >0 si dica se è primo
Ciclo di verifica che n non sia esattamente divisibile da un numero tra n/2 e 2.
div ← n / 2
r ← n - n / div × div
while r 6= 0
div ← div - 1
r ← n - n / div × div
if div 6= 1 n è primo
else n non è primo
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.41/44
?
Cosa produce questo algoritmo ?
while n 6= 1 stampa n
if n - n / 2 × 2 = 0 n ← n / 2
else n ← n × 3 + 1
Terminazione di un algoritmo
H(P,x)
if P(x) termina stampa 1
else stampa 0
G(P,x)
while H(P,x) stampa 1
? H(G,x)
Pseudo codice, Paolo Bison, A.A. 2004-05, 2004-10-13 – p.43/44
