Informatica Generale

1

Informatica GeneraleSusanna Pelagatti email: [email protected]

Ricevimento: Mercoledì ore 14.30-17.30presso Dipartimento di Informatica, Via Buonarroti, 2stanza 346 DE Tel. 050.2212.772o per posta elettronica

Pagina web del corso: http://www.di.unipi.it/~susanna/IG02/

2

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

3

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

4

Esempio di leggi_Na

8

Inizialmente X è vuoto

Passo 1, leggo il primo numero

I=0 Leggo 8 e lo scrivo nella posizione 0, cioè X[0]=8

Termina

Sequenza di numeri da leggere : 8, 1, 9, 7 quindi N=4

Passo 2, leggo il secondo numero8 1I=1 Leggo 1 e lo scrivo nella posizione 1, cioè X[1]=1

8 1 9 7

Passo 3, leggo il terzo numero

I=2 Leggo 9 e lo scrivo nella posizione 2, cioè X[2]=9 8 1 9

Passo 4, leggo il quarto numero

I=3 Leggo 7 e lo scrivo nella posizione 3, cioè X[3]=7

X =

0 1 2 3posizione

I=4, quindi I< N non è più verificata

5

I < N ?

Inizio

Fine

Si No

Leggi il nuovo numero in X[I]

Sottoalgoritmo per lalettura di N numeri (leggi_Na)

Leggi il valore di N

I = 0

I = I + 1

Strutture dati: Int X[N] // la sequenza

Input : vuoto (void)

Output : Int X[N] // la sequenza lettaInt N // la sua lunghezza

6

Esempio di max_Na 8 1 9 7

8 1 9 7

Passo 1, esamino X[0], I=0

m = 8 Imax = 0

Termina

Trova il valore m del massimo in X ela sua posizione Imax ,la lunghezza di X è N=4

Passo 2, esamino X[1], I=1 8 1 9 7

8 1 9 7

Passo 3, esamino X[2], I=2 8 1 9 7

Passo 4, esamino X[3], I=3

X =

0 1 2 3posizione

I=4, quindi I< N non è più verificata

(Valore e posizione del massimo trovato fra gli elementi già esaminati)

m = 8 Imax = 0

m = 9 Imax = 2

m = 9 Imax = 2

7

I < N ?

Inizio

Fine

Si No

Sottoalgoritmo per latrovare il massimodi N numeri in un array(max_Na)

Imax = 0, I = 0

I = I + 1


m = X[0]

Input: Int X[N],Int N

Output: Int m // il valore del massimoInt Imax // l’indice del massimom > X[i]

?

Si

No

m = X[i], Imax = I

8

Ordinare N numeri interi

8 7 3 1

1 3 7 8

1 7 3 8

N=4 Max_Na = 8 in posizione 1

Scambio la posizione 1 e 4


Scambio la posizione 1 e 3


Nessuno scambio1 3 7 8

Termina1 3 7 8

N=1

9

Ordinare N numeri interi (2)• Algoritmo ordina_Na

1. Leggi il valore di N dall’esterno2. Leggi gli N numeri della sequenza nell’array X3. 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 37. Stampa X, termina

10

N > 1 ?

Inizio

Fine

Si No

(X,N)=leggi_Na()

(m,I) = max_Na(X,N)

DF per il problema delordinare di N numeri(ordina_Na)


T = X[N]

X[N] = X[I]

Input : vuoto (void)

Stampa(X,Lung)

X[I] = T

N = N-1

Lung=N

Output : vuoto (void)

Scambiodei due valori

11

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

12

Record (2)• A cosa possono servire…...

– A rappresentare le schede della biblioteca

Nome Autore

Cognome Autore

Titolo

Scaffale

Posizione

… altre informazioni …..

stringa

stringa

stringa

intero

intero

Campi del record

Costo reale

13

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 ;} ;

14

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";

15

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

16

I < 100000 ?

Inizio

Fine

Si No

Ricerca ‘stupida’ (ricerca)

I = 0

I = I + 1

Strutture dati: struct scheda archivio // l’array di schede

Input : struct schedaarchivio

Output : la scheda cercata e un valore (si/no) che dice se c’è

Leggi Nome, Cognome e Titolo del libro cercato

archivio[I].nome = Nome archivio[I].cognome = Cognome

archivio[I].titolo = Titolo?

Si Fine

No

L’ho trovata!

Non l’ho trovata!

17

DF e programmiDF

Codifica in un linguaggio diprogrammazione (C, Java etc)

Programma

Compilatore

Input : programma

Output : rappresentazione comprensibile alla macchina

Eseguibile

18

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

19

DF di max

d > 0 ?

Inizio

Fine

Leggi x e y

Si No

d = x - y

Scrivi ‘max è x’ Scrivi ‘max è y’

20

DF e programmi : max in Cmain() /* calcola max */{int x, y, d; //def. Delle variabili scanf ("%d %d”, &x, &y) ; //lettura x,yd = x - y ;if (d > 0) //scrittura risultati printf (”il max è %d”, &x) ; else printf (”il max è %d”, &y) ;return ; //terminazione}

21

I < N ?

Inizio

Fine

Leggi i primi due numeri x1 e x2e memorizzali nelle variabili a e b

Si No

Leggi il nuovo numero in a

Scrivi ‘max è m’

m = max(a,b)

m = max(a,m)

DF per il problema delmassimo di N numeri (seconda versione)

Leggi N I = 2

I = I + 1

Supponiamo N almeno 2

22

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 ;}

23

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;}

24

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 ;}

25

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

Informatica Generale

Documents

Transcript of Informatica Generale