Algoritmi di base

(1)

Elementi di Informatica

Prof. G. A. Di Lucca - Univ. del Sannio 1

Algoritmi di base

{...

MAX=Num; // il primo valore della sequenza è //il ‘primo’ massimo attuale

{ ... // inizia un ciclo per analizzare // gli altri valori nella sequenza

if (Num>MAX) MAX=Num; // aggiorna il massimo attuale // quando trovato un valore // maggiore nella sequenza ....

} // fine ciclo ....

printf (“Massimo = %d”, MAX);

....

}

... Ricerca del valore massimo in una sequenza di valori (ad es. di numeri interi)

Algoritmi di base

{....

MIN=Num; // il primo valore della sequenza è //il ‘primo’ minimo attuale

{... // inizia un ciclo per analizzare // gli altri valori nella sequenza

if (Num<MIN) MIN=Num; // aggiorna il minimoattuale // quando trovato un valore // minore nella sequenza ....

} // fine ciclo ....

printf (“Minimo = %d”, MIN);

...

}

... Ricerca del valore minimo in una sequenza di valori (ad es. di numeri interi)

(2)

{....

Cerca = ... // Inizializza variabile con valore da cercare // e contare occorrenze nella sequenza

....

Volte=0; // Inizializza contatore occorrenze { ... // inizia un ciclo per analizzare // i valori nella sequenza

if (VAL==Cerca)

Volte=Volte+1; // Incrementa contatore occorrenze // ogni volta che il valore è // trovato nella sequenza ...

} // fine ciclo

printf (“Valore %d presente %d volte \n", Cerca, Volte);

....

}

Algoritmi di base

... Ricerca e conteggio occorernze di un dato valore in una sequenza (ad es. di numeri interi)

Algoritmi di base

{....

scanf (“%d”, &N); //legge estremo superiore sommatoria Sommatoria = 0; // Inizializza valore della sommatoria for (i=1;i<=N;i++) // ciclo for per calcolare la sommatoria

Sommatoria = Sommatoria + i;

// Incrementa valore di Sommatoria // con il valore i

printf (“Sommatoria = %d \n", Sommatoria);

}

... Calcolo sommatoria dei numeri interi da 1 a N:

(3)

Algoritmi di base

{....

scanf (“%d”, &N); //legge estremo superiore produttoria Produttoria = 1; // Inizializza valore della produttoria for (i=2;i<=N;i++) // ciclo for per calcolare la produttoria

produttoria = produttoria * i;

// Incrementa valore di produttoria // con il valore i

printf (“Produttoria= %f \n", produttoria);

}

... Calcolo produttoria dei numeri interi da 1 a N:

Algoritmi di base

{....

scanf (“%d”, &N); //legge cardinalità della serie Sommatoria=0; // Inizializza valore della sommatoria for (i=1;i<=N;i++) // ciclo for per calcolare la sommatoria {...

scanf (“%d”, &numero); //legge un numero della serie Sommatoria = Sommatoria + numero;

// Incrementa valore di Sommatoria // con il valore di numero

...

}

printf (“Sommatoria = %d \n", Sommatoria);

}

... Calcolo sommatoria di una serie di N numeri interi (immessi da tastiera) ...

(4)

Algoritmi di base

... qualche considerazione/osservazione ...

... serie/sequenze ‘costruite’ usando una sola variabile per i valori della sequenza ...

... se si volessero elaborare/stampare tutti i valori della serie/sequenza dopo che sono stati tutti immessi ?

... ad esempio secondo un certo ordinamento ...

... se si volesse fare una nuova elaborazione sulla stessa serie/sequenza di valori?

... una serie/sequenza è un insieme di più valori,

... uso di una variabile per ciascun valore ... ???

... quante se non nota la lunghezza della sequenza

Necessità di strutture dati che consentono di registrare un determinato insieme di valori .

Tipi strutturati

…. l’informazione può essere decomposta in tipi più semplici ...

…. più informazioni aggregate fra loro in base ad una relazione per costituire un’informazione più complessa

Es:

data (giorno, mese, anno)

numero complesso (parte reale, coefficiente immaginario) generalità anagrafiche (cognome, nome, data nascita, indirizzo)

Un tipo strutturato è caratterizzato da:

• tipi componenti

• costruttore

(5)

COSTRUTTORI DI TIPO

Prodotto cartesiano

tipo T = cartesiano (t1, t2, .... , tn)

t1, t2, …, tn : tipi componenti, non necessariemente tutti uguali

permette di formare n-ple ordinate di elementi dei tipi t1, t2, …, tn

un tipo strutturato si ottiene componendo insieme i tipi componenti attraverso appositi operatori che consentono di

‘costruire’ il tipo strutturato due costruttori:

• prodotto cartesiano

• sequenza

COSTRUTTORI DI TIPO

Prodotto cartesiano

… due modi per definire il tipo strutturato:

• indicando solo i tipi componenti tipo T = cartesiano (t1, t2, .... , tn)

tipo complesso = cartesiano(reale, reale) tipo data = cartesiano(intero, intero, intero)

tipo persona = cartesiano(stringa caratteri, stringa caratteri, data)

• indicando attributi e tipi componenti

tipo T = cartesiano (a1:t1, a2:t2, .... , an:tn)

… attributo a1 di tipo t1, … , … an di tipo tn

tipo complesso: cartesiano (ParteReale:reale, CoeffImm: reale) tipo data: cartesiano (giorno: intero, mese:intero, anno:intero)

tipo persona = cartesiano(Cognome: stringa caratteri, Nome: stringa caratteri, Datanascita: data)

(6)

Sequenza

tipo T = sequenza (t1, t2, ..., tn)

dove t1 = t2 = … = tn tipi componenti tutti uguali COSTRUTTORI DI TIPO

Es.;

stringaCaratteri = sequenza (carattere) parola = sequenza (carattere)

numero decimale = sequenza (cifra decimale) capitolo = sequenza (paragrafi)

coda = sequenza (persone)

Variabili di Tipo strutturato

Una informazione (variabile) di tipo strutturato va dichiarata, come qualsiasi altra variabile, indicandone il tipo ed il nome

<nome_tipo_strutturato> <nome_variabile>;

Es.:

tipo complesso = cartesiano (ParteReale:reale, CoeffImm: reale) complesso Numero;

dichiarazione della variabile di nome Numero di tipo complesso

(7)

Funzione di Accesso

… per potere accedere ad uno degli elementi costituenti la struttura:

1. tramite l’indicazione di un attributo:

Es.: indicando con W una informazione del tipo strutturato TS,

tipo TStrutt = cartesiano (a1:t1, a2:t2, .... , ak:tk) TStrutt W; // dichiarazione della variabile W di tipo TSrutt

W.ah

indica l’accesso all’elemento con attributo ah (il componente h- esimo) della variabile W di tipo TStrutt

Es.:

tipo complesso = cartesiano(ParteReale:reale, CoeffImm: reale) complesso Numero; // dichiarazione variabile Numero di tipo complesso

Numero.ParteReale // per accedere alla componente ParteReale

Funzione di Accesso 2. tramite l’indicazione della posizione:

…. Uso di un’informazione indice ...

… indice: informazione di un tipo ordinato ...

Detta A una variabile del tipo strutturato:

A [indice]

Si riferisce alla componente di A che occupa la posizione indicata da indice

Es.:

tipo GraduatoriaConcorso = cartesiano(persona, persona, …, persona) GraduatoriaConcorso A;

A[3] indica il componente in terza posizione

(8)

Array monodimensionali

Tipo strutturato praticamente presente in tutti i linguaggi come tipo strutturato primitivo

• Costruttore: Cartesiano

• Tipi componenti: tutti dello stesso tipo

• Funzione d’accesso: per posizione

tipo array monodimensionale = cartesiano(T 1,T 2, … ,T n) con T 1 = T 2 =...= T n = T

bisogna:

specificare il tipo T dei componenti

definire la dimensione (o cardinalità) dell’array

Array monodimensionali

… concettualmente ...

• un nome ‘collettivo’ associato ad un insieme ordinale di elementi tutti dello stesso tipo

• ciascun elemento è direttamente accessibile attraverso una informazione (l’indice) che ne individua la

posizione nella struttura Es.:

classifica campionato: array di squadre graduatoria concorso: array di persone

prenotati ad un esame universitario: array di studenti

(9)

Array monodimensionali

… un modello interpretativo ...

A

[1]

[2]

[3]

[4]

[5]

Valori dell’indice [6]

(posizione componente)

Nome array A[3]

Componente in terza posizione

Accesso diretto ai componenti

Array monodimensionali

Valori dell’indice (posizione componente)

A

[1]

[2]

[3]

[4]

[5]

[6]

34 281 87 623 15 839

Valori elementi array

… non confondere il valore di un elemento dello array con l’indice che esprime la sua posizione in esso …

A[1] = 34 A[3] = 87 A[5] = 15 A[2] = 281 A[4] = 623 A[6] = 839

(10)

Array monodimensionali Parametri caratterizzanti un array:

• Strutturali:

• Nome dello array

• Tipo componente

• Cardinalità: numero (massimo) elementi costituenti lo array

Array monodimensionali

Parametri caratterizzanti un array:

• di utilizzo:

• Indice: appartenete ad un tipo ordinato, indica la posizione di un elemento nello array.

Può essere espresso tramite:

• una costante (es. A[4], quarto elemento dello array)

• una variabile (es. A[I], i-esimo elemento dello array)

• una espressione (es. A[c+d*e],

(elemento dello array nella posizione corrispondente al valore di c+d*e)

• Riempimento: numero di elementi effettivamente utilizzati N.B. non confondere Riempimento con Cardinalità Deve sempre essere :

Riempimento  Cardinalità

(11)

Array monodimensionali

La dichiarazione di una variabile di tipo array è fatta specificando:

• tipo componente

• nome dello array (nome della variabile)

• cardinalità dello array (racchiusa tra parentesi quadre)

<tipo> <nome_array> [<cardinalità>]

Es.:

INT A[10];

FLOAT SpesaSettimanale[7];

Array monodimensionali

ad un elemento di un array è possibile assegnare un valore tramite operazioni di:

• lettura da tastiera Es.:

read(“%d”, A[3]);

legge il valore da assegnare al terzo elemento dello array A

• calcolo e assegnazione Es.:

A[4] = C;

se: C = 73 => A[4] = 73

A[I] = 5;

se: I = 9 => A[9] = 5

A[I] = f * 9 + d;

se: I = 4 , f = 3, d = 8 => A[4] = 35

(12)

Array monodimensionali

un elemento di un array può essere utilizzato in operazioni:

• di stampa Es.:

write(“%d”, A[3]);

stampa il valore da contenuto nel terzo elemento dello array A

• di calcolo e assegnazione Es.:

C = A[4] ;

B= f *9 + d - A[I] ;

• condizionali Es.:

if (A[I] > 7) ……

[1]

[2]

[3]

[4]

[5]

[6]

A

21 18 22 5 8

6

B=A[2] + A[4];

printf(“%d --- %d\n”, A[1], A[5]); 18 --- 21

A[1]= 7; =>

A[4]= 41;

[1]

[2]

[3]

[4]

[5]

[6]

21 7 22

5 41

6

=> B=22 + 8=30

Array monodimensionali

……

x = 3;

if (A[x] != 24) printf(“VERO”);

……

VERO Indici

Valori elementi array

A[3] = 5 <> 24 =>

(13)

Il tipo stringa di caratteri

• Una stringa di caratteri è una sequenza di caratteri

ASCII, atti a rappresentare una parola, una frase, un testo

• E’ un tipo strutturato costruito con l’operatore sequenza

• Una delle operazioni tipiche sulle stringhe di caratteri è la concatenazione di due o più stringhe, tipicamente

indicata con il simbolo //.

Es.

A=“calcolatore “ B=“elettronico”

C=A//B=“calcolatore elettronico”

Array Bidimensionali

tipo array Bidimensionale= cartesiano(T 1,T 2, … , T n) con T 1 = T 2 =...= T n = T

Tipo T = cartesiano (q1, q2, …, qm) q1=q2= ….. =qm

…. Ovvero un array bidimensionale è un array in cui ciascun elemento è a sua volta un array

… array tutti della stessa dimensione e tipo

(14)

Array Bidimensionali

A

Nome array

1 2 3 4 5 6

1 2 3 4 5 6 7

Valori dell’indice (posizione componente)

Array Bidimensionali

… la posizione di ciascun elemento è individuata da 2 indici …

… il primo indice, indica la riga … 1

2 3 4 5 6

1 2 3 4 5

[1,1] [1,2] [1,3] [1,4] [1,5]

[2,1] [2,2] [2,3] [2,4] [2,5]

[6,1] [6,2] [6,3] [6,4] [6,5]

A[4,2]

(15)

Array Bidimensionali

… la posizione di ciascun elemento è individuata da 2 indici …

1 2 3 4 5 6

1 2 3 4 5

23 47 63 96 8

27 66 23 44 567

42 28 34 125 47

A[4,2] = 57

57

A[6,3] = 34

… il primo indice, indica la riga …

… il secondo indice, indica la colonna ...

… ciascuna posizione conterrà un (solo) valore …

Array Bidimensionali

Parametri caratterizzanti un array bidimensionale:

• Strutturali:

• Nome dello array

• Tipo componente

• Cardinalità di riga: numero di righe costituenti lo array

• Cardinalità di colonna: numero di colonne costituenti

lo array

(16)

Array Bidimensionali

Parametri caratterizzanti un array bidimensionale:

• di utilizzo:

• Indice di riga: appartenete ad un tipo ordinato

• Indice di colonna: appartenete ad un tipo ordinato

la coppia ordinata [indice di riga, indice di colonna] indica la posizione di un elemento nello array bidimensionale.

Gli indici possono essere espressi tramite:

• una costante (es. A[4,2], elemento in quarta riga e seconda colonna)

• una variabile (es. A[I, J], elemento in riga i-esima e colonna j-esima)

• una espressione (es. A[c+d*e, k],

(elemento dello array nella riga corrispondente al valore di c+d*e, e k-esima colonna)

Array Bidimensionali

Parametri caratterizzanti un array bidimensionale:

• di utilizzo:

• Riempimento: numero di elementi effettivamente utilizzati

• Riempimento di riga

• Riempimento di colonna

N.B. non confondere Riempimento con Cardinalità Deve sempre essere :

indice riga  Cardinalità riga

indice colonna  Cardinalità colonna Riempimento riga  Cardinalità riga

Riempimento colonna  Cardinalità colonna

(17)

Array Bidimensionali

La dichiarazione di una variabile di tipo array bidimensionale è fatta specificando:

• tipo componente

• nome dello array (nome della variabile)

• cardinalità di riga e di colonna dello array (racchiusa tra parentesi quadre)

<tipo> <nome_array_bidim> [<cardinalità_riga] [cardinalità_colonna>]

Es.:

int A[10] [15];

float Mat[7] [22];

Array Multidimensionali

… generalizzando opportunamente ….

… un array di array di array di array …. Quante sono le dimensioni

… tutti array dello stesso tipo …

… per ciascuna dimensione, tutti array con stessa cardinalità …

… posizione individuata mediante tanti indici quanti sono le dimensioni

… un indice per ciascuna dimensione ...

<tipo><nome_array_multidim>[<card_dim1] [card_dim2>] …[card_dimK]

Es.:

int A[10] [15] [20];

float Multi [7] [22] [30] [45];

(18)

Il tipo record

• Quando si vogliono rappresentare informazioni che sono collezioni di dati diversi,

– ad esempio:

• un libro è una entità composta da un titolo, un autore, un editore, il testo

• Le generalità anagrafiche di una persona: cognome, nome, data di nascita, luogo di nascita, indirizzo attuale

• Il tipo record è usato per rappresentare e gestire queste collezioni di dati,

• Il tipo record permette di raggruppare le diverse informazioni, elementari o strutturate, che caratterizzano la collezione di dati.

Il tipo record

• Il record è un tipo strutturato formato da un

predeterminato numero di campi, ciascuno dei quali può essere un tipo semplice o strutturato

• E’ un tipo strutturato costruito con l’operatore prodotto cartesiano

tipo record = cartesiano(a1:T1, a2:T2, …. , an:Tn)

dove a1, …, an sono i nomi dei campi del record

e T1, … , Tn i rispettivi tipi anche diversi tra loro

(19)

Il tipo record

• dichiarazione in LDP di un tipo record:

record <nome record>=

begin

<nome campo1> :<tipo campo1>;

……

<nome campo_n> : <tipo campo_n>;

end;

Il tipo record

Es.

record anagrafico = begin

cognome:string;

nome:string;

data_nascita: record begin

giorno:integer;

mese: integer;

anno:integer;

end;

indirizzo:string;

end;

Per indicare un campo del record si usa la notazione:

<nome record>.<nome campo>

Es. anagrafico.nome

(20)

Dichiarazione di variabili di tipo record

• E’ simile alla dichiarazione di una qualsiasi altra variabile:

<nome tipo> <nome variabile>;

Es. dichiarazione di una variabile del tipo record anagrafico:

record anagrafico persona;

“persona” è una variabile del tipo record anagrafico

Ciascuna variabile persona è composta dai campi del tipo anagrafico, per accedere ad un campo della variabile si usa la notazione_

<nome_variabile>.<nome_campo>

Es: persona.cognome persona.nome

persona.data_nascita.mese persona.indirizzo

Tipo strutturato File

• Tipo strutturato formato da un insieme di elementi tutti dello stesso tipo

• Gli elementi sono registrati su un supporto di memoria di massa

• Individuato da un nome

• Caratterizzato da un metodo di accesso ai suoi elementi (detti genericamente records)

- File ad accesso Sequenziale - File ad accesso Diretto

(21)

Accesso sequenziale

Per accedere all' N-mo record bisogna accedere agli N-1 record precedenti (nastro)

Accesso diretto

Individuazione ed accesso diretti ad un record tramite:

- o il riferimento alla sua posizione

- o i valori di uno o più campi (detti chiavi)

FILE SEQUENZIALE

• è una sequenza di oggetti tutti dello stesso tipo T …

• ..ed una ulteriore informazione di tipo T detta buffer che indicheremo con f

... il buffer è l’elemento per il transito delle informazioni da/verso il file

• la definizione è completata con le operazioni caratteristiche del tipo file sequenziale

• Operazioni possibili su un file sequenziale:

• Inserimento di un nuovo elemento (WRITEF)

• Lettura degli elementi (READF)

• Riposizionamento all’inizio del file (RESET)

• Riscrittura del file (REWRITE)

• Verifica di fine file (EOF)

(22)

operazione WRITEF(f)

• è una operazione di inserzione che modifica lo stato del file

• inserzione del valore del buffer alla fine di f; il buffer avrà valore indefinito dopo l’operazione

… prima di WRITEF(f) ...

f = f x

… dopo WRITEF (f) ...

f = f ?

a b c d

a b c d x

...una osservazione

• in ogni istante la sequenza di oggetti di un file f può essere vista come concatenazione di altre due sequenze

....una parte sinistra f_s ed una parte destra f_d....

f = f

_s

// f

_d

(23)

operazione READF(f)

non modifica il contenuto del file f, ma quello del buffer con un valore di f ben definito, inoltre... modifica parte ...sinistra..e destra..

f=

f ?

fs fd

… prima di READF(f)...

… dopo READF(f) ...

f f c

fs fd

Nel buffer sarà presente il primo elemento di f_d

a b c d

operazione RESET (f)

• posiziona il buffer sul primo elemento del file la parte sinistra risulterà vuota

… prima di RESET (f) ...

… dopo RESET(f) ... f =

f a fs fd f =

f ?

fs fd

a b c d

(24)

f = f ?

… prima di REWRITE ...

… dopo REWRITE(f) ... f = < >

f ? operazione REWRITE (f)

• cancella gli elementi del file svuotandolo

a b c d

il predicato EOF (f)

E’ usato per verificare se si è raggiunta la fine del file EOF = End Of File

• EOF(f)

• TRUE se la parte destra della sequenza è vuota

• FALSE se non lo è

(25)

Alcune regole

Dopo un RESET sono possibili solo operazioni di READF Dopo un REWRITE sono possibili solo operazioni di WRITEF Non è possibile mescolare/alternare operazioni di WRITEF e READF Generazione di un File:

un REWRITE seguito da una o più operazioni di WRITEF Visita (ispezione/lettura) di un FILE:

un RESET seguito da una o più operazioni di READF, fino alla fine del file