Informatica Generale
Susanna Pelagatti
email: [email protected]
Ricevimento:
Mercoledì ore 14.30-17.30
presso
Dipartimento di Informatica, Via Buonarroti, 2
stanza 346 DE Tel. 050.2212.772
o per posta elettronica
Pagina web del corso:
http://www.di.unipi.it/~susanna/IG02/
1
La scorsa lezione …
• Abbiamo introdotto le strutture dati array
• Abbiamo iniziato a vedere un esempio di utilizzo
di array : l’algoritmo per ordinare N numeri
• Oggi :
– completiamo l’esempio
– parliamo di record
– riprendiamo il discorso della codifica dei programmi
in C
2
Usiamo gli array ...
• Costruiamo una versione dell’algoritmo che
ordina N numeri che usa un array
int X[N]per memorizzare i numeri della
sequenza da ordinare
• Vediamo prima 2 sottoalgoritmi
– leggi_Na che legge i numeri da ordinare e li
inserisce nell’array X
– max_Na che trova il valore del massimo
numero in X e la sua posizione
3
Esempio di leggi_Na
Sequenza di numeri da leggere : 8, 1, 9, 7
quindi
Inizialmente X è vuoto
Passo 1, leggo il primo numero
N=4
X=
posizione
I=0 Leggo 8 e lo scrivo nella posizione 0, cioè X[0]=8
0
1
2
3
8
Passo 2, leggo il secondo numero
I=1
Leggo 1 e lo scrivo nella posizione 1, cioè X[1]=1
8
1
8
1
9
8
1
9
Passo 3, leggo il terzo numero
I=2
Leggo 9 e lo scrivo nella posizione 2, cioè X[2]=9
Passo 4, leggo il quarto numero
I=3
Leggo 7 e lo scrivo nella posizione 3, cioè X[3]=7
Termina
I=4, quindi I< N non è più verificata
7
4
Input : vuoto
(void)
Inizio
Leggi il valore di
N
Strutture dati:
Int X[N] // la sequenza
I=0
Si
Sottoalgoritmo per la
lettura di N numeri
(leggi_Na)
No
I<N?
Fine
Leggi il nuovo
numero in X[I]
Output :
Int X[N] // la sequenza letta
Int N
// la sua lunghezza
I=I+1
5
Esempio di max_Na
Trova il valore m del massimo in X e
la sua posizione Imax ,
la lunghezza di X è N=4
Passo 1, esamino X[0], I=0
m=8
X=
8
1
posizione
Imax = 0 (Valore e posizione del massimo
trovato fra gli elementi già esaminati)
9
7
0
1
2
3
8
1
9
7
8
1
9
7
8
1
9
7
8
1
9
7
Passo 2, esamino X[1], I=1
m=8
Imax = 0
Passo 3, esamino X[2], I=2
m=9
Imax = 2
Passo 4, esamino X[3], I=3
m=9
Termina
Imax = 2
I=4, quindi I< N non è più verificata
6
Input:
Int X[N],
Int N
Sottoalgoritmo per la
trovare il massimo
di N numeri in un array
(max_Na)
Inizio
m = X[0]
Imax = 0, I = 0
Si
Strutture dati:
Int X[N] // la sequenza
No
I<N?
Fine
Si
No
m > X[i]
?
I=I+1
Output:
Int m // il valore del massimo
Int Imax
// l’indice del massimo
m = X[i], Imax = I
7
Ordinare N numeri interi
8
7
3
1
N=4
Max_Na = 8 in posizione 1
Scambio la posizione 1 e 4
1
7
3
8
N=3
Max_Na = 7 in posizione 2
Scambio la posizione 1 e 3
1
3
7
8
N=2
Max_Na = 3 in posizione 2
Nessuno scambio
1
3
7
8
N=1
Termina
1
3
7
8
8
Ordinare N numeri interi (2)
• Algoritmo ordina_Na
1. Leggi il valore di N dall’esterno
2. Leggi gli N numeri della sequenza nell’array X
3. Trova il maggiore (m, imax) fra i primi N numeri
dell’array X (con max_Na)
4. Scambia fra loro X[imax] e X [N]
5. Considera adesso solo i primi N-1 numeri dell’array
(N=N-1)
6. Se N = 1 continua, altrimenti vai al passo 3
7. Stampa X, termina
9
Input : vuoto
(void)
(X,N)=leggi_Na()
Inizio
Si
N>1?
(m,I) = max_Na(X,N)
T = X[N]
X[N] = X[I]
X[I] = T
N = N-1
Lung=N
No
Stampa(X,Lung)
Strutture dati:
Int X[N]
// la sequenza
Fine
Output : vuoto (void)
Scambio
dei due valori
DF per il problema del
ordinare di N numeri
(ordina_Na)
10
Record
• Finora abbiamo visto solo variabili di tipo
intero
• Normalmente è possibile avere variabili di
tipo diverso che rappresentano informazioni
di natura diversa :
– interi, reali …
– caratteri (‘a’,’b’, …)
– sequenze di caratteri (dette stringhe, ”gatto ”,
”oggi piove !” …)
• I record sono aggregati di variabili di tipo
diverso e permettono di definire nuovi tipi
11
Record (2)
• A cosa possono servire…...
– A rappresentare le schede della biblioteca
stringa
Nome Autore
stringa
Cognome Autore
Titolo
intero
Scaffale
Posizione
Costo
stringa
intero
reale
… altre informazioni …..
Campi del record
12
Record (3)
• Il tipo record scheda espresso in C
struct scheda {
char nome[100]; //stringa di al più
//100 caratteri
char cognome[100];
char titolo[300];
int scaffale;
int posizione;
double costo ;
} ;
13
Record (4)
//Come dichiaro che voglio
//una variabile di tipo ‘scheda’
struct scheda nuovo_libro;
// come assegno valori ai diversi campi
nuovo_libro.nome =”Jorge";
nuovo_libro.cognome =”Amado";
nuovo_libro.titolo =”Dona Flor e i
suoi due mariti";
nuovo_libro.scaffale =”8";
nuovo_libro.posizione =”356";
14
Record (5)
• Si possono definire array di record
– questo può servire, ad esempio a definire
l’insieme delle schede di una biblioteca:
struct scheda archivio[100000]
– possiamo quindi formalizzare il nostro
algoritmo ‘stupido’ per la ricerca nello
schedario
15
Input :
struct
scheda
archivio
Ricerca ‘stupida’
(ricerca)
Inizio
Leggi Nome, Cognome
e Titolo del libro cercato
Strutture dati:
struct scheda archivio
// l’array di schede
I=0
Si
No
I < 100000 ?
Fine
archivio[I].nome = Nome
archivio[I].cognome = Cognome
archivio[I].titolo = Titolo
?
Si
No
I=I+1
Fine
Non l’ho trovata!
Output :
la scheda cercata
e un valore (si/no) che
dice se c’è
L’ho trovata!
16
DF e programmi
DF
Codifica in un linguaggio di
programmazione (C, Java etc)
Programma
Input : programma
Compilatore
Eseguibile
Output : rappresentazione comprensibile alla macchina
17
DF e programmi (2)
• L’eseguibile dipende dalla macchina che
dobbiamo specializzare (es. processore
Intel, o processore SUN), dal sistema
operativo (es. Windows, Linux …) e dal
linguaggio usato (es: C o Java)
• Gli eseguibili di alcuni linguaggi (come
Java) contengono operazioni complesse che
non possono essere eseguite direttamente!
• In questo caso si utilizza un programma
interprete (es Java Virtual Machine) che
realizza le operazioni elementari complesse
18
DF di max
Inizio
Leggi x e y
d=x-y
Si
No
d>0?
Scrivi ‘max è y’
Scrivi ‘max è x’
Fine
19
DF e programmi : max in C
main() /* calcola max */
{
int x, y, d; //def. Delle variabili
scanf ("%d %d”, &x, &y) ; //lettura x,y
d = x - y ;
if (d > 0)
//scrittura risultati
printf (”il max è %d”, &x) ;
else
printf (”il max è %d”, &y) ;
return ;
//terminazione
}
20
Leggi N
Inizio
Leggi i primi due numeri x1 e x2
e memorizzali nelle variabili a e b
m = max(a,b)
Si
I=2
No
I<N?
I=I+1
Leggi il nuovo
numero in a
Scrivi ‘max è m’
Fine
DF per il problema del
massimo di N numeri
(seconda versione)
m = max(a,m)
Supponiamo N almeno 2
21
DF e programmi : max_N in C (1)
main() /* calcola max_N */
{ int m, i, a, b;
i = 2 ;
scanf ("%d %d”, &a, &b);
m = max(a,b);
while (i < N) { scanf ("%d ”, &a) ;
m = max(a,m); }
printf (”il max è %d”, &m) ;
return ;
}
22
DF e programmi : max_N in C (2)
int max(int x, int y)
/* sottoprogramma che calcola max */
{ int d;
d = x - y ;
if (d > 0) return x;
else return y;
}
23
DF e programmi : ordina_Na in C
main() /* calcola max_N */
{ int m, i, t, X[N], N, lung;
leggi_Na (N, X) ;
m = X[0];
lung = N ;
while (N > 1) { max_Na(X,N,&m,&i) ;
t = X[N];
X[N] = X[i] ;
X[i] = t ;
N = N - 1 ; }
stampa_Na (X,lung) ;
return ;}
24
Esercizi proposti
• Dare il DF per il sottoalgoritmo stampa_Na
• Trovare un algoritmo (e fornire il DF) per i
seguenti problemi :
– trovare la somma dei primi K numeri (K letto
dall’esterno)
– trovare la media di una sequenza di numeri positivi
(la sequenza viene letta dall’esterno e si interrompe
al primo numero negativo letto)
– leggere una data (un record che indica giorno, mese
ed anno) e stampare il numero di giorni passati
dall’inizio dell’anno
25