Pseudo codice

Pseudo codice

Paolo Bison

Fondamenti di Informatica A.A. 2007/08

Università di Padova

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.1

Pseudo codice



linguaggio testuale



mix di linguaggio naturale ed elementi linguistici con sintassi ben definita e semantica univoca



elementi



espressioni



istruzioni

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.2

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. dipende

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.5

Come si valutano le espressioni? - II



semantica

regole per valutare una espressione



significato degli operatori



ordine di valutazione

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.6

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 ( )

Espressioni logiche



espressioni che ritornano un valore di verità (vero,falso)



predicati



operatori di confronto

= 6= > ≥ < ≤



esempi

lato quadrato 6= 0

primo numero ≥ secondo numero

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.9

Istruzioni



elementi del linguaggio che definiscono le azioni da svolgere



modifica dati



flusso di esecuzione



istruzioni base



struttura sequenziale



struttura condizionale



struttura iterativa



istruzione di assegnazione

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.10

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 √

L

somma le tre radici quadrate

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, FI07, 2008-01-08 – p.13

Es. struttura di selezione



dati due numeri,sommare al primo il valore assoluto del secondo

if il secondo numero < 0 sottrai il secondo dal primo else

somma il primo con il secondo

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.14

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

ifX>Y ifX>Z

X è max else

Z è max else

ifY>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, FI07, 2008-01-08 – p.17

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

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.18

Tipi di iterazione



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

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.21

Ciclo do while



sintassi do

istr

while predicato



semantica

- si esegue istr

- si valuta il predicato - se vero

si rieseguono i passi precedenti altrimenti

termina l’esecuzione



iterazione indefinita

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.22

Ciclo repeat



sintassi

repeat espressione istr



semantica

- si valuta l’espressione che deve ritornare un valore intero positivo

- si esegue istr per un numero di volte pari a tale valore



iterazione definita

Es. repeat



stampa di 100 asterischi * repeat 100

stampa *

Programmazione strutturata



teorema di Jacopini-Böhm

ogni algoritmo può essere espresso utilizzando solo tre strutture di controllo



struttura sequenziale



struttura di selezione



un ciclo indefinito ( while ) do

istr

while predicato ≡

istr

while predicato istr

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.25

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

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.26

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

aaltri simboli := =



semantica

al termine dell’esecuzione alla variabile id è associato il valore ottenuto valutando l’espressione



esempio



ris ← ³⁴

•

prima: ris -150

•

dopo: ris 34

Significato identificatori nell’assegnazione 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, FI07, 2008-01-08 – p.29

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}

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.30

Scambio tra due variabili



scambio di valori tra m e n



ERRATO

•

scambio diretto m ← ⁿ

n ← ^m



CORRETTO

•

uso di una terza variabile per salvare il valore di una delle due da scambiare

t ← ^m m ← ⁿ n ← ^t

Programma equivalente per repeat



uso di una variabile come contatore

repeat n

istr ≡

_i ← ¹ while _i ≤ ⁿ

istr

_i ← ^{_i + 1}

Algoritmi



moltiplicazione



divisione intera



somma di n numeri



somma di n numeri pari



fattoriale



massimo comun divisore



numero primo



?

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.33

Moltiplicazione

calcolo di m × ^{n, m,n} ≥ 0, come addizioni ripetute m × n = m + m + · · · + m | {z }

n



ciclo repeat ris ← ⁰ repeat n

ris ← ^{ris + m}



ciclo while

ris ← ⁰ i ← ¹ while i ≤ ⁿ

ris ← ^{ris + m}

i ← ^{i + 1}

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 ← ⁰

while m ≥ ⁿ 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 ← ⁰ i ← ¹ while i ≤ ⁿ

s ← ^{s + i}

i ← ^{i + 1}

Somma di n numeri pari

calcolo della somma dei primi n numeri naturali pari 2 + 4 + 6 + ··· + 2(n − 1) + 2n s ← ⁰

i ← ²

while i ≤ ² × ⁿ if i - i / 2 × ^{2 = 0}

s ← ^{s + i} i ← ^{i + 1}

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.37

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 ← ¹

while n > 1

fat ← ^fat × ⁿ n ← ^{n - 1}

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.38

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 ← ^t i ← ²

mcd ← ¹ while i ≤ ⁿ

if m - m / i × ^{i = 0} if n - n / i × ^{i = 0}

if i > mcd

mcd ← ⁱ

i ← ^{i + 1}

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 ≥ ⁰ q

k - qq

k = r k(q

- qq

) = r

Si calcola il resto r di m/n. Se tale resto è zero n è il MCD, altrimenti n e r diventano m e n e si riapplica il passo precedente.

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.41

Massimo Comun Divisore - IV



algoritmo 2 if m < n

t ← ^m m ← ⁿ n ← ^t r ← ^{m - m / n} × ⁿ while r 6= ⁰

m ← ⁿ n ← ^r

r ← ^{m - m / n} × ⁿ

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.42

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= ⁿ

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= ⁰

div ← ^{div - 1}

r ← n - n / div × ^div if div 6= ¹

n è primo

else

?

Cosa produce questo algoritmo ? while n 6= ¹

stampa n

if n - n / 2 × ^{2 = 0} n ← ^{n / 2} else

n ← ⁿ × ^{3 + 1}

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.45

Do it yourself

 Minimo comune multiplo di due numeri m e n

 Calcolo della radice quadrata intera di un numeron>0; la radice intera è quel numeromche soddisfa le condizionim²≤ n^e(m + 1)²> n

 Calcolo approssimato dell’integrale definitoRx₁

x₀ f(x)come area sottesa da f(x)trax0ex1con f(x) > 0perx0≤ x ≤ x^1.

 Calcolo dei coefficienti dell’equazione della rettaax+ by + c = 0dati due punti (x₀,y₀) e (x₁,y₁)

Pseudo codice, Paolo Bison, FI07, 2008-01-08 – p.46