Fondamenti di informatica – A.A. 2013/2014
Laboratorio 3 – Vettori e funzioni
Integrate a partire da slide di
Alberto Quattrini Li 2012/2013
Avvio dei PC






Se non acceso, avviare il PC
Il PC si avvierà in ambiente Windows
Avviare l'applicazione Internet Explorer
Si presenterà una schermata nera: Virtual Desktop
Inserire i propri Codice Persona e Password
Tra le applicazioni che saranno disponibili selezionare NX Client






COME POTETE PORTARVI A CASA IL LAVORO FATTO:
In ambiente Windows aprire l'applicazione Blocco Note
Selezionare il vostro codice scritto in gedit
Pulsante destro del mouse → copia
Andate nel Blocco Note, pulsante destro del mouse → incolla
Inserite una chiavetta nel computer
Copia e incolla dei file nella vostra chiavetta
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
2
Programma di oggi
 Vettori/Matrici
 Funzioni

Funzioni ricorsive
 Esercizi
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
3
Vettori
 Collezione di elementi

Dello stesso tipo

Che condividono lo stesso nome

Memorizzati in zone contigue di memoria
 Sequenza indicizzata di elementi
 Sintassi:

Dichiarazione:
tipo nome_vettore[dimensione];
•
es., int vettore_interi[10];

Accesso ad elemento: nome_vettore[indice]
•
es., vettore_interi[2] = 2;

Inizializzazione vettore: tipo nome_vettore[] =
{elemento1, elemento2};
•
es., int vettore_interi[] = {1, 2, 3, 4, 5}
 Nota bene: gli indici vanno da 0 a dimensione-1
 Il nome del vettore indica la prima area di memoria
4
Nome del vettore (si noti
che tutti gli elementi di
questo vettore hanno lo
stesso nome, c)
c[0]
-45
c[1]
6
c[2]
0
c[3]
72
c[4]
1543
c[5]
-89
c[6]
0
c[7]
62
c[8]
-3
c[9]
1
c[10]
c[11]
6453
78
Numero della posizione di
ogni elemento all’interno
del vettore c (indice)
Figura del Deitel & Deitel
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Vettori di caratteri
5
 Possibile memorizzare sequenza di caratteri (stringhe) tramite vettori
 Inizializzazione:

char string1[] = “prova”;

char string1[]={'p', 'r', 'o', 'v', 'a', '\0'};
•
Notare il carattere '\0' per indicare la fine della stringa
 Acquisizione di una stringa in input

scanf(“%s”, string1);
•
La scanf si “ferma” quando trova uno spazio
 Stampa di una stringa in output

printf(“%s”, string1);
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Vettori di Caratteri – Alcune operazioni in
string.h
6
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
 strlen(char *string);

restituisce un intero contenente la lunghezza della stringa
s
l
a
b
\0
strlen(s) restituisce 3, quindi NON considera il '\0'
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Vettori di Caratteri – Alcune operazioni in
string.h
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
 strcmp(char *s1, char *s2);

confronta la stringa s1 e s2

Restituisce:
•
== 0 se le stringhe sono uguali
•
< 0 se s1 precede alfabeticamente s2
•
> 0 se s1 segue alfabeticamente s2
s1
l
a
b
\0
s2
l
a
b
\0
strcmp(s1, s2) restituisce 0
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
7
Vettori di Caratteri – Alcune operazioni in
string.h
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
 strcmp(char *s1, char *s2);

confronta la stringa s1 e s2

Restituisce:
•
== 0 se le stringhe sono uguali
•
< 0 se s1 precede alfabeticamente s2
•
> 0 se s1 segue alfabeticamente s2
s1
l
a
b
\0
s2
l
c
b
\0
strcmp(s1, s2) restituisce < 0
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
8
Vettori di Caratteri – Alcune operazioni in
string.h
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
 strcmp(char *s1, char *s2);

confronta la stringa s1 e s2

Restituisce:
•
== 0 se le stringhe sono uguali
•
< 0 se s1 precede alfabeticamente s2
•
> 0 se s1 segue alfabeticamente s2
s1
m
a
b
\0
s2
l
c
b
\0
strcmp(s1, s2) restituisce > 0
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
9
Vettori di Caratteri – Alcune operazioni in
string.h
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
 strcmp(char *s1, char *s2);

confronta la stringa s1 e s2

Restituisce:
•
== 0 se le stringhe sono uguali
•
< 0 se s1 precede alfabeticamente s2
•
> 0 se s1 segue alfabeticamente s2
s1
m
a
b
\0
s2
M
a
b
\0
strcmp(s1, s2) restituisce > 0
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
10
Vettori di Caratteri – Alcune operazioni in
string.h
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
ncmp(char *s1, char *s2, int n);
confronta la stringa i primi n elementi di s1 e s2
 str

Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
11
Vettori di Caratteri – Alcune operazioni in
string.h
12
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
 strcpy(char *dest, char *src);

permette di copiare una stringa (src) in un'altra (dest)

Attenzione alle dimensioni delle stringhe!

Dimensione di dest deve essere > di quella della stringa in src
src
l
a
b
dest
strcpy(dest, src)
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
\0
Vettori di Caratteri – Alcune operazioni in
string.h
13
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
 strcpy(char *dest, char *src);

permette di copiare una stringa (src) in un'altra (dest)

Attenzione alle dimensioni delle stringhe!

Dimensione di dest deve essere > di quella della stringa in src
src
l
a
b
\0
dest
l
a
b
\0
strcpy(dest, src)
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Vettori di Caratteri – Alcune operazioni in
string.h
14
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
ncpy(char *dest, char *src, int n);
permette di copiare i primi n una stringa (src) in un'altra (dest) e
 str

poi posiziona il '\0' in dest
src
c
i
a
o
dest
strncpy(dest, src, 3);
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
\0
Vettori di Caratteri – Alcune operazioni in
string.h
15
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
ncpy(char *dest, char *src, int n);
permette di copiare i primi n una stringa (src) in un'altra (dest) e
 str

poi posiziona il '\0' in dest
src
c
i
a
o
dest
c
i
a
\0
strncpy(dest, src, 3);
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
\0
Vettori di Caratteri – Alcune operazioni in
string.h
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
 strcat(char *s1, char *s2);

Concatena s1 e s2

In s1 verrà quindi scritta la stringa s1 seguita dalla s2
s1
c
i
\0
s2
a
o
\0
strcat(s1, s2);
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
16
Vettori di Caratteri – Alcune operazioni in
string.h
17
 Alcune operazioni sulle stringhe sono gestite dalla libreria standard
“string.h”:
 strcat(char *s1, char *s2);

Concatena s1 e s2

In s1 verrà quindi scritta la stringa s1 seguita dalla s2
s1
c
i
a
s2
a
o
\0
strcat(s1, s2);
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
o
\0
Vettori – Ricezione input utente
char string[DIM];
scanf("%s", string);
int vet[DIM];
scanf("%d", vet);
for(i=0; i < DIM; i++){
scanf("%d", &vet[i]);
}
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
18
Matrice
19
 Vettori a più dimensioni
Riga 0
Colonna 0
a[0][0]
Colonna 1
a[0][1]
Colonna 2
a[0][2]
Colonna 3
a[0][3]
Riga 1
a[1][0]
a[1][1]
a[1][2]
a[1][3]
Riga 2
a[2][0]
a[2][1]
a[2][2]
a[2][3]
Figura del Deitel & Deitel
 Sintassi:


Dichiarazione: tipo nome_vd[NUM_RIGHE][NUM_COLONNE];
•
es., int a[3][3];
Accesso agli elementi: nome_vd[indice_riga][indice_colonna];
•
es., a[0][0] = 1;
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Errori logici comuni su vettori/matrice
20
 Accedere ad elementi del vettore/matrice il cui indice supera la dimensione
massima del vettore/matrice
 Inizializzare la stringa omettendo sia la dimensione del vettore che il carattere
nullo di chiusura
 Inizializzare la stringa omettendo il carattere nullo di chiusura e mettendo una
dimensione pari al numero di inizializzatori (escluso il carattere nullo)
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Funzioni
21
 Frammento di codice (modulo) riutilizzabile
 Codice del programma più leggibile e facile da modificare
 Per chi usa una funzione (chiamante), è importante sapere “cosa fa”
(risultato) e non “come lo fa” (implementazione)
 Il chiamante deve passare 0 o più parametri affinché la funzione restituisca
un risultato
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Funzioni - sintassi
24
 Dichiarazione:
tipo_ret nome_funzione(tipo argomento1, tipo argomento2);

void se la funzione non restituisce nessun risultato

es. int somma (int addendo1, int addendo2);
 Definizione:
tipo_ret nome_funzione(tipo argomento1, tipo argomento2){
/* Istruzioni */
/* Restituzione del controllo */
}

es. int somma (int addendo1, int addendo2){
return addendo1+addendo2;
}
 Chiamata: tipo risultato = nome_funzione(argomento1, argomento2);

argomento1, argomento2 si chiamano parametri attuali

Attenzione che i parametri attuali siano dello stesso tipo degli
argomenti formali richiesti come input dalla funzione

es. ris = somma (ad1, ad2);
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Funzioni – passaggio parametri
25
 Per valore

es. int fun(int param);

Viene passata una copia della variabile

La variabile visibile nella funzione chiamante non è modificata
 Per riferimento

Vettori/matrici
• es. int fun(int vet[]);
• es. int fun(int mat[][3]);

Dedicheremo maggiore attenzione al passaggio per riferimento nel
prossimo laboratorio
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Funzione ricorsiva
26
 Funzioni che richiamano se stesse al loro interno (nella definizione)
 Funzione che risolve un caso base
 Quando una funzione ricorsiva viene chiamata vengono eseguiti i seguenti
passi:
Chiamata
funzione
ricorsiva
no
Caso base?
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
sì
Restituisci
valore
ESERCIZI
27
 Potete scaricare gli esercizi dal seguente link:
ftp://ftp.elet.polimi.it/users/Marco.Rocco/
 Scaricate il file esercizi_lab3.pdf

 Vi interromperemo di tanto in tanto per vedere alcuni
aspetti problematici e/o importanti nella risoluzione dei
diversi esercizi proposti
 Verso metà lezione faremo una pausa di 10 minuti
 Comandi utili: cd, ls, pwd,
gcc nomefile.c -o nome_eseguibile
./nome_eseguibile
Evitate di mettere spazi nei nomi dei file
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Problema 1
28
 Definire all'interno del codice un vettore di interi di dimensione DIM,
es. int array[] = {1, 5, 2, 4, 8, 1, 1, 9, 11, 4, 12};
 Chiede all'utente un numero e, tramite ricerca lineare (definita in una
funzione), si ricerchi il numero e si comunichi all'utente se il numero è
o meno presente nel vettore. Nel caso in cui sia presente, si comunichi
la posizione della sua prima occorrenza.
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
29
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
30
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
31
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
32
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
33
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
34
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
35
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
36
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
37
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
38
Problema 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
39
Problema 2
 Dato un vettore di lunghezza DIM, si chieda all'utente, tramite una
funzione, di riempire il vettore con numeri interi.
 Ordinare gli elementi del vettore in modo crescente.
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
42
Problema 2
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
43
Problema 2
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
44
Problema 2
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
45
Problema 2
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
46
Problema 3
48
 Si ricevano in input due stringhe
 Si faccia un confronto per capire quale delle due precede
alfabeticamente l'altra
 Concatenare le due stringhe, posizionandole secondo l'ordine
alfabetico. Verificare che la concatenazione delle due stringhe possa
essere contenuta nel vettore in cui viene salvato (quello della stringa
che alfabeticamente precede l'altra). Nel caso in cui ciò non sia
possibile, copiare solo la parte di seconda stringa per cui vi è spazio
disponibile.
 Modificando la funzione di ricerca lineare scritta per il problema 1,
cercare se nel vettore di caratteri così ottenuto è presente il carattere
'\0' e dire in che posizione si trova. (Se il carattere '\0' non c'è, c'è
qualche problema nel codice)
man strcmp, man strcat, man strncat (tasto q per uscire dalle pagine
man)
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Problema 3
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
49
Problema 3
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
50
Problema 3
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
51
Problema 3
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
52
Problema 3
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
54
Problema 3
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
55
Problema 3
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
56
Problema 3
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
57
Problema 3
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
58
Problema 4
Scrivere un programma che calcoli n! utilizzando una funzione
ricorsiva. Dove n è un numero inserito dall'utente.
●
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
59
Problema 4
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
60
Problema 4
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
61
Problema 4
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
62
Problema 4
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
63
Problema 4
64
Caso base: 0! = 1 e 1! = 1
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Problema 4
65
Caso base: 0! = 1 e 1! = 1
Passo ricorsivo: n! = n * (n-1)!
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Problema 5
70
 Scrivete il codice che permetta di simulare il seguente circuito. Gli
ingressi vengono richiesti all'utente, l'output deve essere prodotto dal
programma.
a
b
c




AND = &
OR = |
XOR = ^
NOT = !
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Problema 6
71
 Scrivere un programma che chieda all'utente se vuole inserire un
numero decimale o un numero binario di 8 bit (inserire gli opportuni
controlli).
 Se il numero inserito è decimale, in una funzione, trasformarlo in
binario di 8 bit e stamparlo
 Se il numero inserito è binario, in una funzione, trasformarlo in numero
decimale e lo stampi
Cosa succede se l'utente inserisce il numero 258? Perchè?
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
Problema 7
 Esercizio basato sulla prima prova in itinere
 gcc nome_file.c -o nome_eseguibile -linizializzazione
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013
72
Problema 8
73
 Scrivere un programma che trovi un numero (inserito da tastiera) in un
vettore, usando la ricerca binaria (definita in una funzione).
Laboratorio di Fondamenti di Informatica – A.A. 2012/2013