S. Petrarca: Informatica e Telematica

Algoritmi e strutture dati

Stefano Petrarca
Conservatorio S. Cecilia - Roma

Rappresentazione degli algoritmi tramite pseudo-codice

Flow-chart

Pseudo-codice

Pseudo-codice (per anglofili...)

Inizia

input a

input n

s 0

se (a != 0) AND (n != 0) allora

inizio

esegui

s s + a

n n - 1

mentre n != 0

fine

output s

Fine

Begin

input a

input n

s 0

if (a != 0) AND (n != 0) then

begin

s s + a

n n - 1

while n != 0

end

output s

End

Nota: L'operatore AND serve per costruire un'espressione logica collegando due o più proposizioni logiche: l'intera espressione è vera se e solo se sono tutte vere le proposizioni collegate da AND, altrimenti è falsa.

Strutture dati

Variabili scalari

Possono contenere tipi di dati semplici.

Un tipo di dato rappresenta la forma e la dimensione dell'informazione associata

I tipi di dati semplici (o scalari) sono, ad esempio:

numeri interi con e senza segno
numeri reali
caratteri (lettere, segni di interpunzione, cifre, caratteri speciali)
booleani: valori relativi a espressioni logiche; una variabile di tipo booleano può assumere solo valori Vero o Falso (TRUE - FALSE)

Pertanto una variabile scalare può contenere un singolo dato di tipo scalare

Un intero è più piccolo di un real, mentre un booleano è più piccolo di un intero, etc.

Nei linguaggi di programmazione "classici" abbiamo:

interi: 16 bit
reali: 32 bit
caratteri: 8 bit
booleani: basterebbe un bit...

Un singolo carattere, ad esempio la lettera A, viene indicato, in ambito informatico, con 'A'

Se x è una variabile di tipo carattere, allora x 'A' è una valida assegnazione.

Variabili strutturate

Possono contenere una molteplicità di dati di diverso tipo, scalari o, a loro volta, strutturati

Il tipo strutturato più semplice è l'array unidimensionale (detto anche vettore)

Un vettore è un insieme di dati dello stesso tipo disposti in sequenza

Ogni elemento del vettore è accessibile tramite un indice che ne individua univocamente la posizione all'interno della sequenza

Il singolo elemento, situato alla posizione k, dell'array a si indica con a[k]

Un array può essere schematizzato nella seguente maniera (nell'es. abbiamo un vettore con 4 elementi interi)

Indice	Valore
0	7
1	5
2	2
3	8

Nell'esempio precedente, se chiamiamo a il vettore, a[1] vale 5 a[3] vale 8, etc.

Il numero di elementi di cui è composto un array viene chiamato dimensione dell'array

Un vettore i cui elementi sono caratteri viene anche chiamato stringa.

Una stringa costante, ad esempio la parola Ciao, viene indicata con "Ciao"

Esercizi

- Descrivere in pseudo-codice gli algoritmi svolti fino ad ora

- Valutare le seguenti espressioni riferendoci al vettore precedentemente schematizzato

a[k] - a[k-1] , nel caso in cui k = 3
a[k+1] + a[k-1] , nel caso in cui k = 1
a[k-1] * a[k-2] , nel caso in cui k = 1
a[k+1] / a[k+2] , nel caso in cui k = 2

- Sviluppare i seguenti algoritmi

Riempimento tramite input esterno di un vettore
Media di 5 numeri introdotti in un vettore
Ricerca dell'elemento massimo presente in un vettore
Ricerca di un numero, introdotto da input, all'interno di un vettore
Inversione dell'ordine in cui sono posti gli elementi di un vettore
Ricerca della parola "OK" all'interno di una stringa (non facile...)

Pagina iniziale ________________ Matematica ________________ Programma ________________ Bibliografia