Paolo Bison Fondamenti di Informatica 1 A.A. 2003/04...

Pseudo codice

Paolo Bison

Fondamenti di Informatica 1

A.A. 2003/04

Universita di Padova

Pseudo codice, Paolo Bison, A.A. 2003-04, 2003-09-30 – p.1/38

Pseudo codice

� linguaggio testuale

� mix di linguaggio naturale ed elementi linguistici la cuisintassi e semantica sono ben definite ed univoche

� elementi base

�

struttura sequenziale

�

struttura di selezione

�

strutture iterative

�

variabile ed istruzione di assegnazione


Struttura sequenziale

� sequenza di passi da eseguirsi una di seguito all’altra

� 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 fissa e non può essere modificata dallecircostanze


Esempio - I

� fare la somma di due numeri

leggi primo numeroleggi secondo numerosomma il primo con il secondostampa risultato


Struttura di selezione

� permette di eseguire istruzioni differenti al verificarsi omeno di una condizione

� sintassiif condizione

then istr_1else istr_2

� semanticase la condizione è vera si esegue istr_1, altrimentiistr_2

� una sola viaif condizione

then istr_1

� esecutore deve essere in grado di interpretare evalutare la condizione Pseudo codice, Paolo Bison, A.A. 2003-04, 2003-09-30 – p.5/38

Esempio - II

� dati due numeri,sommare al primo il valore assolutodel secondo

leggi primo numeroleggi secondo numeroif il secondo numero è negativo

then sottrai il secondo dal primoelse somma il primo con il secondo

stampa risultato


Gerarchie di selezione

� sequenze in cascata di costrutti di selezione (ifnidificati)

� scelta del massimo tra tre numeri X,Y e Zif X � Y

thenif X � Z

then X è maxelse Z è max

elseif Y � Z

then Y è maxelse Z è max

� numero di vie selezionabili arbitrario ma finito

� indentazione Pseudo codice, Paolo Bison, A.A. 2003-04, 2003-09-30 – p.7/38

Esempio - III

� ricerca di un indirizzo in un archivio dato il nome

leggi nome della prima schedaif è il nome cercato

then estrai indirizzoelse

leggi nome della seconda schedaif è il nome cercato

then estrai indirizzoelse

if ......

� non è possibile esprimere algoritmi la cui lunghezzadipenda da fattori esterni


Strutture iterative

� ripetizione di istruzioni per un numero arbitrario, mafinito di volte

� ciclo (loop)

� permettono di descrivere una elaborazione di durataindeterminata con un numero finito di istruzioni

� iterazione definita

�

durata determinata e conosciuta primadell’esecuzione

�

termine garantito

� iterazione indefinita

�

durata indeterminata

�

termine dipende dal verificarsi o meno dellacondizione di terminazione Pseudo codice, Paolo Bison, A.A. 2003-04, 2003-09-30 – p.9/38

Repeat until

� sintassirepeat

istruntil condizione

� semantica- si esegue istr- si valuta la condizione- se falsa si riesegue istr

altrimenti termina l’esecuzione

� condizione di terminazionedeve assicurare che l’iterazione termini correttamente


Esempio - IV

� ricerca in un archivio

leggi primo nomerepeat

if è il nome cercatothen estrai indirizzoelse

leggi nome successivountil trovi il nome o elenco esaurito

� ciclo errato se archivio vuoto


while do

� sintassiwhile condizione do

istr

� semantica- si valuta la condizione- se vera

- si esegue istr- si torna a valutare la condizione

altrimenti termina l’esecuzione


Esempio - V

� ricerca del max in un elenco di numeri

stabilisci come max il primo numerowhile elenco non è esaurito do

esamina numero successivoif questo � max finora trovato

then stabilisci questo come max

6 -1 7 4 10


repeat N times

� quando si conosce il numero di iterazioni primadell’esecuzione del ciclo

� sintassirepeat N times

istr

� semantica- si esegue N volte istr


Variabile

� elemento che può assumere un qualunque valore mache in ogni momento dell’esecuzione è associato aduno ed uno solo valore

� nome (identificatore)sequenza di caratteri alfanumericiris x0 st

� etichetta di un contenitoreris -150x0 3.67st hello


Variabili tipizzate

� variabile associata ad un tipo che la vincola adassumere valori solo da un dato insieme

� tipo definisce:

�

un insieme di valori che la variabile può assumere

�

un insieme di operazioni che possono essereapplicate alla variabile

� esempio

integer idx0


Operazioni su variabile

� accesso al valore attualestampa risx0+ris-7

� modifica del valore associato

�

operazioni di letturaleggi x0

�

istruzione di assegnazione


Istruzione di assegnazione

� sintassiid espressione a

� semanticaal termine dell’esecuzione alla variabile id è associatoil valore ottenuto valutando l’espressione

� esempio

�

ris 34

� prima: ris -150

� dopo: ris 34

aaltri simboli := =


Ordine di esecuzione

n mm r

� m rn m

� datim 17 n 23 r 31

n mm r

m 31 n 17 r 31

m rn m

m 31 n 31 r 31


Scambio tra due variabili

� scambio di valori tra m e n

�

ERRATO

� scambio direttom nn m

�

CORRETTO

� uso di una terza variabile per salvare il valore diuna delle due da scambiaret mm nn t


Variabili indicizzate - Array

� variabili associate ad un insieme di M elementi

� singoli elementi accessibili attraverso un indicecompreso tra 0 e M-1

� notazionedata la variabile array AA è l’insieme di tutti gli elementi

A �� è l’elemento il cui indice è dato dal valore di ��

A A � A � � ��

� operazioni

�

variabile B A B A + C

�

singolo elemento B � A � - C�

� multidimensionali D ��


Esempio - V

� creazione di un array contente i primi n numeri interi

i 1while i n do

A � ii i + 1


Somma di n numeri

calcolo della somma dei primi N numeri interi positivi

leggi ns 0i 1while i n do

s s + ii i + 1

stampa s


Somma di n numeri pari

calcolo della somma dei primi N numeri interi positivi pari

leggi ns 0i 1while i n do

if resto di i/2 = 0 thens s + i

i i + 1stampa s


Resto della divisione

calcolo del resto della divisione tra due interi n e m, con m

� n, avendo a disposizione l’operazione di divisione intera(/)

leggi n e mr m - ((m / n) � n)stampa r


Fattoriale

n! = n �(n-1) �(n-2) � ... �1 n 0 e con 0!=1

Ciclo da n a 1 che moltiplica tutti i numeri tra n e 1

leggi ni 1while n � 1 do

i i � nn n - 1

stampa i


Massimo di un array

Dati un array A di n elementi interi trovare quello massimo

leggi n e A � (

� � �� )max A �

i 2while i n do

if max A � thenmax A �

i i + 1stampa max


Massimo Comun Divisore - I

Dati due numeri m,n � 0 trovare MCD

� metodo 1Sia m n, con ciclo da 2 a n si verifica quali sono inumeri che dividono esattamente sia m che n. Il MCDè il massimo di tali numeri.Nota: un numero è divisibile per un altro se il restodella divisione è zero.


Massimo Comun Divisore - II

� algoritmo 1

leggi m,nif m n then scambia m con ni 2mcd 1while i n do

if resto di m/i = 0 thenif resto di n/i = 0 then

if i � mcd thenmcd i

i i + 1stampa mcd


Massimo Comun Divisore - III

� metodo 2 - Metodo di EuclideSia m n, qualunque numero che divide sia m che ndivide anche il resto della divisione m/n

m = qn + rm - qn = r 0q !k - qq� k = rk(q ! - qq� ) = r

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


Massimo Comun Divisore - IV

� algoritmo 2

leggi m,nif m n then scambia m con nr resto di m/nwhile r � 0 do

m nn rr resto di m/n

stampa n


Massimo Comun Divisore - V

� metodo 3 - Metodo di Euclide (senza divisione)Se m=n il MCD è m, altrimenti se m �n m diventa m-naltrimenti è n che diventa n - m, e si ricontrollal’eventuale uguaglianza di m con n

� algoritmo 3leggi m,nwhile m � n do

if m � nthen m m - nelse n n - m

stampa m


Numero primo

Dato un numero intero n �0 si dica se è primo

Ciclo che verifichi che N non sia divisibile da un numerotra n/2 e 2.

leggi ndiv n / 2repeat

r resto di n / divdiv div - 1

until r �0 o div � 1if r �0

then stampa che n è primoelse stampa che n non è primo


Numeri primi

Si trovino tutti i numeri primi compresi tra 1 e N

Ciclo da 1 a N di verifica se il numero è primo o no.

leggi Ni 1repeat N times

if i è numero primothen stampa i

i i + 1

i è numero primodiv i / 2repeat

r resto di i / divdiv div - 1

until r �0 o div � 1if r �0

then vero, i è primoelse falso, i non è primo


Equazioni di II grado - I

ax

+ bx + c = 0leggi a,b e cif a=0 e b=0 then segnala eq. de-genere

else calcola radici

calcola radiciif a=0 then eq. I grado

else eq. II grado

eq. I gradox - c / astampa x

eq. II gradob

- 4acif

0 thenradici immaginarie

else radici realiPseudo codice, Paolo Bison, A.A. 2003-04, 2003-09-30 – p.35/38

Equazioni di II grado - II

radici immaginariez "

parte reale - b / 2aparte immaginaria z / 2astampa parte reale e parte immagi-nariaradici realiif � 0 then x1 - b / 2a

x2 x1else S

x1 (-b + S)/2ax2 (-b - S)/2a

stampa x1 e x2


valore di un polinomio

Calcolare, per un dato valore di x, il polinomio

#� � #� $ � � $ �� # � #&%

leggi x,n e A � (

� � '� � � �)pot 1val A%

i 1while i n do

val A � � pot + valpot pot � xi i + 1

stampa val


Do it yourself

�

Minimo comune multiplo di due numeri m e n

�

Calcolo della radice quadrata intera di un numero ( ) 0; la radiceintera è quel numero * che soddisfa le condizioni * + , ( e- * . / 0 + ) (

�

Data una serie di numeri calcolarne media e varianza

�

Data una serie di numeri trovarne il valore mediano *; * è quelvalore, presente nella serie, tale per cui il 50% dei numeri è

, *.

�

Calcolo approssimato dell’integrale definito

1213

4 -65 0

come areasottesa da

4 -65 0

tra 587 e 589 .

�

Calcolo dei coefficienti dell’equazione della retta :5 . ;=< .?> @ A

dati due punti (x7 ,y7 ) e (x9 ,y9 )


Paolo Bison Fondamenti di Informatica 1 A.A. 2003/04...

Documents

Transcript of Paolo Bison Fondamenti di Informatica 1 A.A. 2003/04...