Corso di Programmazione 1
a.a.2007/2008
Prof.ssa Chiara Petrioli
Corso di Laurea in Informatica
Università degli Studi “La Sapienza”
(lezioni 12-15)
Puntatori e ricorsione
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Aritmetica dei puntatori
I puntatori sono degli operandi validi per le
espressioni aritmetiche (insieme limitato di
operatori aritmetici possono essere applicati a
puntatori), le espressioni di assegnamento e le
espressioni di confronto
Devono però essere puntatori allo stesso tipo di dato
– un puntatore
potrà essere incrementato e
decrementato con gli operatori ++ o --, ad un
puntatore potrà essere sommato o sottratto un intero
(operatori +, -,-=, +=). Infine ad un puntatore potrà
essere sottratto un secondo puntatore.
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Aritmetica dei puntatori per operare
sui vettori
int i;
int v[100];
int * vPtr;
for (i=0; i<100;i++)
v[i]=i;
vPtr=&v[0];
0
1
2
… 98 99
3000
3000
vPtr
vPtr poteva anche essere inizializzato
Scrivendo vPtr=v;
In quale locazione di memoria si trova v[1]? Ed il generico elemento v[i]?
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
v
Operatore sizeof
sizeof(nome_di variabile o tipo di dato o costante)
È l’operatore che consente di determinare quante celle di
memoria sono associate ad un certo tipo di dato
printf(“sizeof(char)=%d\n”
“sizeof(short)=%d\n”
“sizeof(int)=%d\n”
“sizeof(long)=%d\n”
“sizeof(float)=%d\n”
“sizeof(double)=%d\n”
“sizeof(long double)=%d\n”,
sizeof(char),sizeof(short),sizeof(int),sizeof(long),
sizeof(long),sizeof(float),sizeof(double),
sizeof(long double));
sizeof(char)=1
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
sizeof(short)=2
sizeof(int)=2
sizeof(long)=4
sizeof(float)=4
sizeof(double)=8
sizeof(long double)=10
Aritmetica dei puntatori per operare
sui vettori
int i;
int v[100];
for (i=0; i<100;i++)
v[i]=i;
vPtr=&v[0];
0
1
2
… 98 99
3000
3004
3000
vPtr
Supponendo che il numero di celle associate ad un
Intero sia 2…
vPtr+=2 fa puntare vPtr a v[2]
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
v
Aritmetica dei puntatori per operare
sui vettori
int i;
int v[100];
for (i=0; i<100;i++)
v[i]=i;
vPtr=&v[0];
0
1
2
… 98 99
v
3000
3002
3004
vPtr
Supponendo che il numero di celle associate ad un
Intero sia 2…
vPtr-- fa puntare vPtr alla posizione precedente del vettore,
v[1] (stessa cosa scrivendo vPtr-=1)
Infatti in questo caso la variabile puntatore viene decrementata
di una quantità di celle pari a quelle che servono per memorizzare
Prof.ssa
Chiara Petrioli
-- corso
di
il tipo di dato 
in modo
da far
puntare
all’elemento precedente
programmazione 1, a.a. 2006/2007
del vettore
Aritmetica dei puntatori per operare
int i;
sui vettori
int v[100];
0 1 2 … 98 99
Un confronto tra puntatori
int ha
*vPtr;
senso solo per puntatori
puntano ad elementi
3000
int che
*vPtr2;
diversi dello stesso vettore
può adi<100;i++)
esempio essere
for e(i=0;
usato per controllare quale
dei due elementi puntati ha
v[i]=i;
3198
vPtr2
Indice maggiore
3000
vPtr
vPtr=&v[0];
che il numero di celle associate ad un
vPtr2=&v[99]; Supponendo
Intero sia 2…
v
x=vPtr2-vPtr;
Assegna ad x il numero di elementi del vettore compresi
tra l’elemento puntato da vPtr2 e vPtr (infatti il valore delle
L’aritmetica dei differenza
puntatori ha
senso
con gli elementi
di undivettore
altrimenti
viene
normalizzato
al numero
celle necessarie
Chiaradello
Petrioli --stesso
corso di tipo siano immagazzinate in
Non si può assumere
cheProf.ssa
variabili
per contenere
un
intero)in
questo caso 99
programmazione 1, a.a. 2006/2007
celle consecutive di memoria
Puntatori e vettori
notazione con puntatore
e indice
0
1
2
… 98 99
v
3000
vPtr[4] e *(vPtr+4)
sono anche notazioni
equivalenti
3000
vPtr
notazione con
puntatore e offset
v==&v[0]
Se vPtr==v
v[4] e *(vPtr+4) sono due notazioni equivalenti per
far riferimento al valore del quinto elemento del vettore
Prof.ssa
Chiara
Petrioli -- corso
di
Attenzione: il nome del vettore
è un
puntatore
costante
punterà sempre alla
programmazione 1, a.a. 2006/2007
Prima posizione del vettore, non può essere modificato
Un esempio
#include <stdio.h>
b[0]=10
main()
b[1]=20
{
b[2]=30
int i, offset,*(bPtr+0)=10
b[ ]={10,20,30,40};
b[3]=40
*(bPtr+1)=
20
int *bPtr=b;
*(bPtr+2)=
30
printf(“stampa
del vettore
con notazione con indici”);
*(bPtr+3)= 40
for (i=0;i<=3;i++)
printf(“b[%d]=%d\n”,i,b[i]);
printf(“stampa del vettore con notazione con puntatore e
offset”);
for (offset=0;offset<=3;offset++)
printf(“*(bPtr+%d)=%d\n”,offset,*(bPtr+offset));
printf(“stampa del vettore con notazione con puntatore e
indice”);
for (i=0;i<=3;i++)
printf(“bPtr[%d]=%d\n”,i,bPtr[i]);
return 0;
bPtr[0]=10
}
bPtr[1]=20
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
bPtr[2]=30
bPtr[3]=40
Alcuni esercizi sulle stringhe…
Si scriva una funzione che copia la stringa s2 nel vettore
s1.
/*Pre: dim del vettore s1 sufficienti per contenere s2*/
/*Post: s1 contiene la stringa s2*/
void stringcopy(char *s1, char *s2)
{
for (;*s2 !='\0';s1++,s2++)
*s1=*s2;
*s1='\0';
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Alcuni esercizi sulle stringhe…
/*Post: confronta s1 e s2. Restituisce -1 se s1 e' minore in ordine
lessicografico di s2, 0 se sono uguali ,1 se s1 e' maggiore in
ordine lessicografico di s2 */
int stringcmp(char *s1, char *s2)
{
while (*s1==*s2)
{
if (*s1=='\0')
return 0;
s1++;
s2++;
}
if (*s1 == '\0')
return -1;
else if (*s2 == '\0')
return 1;
else
return (((*s1 - *s2)>0)?1:-1);
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 1, Compito B
Si scriva una funzione che dato un vettore
di interi ORDINATO calcoli il numero di
valori che compaiono ripetuti almeno una
volta nel vettore
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Soluzioni compito B
/* conta il numero di elementi del vettore che vengono ripetuti */
int numRipetizioni (int vett[ ], int n) {
int check;
int done = 0;
int count = 0;
int i = 0;
check = vett[0];
for (i = 1; i < n; i++) {
if (check == vett[i]) {
if(done == 0) {
done = 1;
count++;
}
}
else {
check = vett[i];
done = 0;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 2, compito D
Denominiamo un elemento di una matrice
di interi n*m un minimo diagonale se è
l’elemento con il valore (strettamente)
minore tra quelli delle (due) diagonali a cui
appartiene.
Si scriva una funzione che data una
matrice di interi ed un intero h calcoli il
numero dei suoi minimi diagonali con
valore > h
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Soluzione esercizio
int minimoDiagonale2(int righe, int colonne, int matrix[][colonne], int h) {
int k, i ,j ;
int count = 0;
for (i = 0; i < righe; i++) {
for (j = 0; j < righe; j++) {
if (matrix[i][j] > h) {
if (controlloDiagonale1(colonne, i, j, matrix) &&
controlloDiagonale2(colonne, i, j, matrix) &&
controlloDiagonale3(righe, colonne, i, j, matrix) &&
controlloDiagonale4(righe, colonne, i, j, matrix)) {
count++;
}
}
}
}
return count;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Sol esercizio 2 compito D
int controlloDiagonale1(int num_colonne, int indice_riga, int
indice_colonna, int matrix[][num_colonne]) {
int valore = matrix[indice_riga][indice_colonna];
indice_riga--;
indice_colonna++;
while (indice_riga >= 0 && indice_colonna < num_colonne) {
if (valore >= matrix[indice_riga][indice_colonna]) {
return 0;
}
else {
indice_riga--;
indice_colonna++;
}
}
return 1;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Sol esercizio 2 compito D
int controlloDiagonale2(int num_colonne, int indice_riga, int
indice_colonna, int matrix[][num_colonne]) {
int valore = matrix[indice_riga][indice_colonna];
indice_riga--;
indice_colonna--;
while (indice_riga >= 0 && indice_colonna >= 0) {
if (valore >= matrix[indice_riga][indice_colonna]) {
return 0;
}
else {
indice_riga--;
indice_colonna--;
}
}
return 1;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Sol esercizio 2 compito D
int controlloDiagonale3(int num_righe, int num_colonne, int indice_riga,
int indice_colonna, int matrix[][num_colonne]) {
int valore = matrix[indice_riga][indice_colonna];
indice_riga++;
indice_colonna--;
while (indice_riga < num_righe && indice_colonna >= 0) {
if (valore >= matrix[indice_riga][indice_colonna]) {
return 0;
}
else {
indice_riga++;
indice_colonna--;
}
}
return 1;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Sol esonero 2 compito D
int controlloDiagonale4(int num_righe, int num_colonne, int indice_riga, int
indice_colonna, int matrix[][num_colonne]) {
int valore = matrix[indice_riga][indice_colonna];
indice_riga++;
indice_colonna++;
while (indice_riga < num_righe && indice_colonna < num_colonne) {
if (valore >= matrix[indice_riga][indice_colonna]) {
return 0;
}
else {
indice_riga++;
indice_colonna++;
}
}
return 1;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 2 compito B
Denominiamo un elemento di una matrice
di interi n*m un massimo diagonale se è
l’elemento con il valore (strettamente)
maggiore tra quelli delle (due) diagonali a
cui appartiene.
Si scriva una funzione che data una
matrice di interi calcoli il numero dei suoi
massimi diagonali.
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esempio
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Compito B, secondo esercizio
int massimoDiagonale(int righe, int colonne, int matrix[][colonne]) {
int k, i ,j ;
int count = 0;
/*scorre le diagonali che partono da (i, 0) con "i" indice di riga e controlla
se tale diagonale contiene un massimo diagonale. In caso affermativo
aumenta il contatore*/
for (k = 0; k < righe; k++) {
count += esisteMassimoDiagonale(righe, colonne, k, 0, matrix);
}
/*scorre le diagonali che partono da (0, j) con "j" indice di colonna
(j > 0 perché tale caso è già stato controllato nel for precedente) e
controlla se tale diagonale contiene un massimo diagonale. In caso
affermativo aumenta il contatore*/
for (k = 1; k < colonne; k++) {
count += esisteMassimoDiagonale(righe, colonne, 0, k, matrix);
}
return count;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Compito B, secondo esercizio
int esisteMassimoDiagonale(int num_righe, int num_colonne, int indice_riga, int indice_colonna,
int matrix[ ][num_colonne])
{
int i, j, k, aux_riga, aux_colonna;
int check = matrix[indice_riga][indice_colonna];
aux_riga = indice_riga;
aux_colonna = indice_colonna;
j = aux_colonna + 1;
i = aux_riga + 1;
while (i < num_righe && j < num_colonne) {
if (check < matrix[i][j]) {
check = matrix[i][j];
aux_riga = i;
aux_colonna = j;
}
else {
if (check == matrix[i][j]) {
aux_riga = -1;
aux_colonna = -1;
}
}
i++;
j++;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
…fine funzione
int check_diagonale1 = 1;
int check_diagonale2 = 1;
int uscita;
if (aux_riga != -1) {
i = aux_riga - 1;
j = aux_colonna + 1;
uscita = 1;
while (i >= 0 && j < num_colonne && uscita) {
if (matrix[aux_riga][aux_colonna] <= matrix[i][j]) {
check_diagonale1 = 0;
uscita = 0;
}
else {
i--;
j++;
}
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
….fine funzione
if (check_diagonale1) {
i = aux_riga + 1;
j = aux_colonna - 1;
uscita = 1;
while (i < num_righe && j >= 0 && uscita) {
if (matrix[aux_riga][aux_colonna] <= matrix[i][j]) {
check_diagonale2 = 0;
uscita = 0;
}
else {
i++;
j--;
}
Siamo all’interno di if
}
aux_riga !=-1
}
if (check_diagonale1 && check_diagonale2) {
return 1;
}
}
return 0;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Terzo esercizio, compito B
void eliminaInvertiStringa(int k) {
char parola[255];
int count = 0;
char testo[255];
char c;
while ((c = getchar()) != EOF) {
testo[count] = c;
count++;
}
testo [count] = '\0';
int len = strlen(testo);
count=0;
Prende da input un testo e lo memorizza in una
stringa
Calcola la lunghezza della stringa
Contenente il testo
while (len > 0) {
if (testo[len-1] == '\n' || testo[len-1] == ' ') {
parola[count] = '\0';
Stampa in ordine invertito le parole
if (strlen(parola) <= k) {
printf("%s",parola);
che sono di al massimo k caratteri
}
A mano a mano che legge una parola
count = 0;
if (testo[len-1] == '\n') {printf("\n"); }
La mette in un vettore di appoggio
if (testo[len-1]== ‘ ‘) {printf(” “); }
parola
}
else {
parola[count] = testo[len-1];
count++;
}
len--;
}
if (strlen(parola) <= k) {
parola[count] = '\0';
Prof.ssa Chiara Petrioli -- corso di
printf("%s ",parola);
programmazione 1, a.a. 2006/2007
}
Soluzioni compito D
Esercizio 1, compito D
Si scriva una funzione che dato un vettore
di interi verifichi se è vero che ogni
elemento del vettore contenente un valore
dispari abbia un valore maggiore alla
somma degli elementi successivi.
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 1, compito D
/*Pre: vettore non vuoto*/
int dispariMaggiore (int vett[], int n) {
int somma = vett[n-1];
int i;
for (i = n-2; i >= 0; i--) {
if ((vett[i] % 2 != 0) && vett[i] <= somma) {
return 0;
}
somma += vett[i];
}
return 1;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 3, compito D
Si scriva una funzione che prenda da input
una stringa di testo composto da
sequenze di caratteri divise da spazi e
ritorni a capo. La funzione stampa i
caratteri del testo in ordine invertito dopo
aver cancellato le sequenze di caratteri del
testo che contengono cifre.
Vediamo la variante in cui invece il testo
sia dato in una stringa
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Soluzione esercizio 3, compito D
void eliminaInvertiStringaNumeri(char testo[]) {
int len = strlen(testo);
char parola[255];
/*Pre: stringa di testo contenente solo
int count = 0;
Caratteri alfanumerici, spazi e newline*/
int check_num = 1;
while (len > 0) {
if (testo[len-1] == '\n' || testo[len-1] == ' ' || testo[len-1] == '\0') {
parola[count] = '\0';
if (check_num) {
printf("%s",parola);
}
else {
check_num = 1;
}
count = 0;
if (testo[len-1] == '\n') {
printf("\n");
}
if (testo[len-1] == ‘ ') {
printf(“ ");
}
}
else {
parola[count] = testo[len-1];
if (parola[count] >= '0' && parola[count] <= '9') {
check_num = 0;
}
count++;
}
len--;
}
if (check_num) {
Prof.ssa Chiara Petrioli -- corso di
parola[count] = '\0';
programmazione 1, a.a. 2006/2007
printf("%s ",parola);
Alcuni esercizi sulle stringhe
si scriva una funzione che, date due stringhe,
restituisce 1 se la prima stringa compare come
sottostringa della seconda, 0 altrimenti. Se la
prima stringa e' vuota restituisce 1 (una
stringa vuota e' sottostringa di q.siasi stringa.
Se la seconda stringa e' vuota e la prima no
allora restituisce 0.
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Alcuni esercizi sulle stringhe
int findstr (char *s1, char *s2)
{
char *temp_s1;
char *temp_s2;
while (*s2!='\0') {
temp_s2=s2;
temp_s1=s1;
while ((*s1 == *s2)&&(*s1!='\0')&&(*s2!='\0'))
{
s1++;
s2++;
}
if (*s1=='\0')
return 1;
else if (*s2=='\0')
return 0;
else
{
s2=temp_s2+1;
s1=temp_s1;
}
}
return ((s1=='\0')?1:0);
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
}
Vettori di puntatori
I vettori possono contenere elementi di tipo puntatore
Esempio: array di stringhe
const char *suit[4]={“Cuori”,”Quadri”,”Picche”,”Fiori”};
La memoria allocata per suit è quella necessaria per contenere
4 puntatori
Ciascuna stringa ha poi allocata memoria separatamente per
Contenerne i caratteri incluso quello di fine stringa
Gli elementi di suit sono
puntatori alla
6200
posizione dove è memorizzato
C u il primo
o carattere
r
i di ciascuna
\0
stringa
ciascuno punta in maniera
Q u Stabile
a adduna determinata
r
i
\0
suit
stringa
3100
P
i
c
c
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
F
i
o
r
h
e
i
\0
\0
Vettori di puntatori
I vettori possono contenere elementi di tipo puntatore
Esempio: array di stringhe
const char *suit[4]={“Cuori”,”Quadri”,”Picche”,”Fiori”};
Non si poteva usare una matrice di caratteri?
Si MA l’uso di vettori di puntatori a caratteri fa risparmiare memoria
Per ogni stringa
Si alloca la memoria sufficiente a memorizzare la stringa
NON la memoria necessaria a memorizzare la stringa più lunga
6200
suit
3100
C
u
o
r
i
\0
Q
u
a
d
r
i
\0
P
i
c
c
h
e
\0
i
\0
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
F
i
o
r
Un esempio
0 1
Cuori
0
Quadri
1
Re
Donna
Fante
Dieci
Due
Asso
Si scriva un programma che mescoli un mazzo di
carte, stampando l’ordine delle carte ottenuto
9 10 11 12
mazzo_carte
Picche
2
Fiori
3
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Pseudocodice
Inizializza la matrice mazzo_carte a 0
Inizializza una variabile contatore k a 1
Fino a quando non è stato assegnato un
Critico …potrei avere lunghe attese
ordine a ciascuna carta
(52 iterazioni)
(attesa ‘infinita’)
prima di trovare una
libera. Come potrei risolvere
– Scegli la prossimaposizione
carta
il problema? Posso scegliere casualmente
Scegli casualmente
una
riga
i
solo
tra le
posizioni
non ancora riempite
per esercizio
Scegli casualmenteuna
colonna j
Se mazzo_carte[i][j] è diverso da zero scegli una
nuova riga e colonna, ALTRIMENTI
mazzo_carte[i][j]=k
incrementa k
Stampa una a una le carte nell’ordine
selezionato
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Codice
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void shuffle(int wDeck[ ][13]);
void deal(const int wDeck[ ][13],
const char *wFace[ ], const char *wsuit[ ]);
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Codice
int main()
{
const char *suit[4]={“Cuori”,”Quadri”,”Picche”,”Fiori”};
const char *face[13]={“Uno”,”Due”,”Tre”,”Quattro”,
“Cinque”,”Sei”,”Sette”,”Otto”,”Nove”,”Dieci”,”Fante”, “Donna”,
“Re”};
Alloco memoria per
una matrice di 52
int deck[4][13]={0};
interi. Inizializzo la
srand(time(0));
matrice a 0
shuffle(deck);
deal(deck,face,suit);
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Shuffle
void shuffle(int wDeck[ ][13])
{
int i,j,k;
for (k=1; k<=52; k++) {
do{
i=rand()%4;
j=rand()%13;
} while (wDeck[i][j] !=0);
wDeck[i][j]=k;
}
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Shuffle
k=2
0 1
Cuori
0
Quadri
1
Picche
2
Fiori
3
Re
Donna
Fante
Dieci
Due
Asso
k=1
9 10 11 12
1
2
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
i1
j3
i3
j10
Shuffle
i2
i1
j3
j12
SCEGLIAMO
UN ALTRO i e
j, LA POSIZIONE
È GIA’
OCCUPATA
0 1
Cuori
0
Quadri
1
Picche
2
Fiori
3
Re
Donna
Fante
Dieci
Due
Asso
k=3
9 10 11 12
1
3
2
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Stampa delle carte nell’ordine
selezionato
void deal(const int wDeck[][13],const char *wFace[ ], const
char *wSuit[ ])
Scandiamo sempre tutta la matrice
{
anche quando abbiamo trovato
int i,j,k;
l’elemento che corrisponde alla
k-esima carta
for (k=1;k<=52;k++){
inefficiente. Qualche idea su come
for (i=0;i<=3;i++){
evitare questo problema?
for (j=0;j<=12;j++){
if (wDeck[i][j]==k){
printf(“%s di %s\n”,wFace[j],wSuit[i]);
} Quattro di Quadri
Fante di Fiori
}
Re di Picche
}
--}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Puntatori a funzioni
Un nome di funzione indica l’indirizzo di
memoria in cui è memorizzata la prima
istruzione della funzione
Esempio di uso:
una versione del bubblesort che consenta
di inserire da input se il vettore deve
essere ordinato in ordine crescente o
decrescente
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Bubblesort
Puntatore ad una funzione
che prende come parametri
due interi e restituisce un
intero
Compare è un puntatore a
funzione
#include<stdio.h>
#define SIZE 10
void bubble(int work[ ], const int size,
int (*compare)(int a,int b));
int ascending(int a, int b);
int descending(int a,int b);
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Bubblesort
int main()
{
int order; /* 1 per ordine crescente, 2 per decrescente*/
int counter;
int a[SIZE]={2,6,4,8,10,12,89,68,45,37};
printf(“si inserisca 1 per ordinare in ordine crescente, 2 per un ordinamento
decrescente del vettore \n”);
scanf(“%d”, &order);
printf(“dati nell’ordine originale \n”);
for (counter=0;counter<SIZE;counter++){
printf(“%d”,a[counter]);
puntatore a funzione
}
if(order==1){
bubble(a,SIZE,ascending);
}
else{
bubble(a,SIZE,descending);
}
for (counter=0,counter<SIZE; counter++){
printf(“%d”,a[counter]);
}
return 0;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Bubble
compare è un
puntatore ad una
funzione che prende
due parametri interi e
restituisce un intero
void bubble(int work[ ],const int size,
int (*compare)(int a, int b))
{
int (*) (int,int);
int pass;
int count;
void swap(int *element1Ptr,int *element2Ptr);
for (pass=1;pass<size;pass++){
for (count=0;count<size-1;count++){
if ((*compare)(work[count],work[count+1])){
swap(&work[count],&work[count+1]);
}
}
un puntatore a funzione è dereferenziato per
usare la funzione
}
Prof.ssa Chiara
Petrioli -- corso
di
Invoca
la funzione
puntata
da compare con
programmazione
1,
a.a.
2006/2007
}
parametri work[count] e work[count+1]
Swap, ascending, descending
void swap(int *element1Ptr, int *element2Ptr)
{
printf(“si inserisca 1 per ordinare in ordine
int hold;
2 per un ordinamento decrescente
hold=*element1Ptr; crescente,
del vettore \n”);
*element1Ptr=*element2Ptr;
scanf(“%d”, &order);
*element2Ptr=hold; printf(“dati nell’ordine originale \n”);
for (counter=0;counter<SIZE;counter++){
}
printf(“%d”,a[counter]);
A seconda che
si voglia ordinare
/*ritorna 1 se non si segue
crescente*/
} l’ordinamento
in ordine crescente o decrescente
int ascending(int a,int b) if(order==1){
occorre
testare due condizioni
bubble(a,SIZE,ascending);
{
diverse per verificare se due elementi
}
return b<a;
else{ consecutivi sono ordinati correttamente
obubble(a,SIZE,descending);
meno
}
int descending(int a,int b)}
{
return b>a;
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
}
Puntatori a funzione
(secondo esempio)
Un utente seleziona un’opzione da un menu.
Ciascuna opzione è servita da una
funzione differente.
I diversi puntatori a funzione sono
memorizzati in un array di puntatori a
funzione. La scelta dell’utente fornisce
l’indice del vettore. Il puntatore a funzione
è usato per invocare la funzione opportuna
in base alla scelta dell’utente.
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Codice
#include<stdio.h>
inizializza un array
void function1(int a);
void function2 (int b);
di tre puntatori a funzione
void function3 (int c);
Queste funzioni prendono
int main()
in input un intero e non
{
restituiscono valori
void (*f[3])(int)={function1,function2,function3};
int choice,i;
printf(“inserisci la scelta della funzione da invocare: 0, 1, 2 a seconda che
vogliate moltiplicare per uno, due o tre il valore inserito. Inserire il valore 3 per
terminare l’esecuzione”);
scanf(“%d”,&choice);
printf(“inserisci intero \n”);
scanf(“%d”,&i);
while(choice>=0 && choice <3){
(*f[choice])(i);
printf(“inserisci la scelta della funzione da invocare: 0, 1, 2 a seconda che
vogliate moltiplicare per uno, due o tre il valore inserito. Inserire il valore 3 per
terminare l’esecuzione”);
scanf(“%d”, &choice);
invoca la funzione puntata
printf(“inserisci intero \n”);
da f[choice] sul valore intero
scanf(“%d”,&i);
}
inserito da input i
return 0;
Prof.ssa Chiara Petrioli -- corso di
}
programmazione 1, a.a. 2006/2007
Codice delle tre funzioni…
void function1(int a)
{
printf(“il valore di a moltiplicato per uno è %d\n”,a*1);
}
void function2(int a)
{
printf(“il valore di a moltiplicato per due è %d\n”,a*2);
}
void function3(int a)
{
printf(“il valore di a moltiplicato per tre è %d\n”,a*3);
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Argomenti avanzati sulle funzioni…
Classi di memoria
Regole di scope
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Classi di memoria
Una variabile ha associato un tipo, un nome, una
dimensione ed un valore
Altri attributi di una variabile sono
la sua classe di memoria
–
–
–
–
auto
register
extern
static
il periodo durante il quale l’identificatore ha associata memoria
(storage duration)
lo scope (in quali parti del programma si può far riferimento alla
variabile)
linkage (se il programma è suddiviso in più file se l’identificatore
può essere usato solo in questo file oppure in altri file previa
opportune dichiarazioni)
ARGOMENTO CHE TRATTERETE AD ESERCITAZIONE/PROG2
Automatic storage duration
Classi di memoria
register int counter=1;
dice che la variabile
intera counter dovrebbe
essere memorizzata in un
registro e inizializzata a 1
auto
Le variabili viste
Finora erano
register
implicitamente
dichiarate
Le variabili di tipo auto o register permangono in memoria
come auto
fino a quando è attivo il blocco di istruzioni all’interno
Se dichiarate
all’inizio del main del quale la variabile è definita
è loro allocata Le variabili locali alle funzioni sono tipicamente di tipo
memoria fino
auto (è la loro classe di memoria di default)
all’uscita dal
Se una variabile è di tipo register si suggerisce che venga
programma
memorizzata in un registro
se dichiarate
all’inizio di una I compilatori sanno ottimizzare l’uso dei registri meglio
funzione la variabile
di un programmatore
ha allocata memoria
 possono decidere di ignorare la richiesta di mettere in
fino a quando non
un registroProf.ssa
una Chiara
variabile
Petrioli -- corso di
si esce dalla
programmazione 1, a.a. 2006/2007
funzione
Static storage duration
Le parole chiave
extern
static
sono usate per identificare variabili e funzioni di tipo static
storage
Memoria è allocata una volta per tutte e le variabili sono
inizializzate all’inizio del programma. Tale memoria è
disponibile per l’intera durata del programma
Le variabili globali sono di tipo extern per default. Sono dichiarate
fuori da ogni funzione e mantengono memoria a loro allocata
durante l’intera durata del programma. Possono essere riferite
da una qualsiasi funzione che segue la loro dichiarazione.
Le variabili di tipo static invece sono note solo all’interno della
funzione dove sono definite. Tuttavia quando si esce dalla
funzione si continua a memorizzare il loro valore. La prossima
volta che si invoca la funzione la variabile locale static avrà
come valore quello che aveva alla fine della precedente
invocazione.
static int count=1;
Regole di scope
Lo scope di un identificatore è la porzione
del programma all’interno della quale si
può fare riferimento all’identificatore
– function scope
– file scope
– block scope
– function-prototype scope
etichette
usate nel costrutto
switch
possono essere
usate solo all’interno
della funzione nella
Un identificatore dichiarato all’esterno di ogni quale compaiono
(e possono essere
funzione ha uno scope di tipo file scope
riferite in qualsiasi
Possono essere riferite in qualsiasi punto
punto della funzione)
all’interno del file a partire dal punto in cui
l’identificatore è dichiarato
Esempi: variabili globali, definizioni di funzioni,
prototipi)
Regole di scope
Lo scope di un identificatore è la porzione
del programma all’interno della quale si
può fare riferimento all’identificatore
– function scope
– file scope
– block scope
– function-prototype scope
Identificatori block scope
possono essere
riferiti all’interno del
Blocco in cui sono dichiarate
Il blocco è delimitato da {}
Variabili static hanno uno scope
di blocco
Variabili locali ad una funzione
Gli unici identificatori di tipo function prototype
quelli
hannoscope
scopesono
di blocco
usati nella lista dei parametri di un prototipo di funzione. Dato che
tali nomi, se usati, sono ignorati dal compilatore, hanno valore
solo all’interno del prototipo. Gli stessi identificatori possono essere
riutilizzati in altre parti del programma senza problemi di ambiguità
#include <stdio.h>
Un esempio…
void useLocal (void);
void useStaticLocal (void);
void useGlobal (void);
int x=1; /*variabile globale*/
Se lo stesso identificatore
è usato in un blocco più interno
all’interno del blocco interno
vale la definizione e inizializzazione
del blocco interno.
int main()
{
int x=5;
/*variabile locale al main*/
printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);
{/*comincia un nuovo scope*/
int x=7; /*variabile locale al blocco*/
printf(“il valore di x all’interno dello scope più interno del main è: %d”,x);
}
printf(“il valore di x nello scope più esterno del main è: %d”, x);
useLocal();
useStaticLocal();
useGlobal();
Il valore di x all’interno dello scope più
useLocal();
esterno del main è: 5
useStaticLocal();
Il valore di x all’interno dello scope più
useGlobal();
interno del main è: 7
return 0;
Il valore di x all’interno dello scope più
}
Prof.ssa Chiara Petrioli -- corso di
esterno del
programmazione 1, a.a. 2006/2007
main è: 5
Un esempio…
void useLocal (void)
{
int x=25; /*è di classe di memoria auto*/
printf(“”)
printf(“valore di x entrati in useLocal, all’inizio
della funzione: %d\n”,x);
x++;
printf(“valore di x entrati in useLocal, alla fine
della funzione: %d\n”,x);
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
#include <stdio.h>
Un esempio…
void useLocal (void);
void useStaticLocal (void);
void useGlobal (void);
int x=1; /*variabile globale*/
int main()
{
int x=5;
/*variabile locale al main*/
printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);
{/*comincia un nuovo scope*/
int x=7; /*variabile locale al blocco*/
printf(“il valore di x all’interno dello scope più interno del main è: %d”,x);
}
printf(“il valore di x nello scope più esterno del main è: %d”, x);
useLocal();
useStaticLocal();
useGlobal();
Il valore di x entrati in UseLocal all’inizio
useLocal();
della funzione è: 25
useStaticLocal();
Il valore di x entrati in UseLocal alla fine
useGlobal();
return 0;
della funzione è: 26
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio…
void useStaticLocal()
{
static int x=50; /*inizializzata solo la prima volta
che si entra nella funzione*/
printf(“local static vale %d all’inizio della
funzione useStaticLocal”,x);
x++;
printf(“local static vale %d alla fine della funzione
useStaticLocal”,x);
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio…
void useGlobal()
{
printf(“global x vale %d all’entrata di
useGlobal\n”,x);
x*=10;
printf(“global x vale %d alla fine di
useGlobal\n”,x);
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
#include <stdio.h>
Un esempio…
void useLocal (void);
void useStaticLocal (void);
void useGlobal (void);
int x=1; /*variabile globale*/
int main()
{
int x=5;
/*variabile locale al main*/
printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);
{/*comincia un nuovo scope*/
int x=7; /*variabile locale al blocco*/
printf(“il valore di x all’interno dello scope più interno del main è: %d”,x);
}
printf(“il valore di x nello scope più esterno del main è: %d”, x);
useLocal();
useStaticLocal();
useGlobal();
local static vale 50 all’inizio della funzione
useLocal();
useStaticLocal
useStaticLocal();
local static vale 51 alla fine della funzione
useGlobal();
useStaticLocal
return 0;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
#include <stdio.h>
Un esempio…
void useLocal (void);
void useStaticLocal (void);
void useGlobal (void);
int x=1; /*variabile globale*/
int main()
{
int x=5;
/*variabile locale al main*/
printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);
{/*comincia un nuovo scope*/
int x=7; /*variabile locale al blocco*/
printf(“il valore di x all’interno dello scope più interno del main è: %d”,x);
}
printf(“il valore di x nello scope più esterno del main è: %d”, x);
useLocal();
useStaticLocal();
useGlobal();
Global x vale 1 all’entrata di
useLocal();
useGlobal
useStaticLocal();
Global x vale 10 alla fine di
useGlobal();
useGlobal
return 0;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
#include <stdio.h>
Un esempio…
void useLocal (void);
void useStaticLocal (void);
void useGlobal (void);
int x=1; /*variabile globale*/
int main()
{
int x=5;
/*variabile locale al main*/
printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);
{/*comincia un nuovo scope*/
int x=7; /*variabile locale al blocco*/
printf(“il valore di x all’interno dello scope più interno del main è: %d”,x);
}
printf(“il valore di x nello scope più esterno del main è: %d”, x);
useLocal();
useStaticLocal();
useGlobal();
useLocal();
Il valore di x entrati in UseLocal all’inizio
useStaticLocal();
della funzione è: 25
useGlobal();
Il valore di x entrati in UseLocal alla fine
return 0;
della funzione è: 26
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
#include <stdio.h>
Un esempio…
void useLocal (void);
void useStaticLocal (void);
void useGlobal (void);
int x=1; /*variabile globale*/
int main()
{
int x=5;
/*variabile locale al main*/
printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);
{/*comincia un nuovo scope*/
int x=7; /*variabile locale al blocco*/
printf(“il valore di x all’interno dello scope più interno del main è: %d”,x);
}
printf(“il valore di x nello scope più esterno del main è: %d”, x);
useLocal();
useStaticLocal();
useGlobal();
local static vale 51 all’inizio della funzione
useLocal();
useStaticLocal
useStaticLocal();
local static vale 52 alla fine della funzione
useGlobal();
useStaticLocal
return 0;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
#include <stdio.h>
Un esempio…
void useLocal (void);
void useStaticLocal (void);
void useGlobal (void);
int x=1; /*variabile globale*/
int main()
{
int x=5;
/*variabile locale al main*/
printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);
{/*comincia un nuovo scope*/
int x=7; /*variabile locale al blocco*/
printf(“il valore di x all’interno dello scope più interno del main è: %d”,x);
}
printf(“il valore di x nello scope più esterno del main è: %d”, x);
useLocal();
useStaticLocal();
useGlobal();
useLocal();
Global x vale 10 all’entrata di
useStaticLocal();
useGlobal
useGlobal();
Global x vale 100 alla fine di
return 0;
useGlobal
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Ricorsione
Abbiamo visto come un problema complesso
possa essere scomposto in task, ciascuno
realizzato tramite una funzione
Una funzione può invocare altre funzioni
E’ possibile anche invocare la STESSA
funzione, su un input diverso
– Un task complesso può essere risolto invocando la
funzione che realizza il task su dei sottoproblemi,
usando la capacità di svolgere il task su sottoproblemi
per riuscire a svolgere il task sull’intero problema
 ricorsione
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Ricorsione…un esempio
Vogliamo scrivere una funzione che consenta di
calcolare il fattoriale n!
n!= n*(n-1)*(n-2)*(n-3)*…*2*1
Approccio ricorsivo:
– Supponiamo di poter invocare ricorsivamente la
funzione su interi n’ < n e di poter usare tale
invocazione per calcolare il fattoriale di n
– Possiamo sfruttare il fatto che n!=n*(n-1)!
– Per calcolare il fattoriale di n invoco la funzione
fatt su n-1 e moltiplico il risultato per n
Abbiamo ridotto la complessità del problema
esprimendo la soluzione in funzione della
risoluzione di problemi meno complessi
 sfruttando il fatto che tramite chiamata ricorsiva
riusciamo a risolvere su problemi più piccoli per
trovare la soluzione del problema più complesso
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Fattoriale (versione ricorsiva)
int fatt (int n)
Caso base. Occorre saper risolvere
{
direttamente i casi base.
if (n==1)
return 1;
else
return (fatt(n-1)*n);
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
Calcolo di 5!
Viene invocata
x=fatt(5);
All’entrata della funzione
si alloca memoria per la var.
locale n
Si copia in tale locazione il
valore 5
5
3200
n
int fatt (int n)
{
if (n==1)
return 1;
else
return (fatt(n-1)*n);
}
Si invoca fatt(4)
PRIMA INVOCAZIONE DI FATT
fatt(5)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
Calcolo di 5!
Viene invocata
fatt(4);
All’entrata della funzione
si alloca memoria per la var.
locale n, relativa A QUESTA
INVOCAZIONE DI FUNZIONE
Si copia in tale locazione il
valore 4
4
5200
n
int fatt (int n)
{
if (n==1)
return 1;
else
return (fatt(n-1)*n);
}
Si invoca fatt(3)
SECONDA INVOCAZIONE DI FATT
fatt(4)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
Calcolo di 5!
Viene invocata
fatt(3);
All’entrata della funzione
si alloca memoria per la var.
locale n, relativa A QUESTA
INVOCAZIONE DI FUNZIONE
Si copia in tale locazione il
valore 3
3
7800
n
int fatt (int n)
{
if (n==1)
return 1;
else
return (fatt(n-1)*n);
}
Si invoca fatt(2)
TERZA INVOCAZIONE DI FATT
fatt(3)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
Calcolo di 5!
Viene invocata
fatt(2);
All’entrata della funzione
si alloca memoria per la var.
locale n, relativa A QUESTA
INVOCAZIONE DI FUNZIONE
Si copia in tale locazione il
valore 2
2
9800
n
int fatt (int n)
{
if (n==1)
return 1;
else
return (fatt(n-1)*n);
}
Si invoca fatt(1)
QUARTA INVOCAZIONE DI FATT
fatt(2)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
fatt(5)
fatt(4)
Calcolo di 5!
Viene invocata
fatt(1);
Fondamentale che
fatt(3)
La sequenza di
fatt(2)
Invocazioni termini
fatt(1)
SEMPRE con l’invocazione
della funzione su un caso
che sappiamo risolvere
int fatt (int n)
direttamente (caso base)
{
All’entrata della funzione
if (n==1)
si alloca memoria per la var.
return 1;
locale n, relativa A QUESTA
else
INVOCAZIONE DI FUNZIONE
return (fatt(n-1)*n);
Si copia in tale locazione il
}
valore 1
Si restituisce il controllo
1
n
alla funzione chiamante QUINTA INVOCAZIONE DI FATT
fatt(2), restituendo 1
fatt(1)
3900
Prof.ssa Chiara Petrioli -- corso di
La memoria allocata per
programmazione 1, a.a. 2006/2007
n viene rilasciata
Un esempio..
QUARTA INVOCAZIONE DI FATT
fatt(2)
Calcolo di 5!
Viene invocata
fatt(2);
All’entrata della funzione
si alloca memoria per la var.
locale n, relativa A QUESTA
INVOCAZIONE DI FUNZIONE
Si copia in tale locazione il
valore 2
fatt(5)
n
2
fatt(4)
9800
Viene calcolato fatt(2)
2*1=2
e viene restituito tale valore
alla funzione chiamante
fatt(3)
int fatt (int n)
{
if (n==1)
return 1;
else
return (fatt(n-1)*n);
}
restituisce 1
fatt(3)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
fatt(2)
fatt(1)
Un esempio..
TERZA INVOCAZIONE DI FATT
fatt(3)
Calcolo di 5!
Viene invocata
fatt(3);
Viene calcolato fatt(3)
3*2=6
e viene restituito tale valore
alla funzione chiamante
fatt(4)
int fatt (int n)
{
if (n==1)
return 1;
else
return (fatt(n-1)*n);
}
fatt(5)
3
7800
n
fatt(4)
restituisce 2
fatt(3)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
fatt(2)
fatt(1)
Un esempio..
SECONDA INVOCAZIONE DI FATT
fatt(4)
Calcolo di 5!
Viene invocata
fatt(4);
Viene calcolato fatt(4)
4*6=24
e viene restituito tale valore
alla funzione chiamante
fatt(5)
int fatt (int n)
{
if (n==1)
return 1;
else
return (fatt(n-1)*n);
}
fatt(5)
4
5200
n
fatt(4)
restituisce 6
fatt(3)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
fatt(2)
fatt(1)
Un esempio..
PRIMA INVOCAZIONE DI FATT
fatt(5)
Viene calcolato fatt(5)
5*24=120
e viene restituito tale valore
alla funzione chiamante
main()
Calcolo di 5!
Viene invocata
x=fatt(5);
int fatt (int n)
{
if (n==1)
return 1;
else
return (fatt(n-1)*n);
}
fatt(5)
5
3200
n
fatt(4)
restituisce 24
fatt(3)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
fatt(2)
fatt(1)
Alcuni commenti…
Approccio ricorsivo
– richiede l’invocazione di molte chiamate a funzione, di
allocare ogni volta memoria per i parametri e le variabili
locali
può essere inefficiente
TUTTAVIA ragionare in modo ricorsivo è molto utile e
vedrete di qui a poco (PROG2) che esistono strutture
dati molto importanti quali gli alberi sui quali si riesce a
ragionare efficamente solo in modo ricorsivo
RAGIONARE IN MODO RICORSIVO E’ COMPLESSO MA
E’ Q.SA DI FONDAMENTALE PER UN INFORMATICO!!
Abbiamo visto cosa succede in memoria quando
invochiamo una sequenza di chiamate ricorsive…è
importante capire come si ragiona ricorsivamente
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Come si ragiona ricorsivamente
funzione
INPUT
output1
OUTPUT
output2
Se siamo in grado di descrivere correttamente cosa fa la funzione
(postcondizione)
Dobbiamo chiederci se possiamo usare il fatto che la funzione possa
essere applicata su input più piccoli per risolvere il caso generale
Se gli output della invocazioni su casi più piccoli possono essere
elaborati ed usati per trovare la soluzione al problema (OUTPUT) per
il caso più grande
AVER DETERMINATO IL MODO DI FARE CIO’ CI DARA’ IL NOSTRO
CODICE RICORSIVO
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Come si ragiona ricorsivamente
funzione
INPUT
output1
Sarà poi fondamentale
individuare i casi base
e assicurarci che tutte
le sequenze di chiamate
ricorsive terminino
sempre con l’invocazione
di un casoOUTPUT
base
output2
Se siamo in grado di descrivere correttamente cosa fa la funzione
(postcondizione)
Dobbiamo chiederci se possiamo usare il fatto che la funzione possa
essere applicata su input più piccoli per risolvere il caso generale
Se gli output della invocazioni su casi più piccoli possono essere
elaborati ed usati per trovare la soluzione al problema (OUTPUT) per
il caso più grande
AVER DETERMINATO IL MODO DI FARE CIO’ CI DARA’ IL NOSTRO
CODICE RICORSIVO
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio…
SI scriva una funzione ricorsiva che dati due
numeri interi a e b calcoli a+b
Se so calcolare x+y, x<=a, y<b, come posso
usarlo per calcolare a+b
a+b=(a+b-1)+1
Caso base: se b==0, a+b=a
Calcolato dall’invocazione della funzione su
a e b-1
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Soluzione
int somma (int a, int b)
{
if (b==0)
return a;
else
return (somma(a,b-1)+1);
}
Vediamo cosa succede invocando somma (3,2)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
Calcolo di 3+2
Viene invocata
x=somma(3,2);
All’entrata della funzione
si alloca memoria per le var.
locale a e b
Si copia in tali locazioni i
valori 3 e 2
3
a
3200
2
3800
int somma (int a, int b)
{
if (b==0)
return a;
else
return (somma(a,b-1)+1);
}
Si invoca somma(3,1)
PRIMA INVOCAZIONE DI SOMMA
b
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
Calcolo di 3+2
Viene invocata
somma(3,1);
All’entrata della funzione
si alloca memoria per le var.
locale a e b RELATIVE A
QUESTA INVOCAZIONE
Si copia in tali locazioni i
valori 3 e 1
3
a
5700
1
8100
int somma (int a, int b)
{
if (b==0)
return a;
else
return (somma(a,b-1)+1);
}
Si invoca somma(3,0)
SECONDA INVOCAZIONE DI SOMMA
b
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
Calcolo di 3+2
Viene invocata
somma(3,0);
All’entrata della funzione
si alloca memoria per le var.
locale a e b RELATIVE A
QUESTA INVOCAZIONE
Si copia in tali locazioni i
valori 3 e 0
3
a
2700
0
9000
somma(3,2)
somma(3,1)
somma(3,0)
int somma (int a, int b)
{
if (b==0)
return a;
else
return (somma(a,b-1)+1);
}
Si ritorna il controllo restituendo 3
TERZA INVOCAZIONE DI SOMMA
b
La memoria
allocata
Prof.ssa Chiara
Petrioli -- viene
corso di rilasciata
programmazione 1, a.a. 2006/2007
Un esempio..
SECONDA INVOCAZIONE DI SOMMA
Calcolo di 3+2
Viene invocata
somma(3,1);
All’entrata della funzione
si alloca memoria per le var.
locale a e b RELATIVE A
QUESTA INVOCAZIONE
Si copia in tali locazioni i
valori 3 e 1
3
a
5700
1
8100
b
somma(3,2)
somma(3,1)
somma(3,0)
int somma (int a, int b)
{
if (b==0)
return a;
else
return (somma(a,b-1)+1);
}
Si ritorna il controllo restituendo 4
a somma (3,2)
La memoria
allocata
Prof.ssa Chiara
Petrioli -- viene
corso di rilasciata
programmazione 1, a.a. 2006/2007
Ha restituito 3
Un esempio..
PRIMA INVOCAZIONE DI SOMMA
Calcolo di 3+2
Viene invocata
somma(3,2);
All’entrata della funzione
si alloca memoria per le var.
locale a e b RELATIVE A
QUESTA INVOCAZIONE
Si copia in tali locazioni i
valori 3 e 2
3
a
3200
2
3800
b
somma(3,2)
somma(3,1)
somma(3,0)
int somma (int a, int b)
{
if (b==0)
return a;
else
return (somma(a,b-1)+1);
}
Si ritorna il controllo restituendo 5
a main()
La memoria
allocata
Prof.ssa Chiara
Petrioli -- viene
corso di rilasciata
programmazione 1, a.a. 2006/2007
Ha restituito 4
Un terzo esempio
Calcolo di a*b
a*b= a+a+…
…+a
b volte
a*b=(a*(b-1))+a
Caso base
a*1=a
a*0=0
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Moltiplicazione tra due interi
int prodotto (int a,int b)
{
if (b==0)
return 0;
if (b==1)
return a;
else
return (prodotto(a,b-1)+a);
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un quarto esempio
Precondizione: a>=1
Calcolo di ab
ab = a*a*…
…*a
b volte
ab =(ab-1)*a
Caso base
a0 =1
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Moltiplicazione tra due interi
int potenza (int a,int b)
{
if (b==0)
return 1;
else
return (potenza(a,b-1)*a);
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Numeri di Fibonacci
La serie di Fibonacci
0,1,1,2,3,5,8,13,21,..
Comincia con i numero 0 e 1 ed ha la proprietà che se si
conoscono F(i) e F(i+1) allora F(i+2)=F(i+1)+F(i)
E’ una serie che occorre in natura. Il rapporto tra due
numeri consecutivi della serie di Fibonacci converge al
numero 1.618.. che è chiamata sezione aurea
Usare come rapporto tra dimensioni la sezione aurea è
esteticamente piacevole usato sin dall’antichità in
architettura (esempio rapporto tra le dimensioni di una
finestra, le dimensioni relative dei lati di una cartolina
etc.)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Codice
Calcola F(n)
long Fibonacci (long n)
{
if ((n==0)||(n==1))
return n;
else
return (Fibonacci(n-1)+Fibonacci(n-2));
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
Calcolo di Fibonacci(3)
Viene invocata
long Fibonacci (long n)
x=Fibonacci(3);
{
if ((n==0)||(n==1))
return n;
else
return (Fibonacci(n-1)+
Fibonacci(n-2));
All’entrata della funzione
si alloca memoria per le var.
n
}
Si copia in tale locazione il
valore 3
Si invoca Fibonacci(2) E Fibonacci(1)
3
n
3200
PRIMA INVOCAZIONE DI
Attenzione: non si può sapere se FIBONACCI
Prof.ssa
Chiara
-- corso di
verrà valutata
prima
laPetrioli
chiamata
programmazione 1, a.a. 2006/2007
Fibonacci(2) O Fibonacci(1)
Un esempio..
F(3)
F(2)
Calcolo di Fibonacci(3)
F(1)
Viene invocata
long Fibonacci (long n)
Fibonacci(2);
{
All’entrata della funzione
si alloca memoria per le var.
n RELATIVA A QUESTA
INVOCAZIONE
Si copia in tale locazione il
valore 2
F(1)
F(0)
if ((n==0)||(n==1))
return n;
else
return (Fibonacci(n-1)+
Fibonacci(n-2));
}
Si invoca Fibonacci(1) E Fibonacci(0)
2
n
4000
Attenzione: non si può sapere se
Prof.ssa
Chiara
-- corso di
verrà valutata
prima
laPetrioli
chiamata
programmazione 1, a.a. 2006/2007
Fibonacci(1) O Fibonacci(0)
SECONDA INVOCAZIONE DI
FIBONACCI
Un esempio..
1
F(3)
F(2)
Calcolo di Fibonacci(3)
F(1)
Viene invocata
long Fibonacci (long n)
Fibonacci(1);
{
All’entrata della funzione
si alloca memoria per le var.
n RELATIVA A QUESTA
INVOCAZIONE
Si copia in tale locazione il
valore 1
1
5900
n
F(1)
F(0)
if ((n==0)||(n==1))
return n;
else
return (Fibonacci(n-1)+
Fibonacci(n-2));
}
Si restituisce al chiamante
Fibonacci(2) il valore 1
TERZA INVOCAZIONE DI
FIBONACCI
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
1
F(3)
F(2)
Calcolo di Fibonacci(3)
F(1)
Viene invocata
long Fibonacci (long n)
Fibonacci(0);
{
All’entrata della funzione
si alloca memoria per le var.
n RELATIVA A QUESTA
INVOCAZIONE
Si copia in tale locazione il
valore 0
0
9900
n
F(1)
0
F(0)
if ((n==0)||(n==1))
return n;
else
return (Fibonacci(n-1)+
Fibonacci(n-2));
}
Si restituisce al chiamante
Fibonacci(2) il valore 0
QUARTA INVOCAZIONE DI
FIBONACCI
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
1
F(3)
F(2)
Calcolo di Fibonacci(3)
F(1)
Viene invocata
long Fibonacci (long n)
Fibonacci(1);
{
All’entrata della funzione
si alloca memoria per le var.
n RELATIVA A QUESTA
INVOCAZIONE
Si copia in tale locazione il
valore 1
1
15000
n
1
F(1)
0
F(0)
if ((n==0)||(n==1))
return n;
else
return (Fibonacci(n-1)+
Fibonacci(n-2));
}
Si restituisce al chiamante
Fibonacci(3) il valore 1
QUINTA INVOCAZIONE DI
FIBONACCI
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio..
1
1
F(3)
F(2)
Calcolo di Fibonacci(3)
F(1)
Viene invocata
long Fibonacci (long n)
Fibonacci(2);
{
All’entrata della funzione
si alloca memoria per le var.
n RELATIVA A QUESTA
INVOCAZIONE
Si copia in tale locazione il
valore 2
2
n
1
F(1)
0
F(0)
if ((n==0)||(n==1))
return n;
else
return (Fibonacci(n-1)+
Fibonacci(n-2));
}
Si restituisce al chiamante
Fibonacci(3) il valore 1
4000
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
1
0
Un esempio..
1
2
1
F(3)
F(2)
Calcolo di Fibonacci(3)
F(1)
Viene invocata
long Fibonacci (long n)
Fibonacci(3);
{
All’entrata della funzione
si alloca memoria per le var.
n RELATIVA A QUESTA
INVOCAZIONE
Si copia in tale locazione il
valore 3
2
3200
n
1
F(1)
0
F(0)
if ((n==0)||(n==1))
return n;
else
return (Fibonacci(n-1)+
Fibonacci(n-2));
}
Si restituisce al chiamante
main il valore 2
1
1
Numero di chiamate necessarie
Per calcolare F(n) dell’ordine di
Prof.ssa Chiara Petrioli -- n
corso di
2
 complessità esponenziale
programmazione 1, a.a. 2006/2007
Fibonacci
Valore di n
F(n)
0
1
2
3
…
23
24
25
…
41
42
0
1
1
2
Numero di chiamate di
funzione F(n)
1
1
3
5
28657
46368
75025
92735
150049
242785
165580141
267914296
535828591
866988873
La ricorsione in molti casi è utile però può ridurre l’efficienza. Numero di
Prof.ssa
Chiara Petrioli
corso di
chiamate elevato significa che
paghiamo
un-- overhead
elevato (tempo e
programmazione 1, a.a. 2006/2007
spazio) per invocare le funzioni, allocare memoria per le variabili locali
Torri di Hanoi
La leggenda narra che in un tempio del profondo
oriente i monaci fossero occupati nel compito di
spostare dei dischi di pietra impilati in ordine di
dimensione decrescente in un paletto A,dal
paletto (A) al paletto B. Il numero dei dischi era
64, esisteva anche un terzo paletto d’appoggio C.
A
B
C
Torri di Hanoi
La leggenda narra che in un tempio del profondo
oriente i monaci fossero occupati nel compito di
spostare dei dischi di pietra impilati in ordine di
dimensione decrescente in un paletto A,dal
paletto (A) al paletto B. Il numero dei dischi era
64, esisteva anche un terzo paletto d’appoggio C.
Ogni mossa poteva portare
allo spostamento di un unico
disco E in ogni momento
i dischi dovevano
essere posizionati in
ordine decrescente su
ciascuno dei paletti
A
La leggenda narra che il mondo finirà prima
che i monaci siano riusciti a completare
questo compito!
B
C
Torri di Hanoi…un esempio
La leggenda narra che in un tempio del profondo
oriente i monaci fossero occupati nel compito di
spostare dei dischi di pietra impilati in ordine di
dimensione decrescente in un paletto A,dal
paletto (A) al paletto B. Il numero dei dischi era
64, esisteva anche un terzo paletto d’appoggio C.
Ad esempio il disco
viola può essere
spostato in una
mossa da A a B
A
B
C
Torri di Hanoi…un esempio
La leggenda narra che in un tempio del profondo
oriente i monaci fossero occupati nel compito di
spostare dei dischi di pietra impilati in ordine di
dimensione decrescente in un paletto A,dal
paletto (A) al paletto B. Il numero dei dischi era
64, esisteva anche un terzo paletto d’appoggio C.
Il disco azzurro NON
poteva essere spostato
da A a B perché tale
spostamento non avrebbe
soddisfatto il vincolo di
ordinamento decrescente
dei dischi in B
A
Nella mossa successiva il
disco azzurro può essere
spostato da A a C
B
C
Torri di Hanoi…un esempio
La leggenda narra che in un tempio del profondo
oriente i monaci fossero occupati nel compito di
spostare dei dischi di pietra impilati in ordine di
dimensione decrescente in un paletto A,dal
paletto (A) al paletto B. Il numero dei dischi era
64, esisteva anche un terzo paletto d’appoggio C.
Possiamo ad esempio prima spostare il
disco viola in C e poi il disco verde in B
A
Nella mossa successiva non
possiamo direttamente
spostare il disco verde
B
C
Torri di Hanoi
Problema di difficile risoluzione iterativa se
abbiamo molti dischi (e dobbiamo trovare
un algoritmo che valga sempre, per
qualsiasi numero di dischi)
Ragionare in modo ricorsivo aiuta a
trovare una soluzione
A
B
Torri di Hanoi
Cosa vogliamo fare?
– Muovere n dischi dal paletto A al paletto B
usando C come appoggio
Come lo possiamo fare?
– Muovere n-1 dischi dal paletto A al paletto C
usando B come appoggio
A
B
Torri di Hanoi
Cosa vogliamo fare?
– Muovere n dischi dal paletto A al paletto B usando C
come appoggio
Come lo possiamo fare?
– Muovere n-1 dischi dal paletto A al paletto C usando
B come appoggio
– Spostare il disco più grande da A in B
A
B
Torri di Hanoi
Cosa vogliamo fare?
– Muovere n dischi dal paletto A al paletto B usando C
come appoggio
Come lo possiamo fare?
– Muovere n-1 dischi dal paletto A al paletto C usando
B come appoggio
– Spostare il disco più grande da A in B
– Muovere n-1 dischi da C a B usando A come
appoggio
Chiamate ricorsive
A
B
Torri di Hanoi-Codice
#include<stdio.h>
void hanoi (int,int[ ], int *, int [ ], int *, int [ ], int *);
I vettori A, B, C
main()
conterranno i dischi
{
Puntatore alla locazione che contiene
(ed il loro ordine)
int i,n,n_A,n_B,n_C;
prima
locazioneillibera
Numero
Vettore
diLa
dischi
che
rappresenta
primorelativa
piolo al primo piolo
impilati nei pioli A,B, e C
int A[100]={0};
int B[100]={0};
int C[100]={0};
Dato un vettore A, n_A
n_A=n_B=n_C=0;
indicherà il numero di
printf(“inserisci un numero di dischi tra 1 e 100 \n”);
scanf(“%d”, &n);
dischi impilati in A
while ((n>100)||(n<1))
(memorizzati nelle
{
locazioni di memoria
printf(“inserisci un numero di dischi tra 1 e 100 \n”);
0,…,n_A-1)
scanf(“%d”, &n);
n_A sarà quindi anche
}
l’indice della prossima
for (i=0;i<n;i++)
posizione libera del
A[i]=i+1;
vettore
n_A=n;
hanoi (n,A,&n_A, B, &n_B, C, &n_C);
return 0;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Torri di Hanoi-Codice
#include<stdio.h>
void hanoi (int,int[ ], int *, int [ ], int *, int [ ], int *);
main()
{
int i,n,n_A,n_B,n_C;
n_A
int A[100]={0};
int B[100]={0};
4
int C[100]={0};
n_A=n_B=n_C=0;
printf(“inserisci un numero di dischi tra 1 e 100 \n”);
scanf(“%d”, &n);
while ((n>100)||(n<1))
{
printf(“inserisci un numero di dischi tra 1 e 100 \n”);
scanf(“%d”, &n);
}
for (i=0;i<n;i++)
Se
il primo piolo contiene
A[i]=i+1;
I dischi in figura il corrispettivo
n_A=n;
hanoivettore
(n,A,&n_A,
&n_B, C, &n_C);
A B,
conterrà
nelle prime
return
0;
n_A=4 posizioni i valori 1,2,3,4
}
1
2
3
I dischi hanno associato
un indice da 1,..,n
I dischi più grandi avranno
associato un indice più
piccolo
4
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
A
4
3
2
1
Torri
di
Hanoi-Codice
#include<stdio.h>
void hanoi (int,int[ ], int *, int [ ], int *, int [ ], int *);
main()
{
Inizializza i vettori A, B e C a zero
int i,n,n_A,n_B,n_C;
n_A,n_B,n_C a zero (i vettori non hanno
int A[100]={0};
elementi memorizzati)
int B[100]={0};
int C[100]={0};
n_A=n_B=n_C=0;
printf(“inserisci un numero di dischi tra 1 e 100 \n”);
scanf(“%d”, &n);
Prende da input un numero valido di
while ((n>100)||(n<1))
dischi n
{
printf(“inserisci un numero di dischi tra 1 e 100 \n”);
scanf(“%d”, &n);
}
Si invoca
la funzione
il cui
Mette in A i vari dischi
dal più
grande alhanoi
più piccolo
for (i=0;i<n;i++)
Compito
sarà spostare
n dischi
(situazione quando
si comincia
a spostare
da A a da
B
A[i]=i+1;
AaB
seguendo le regole
i dischi). Si aggiorna
coerentemente
n_A. per il
n_A=n;
movimento dei dischi e mantenendo
hanoi (n,A,&n_A, B, &n_B, C, &n_C); aggiornate le informazioni sul
return 0;
Prof.ssa Chiara Petrioli --contenuto
corso di
e num. Di elementi del
programmazione
1,
a.a.
2006/2007
}
vettore
Torri di Hanoi-Codice
/*pre: num >=1*/
void hanoi(int num, int a[ ], int *N_a, int b[ ], int *N_b, int c[ ], int
*N_c)
{
if (num==1)
{
Sposto direttamente da a a b
b[(*N_b)]=a[(*N_a)-1];
(*N_b)=(*N_b)+1;
(*N_a)=(*N_a)-1;
}
else
{
hanoi(num-1,a,N_a,c,N_c,b,N_b);
b[(*N_b)]=a[(*N_a)-1];
(*N_b)=(*N_b)+1;
(*N_a)=(*N_a)-1;
hanoi (num-1,c,N_c,b,N_b,a,N_a);
}
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Un esempio
hanoi(4,A,&n_A,B,&n_B,C, &n_C);
A B through C
4
3
2
1
n_A
4
n_B
0
n_C
hanoi (3, A, N_a, C, N_c, B, N_b);
AC through B
0
Un esempio
hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
4
3
2
1
n_A
4
n_B
0
n_C
hanoi (2, A, N_a, B, N_b, C, N_c);
AB through C
0
Un esempio
hanoi(2,A,N_a,B,N_b,C, N_c);
A B through C
4
3
2
1
n_A
4
n_B
0
n_C
hanoi (1, A, N_a, C, N_c, B, N_b);
AC through B
0
Un esempio
hanoi(1,A,N_a,C,N_c,B, N_b);
A C through B
4
3
2
1
n_A
4
n_B
c[n_C]=a[n_A-1];
n_A--;
n_C++;
0
n_C
0
Un esempio
Viene restituito il
controllo
hanoi(1,A,N_a,C,N_c,B, N_b);
A C through B
3
2
4
1
n_A
3
n_B
c[n_C]=a[n_A-1];
n_A--;
n_C++;
0
n_C
1
Un esempio
Viene restituito il
controllo a questa
chiamata
hanoi(2,A,N_a,B,N_b,C, N_c);
A B through C
3
2
4
1
n_A
3
n_B
b[n_B]=a[n_A-1];
n_A--;
n_B++;
0
n_C
1
Un esempio
hanoi(2,A,N_a,B,N_b,C, N_c);
A B through C
2
3
1
n_A
2
n_B
b[n_B]=a[n_A-1];
n_A--;
n_B++;
1
4
n_C
1
Si invoca:
hanoi (1, C, N_c, B, N_b, A, N_a);
CB through A
Un esempio
hanoi(1,C,N_c,B,N_b,A, N_a);
C B through A
2
3
1
n_A
2
n_B
1
4
n_C
1
Un esempio
hanoi(1,C,N_c,B,N_b,A, N_a);
C B through A
4
2
3
1
n_A
2
n_B
2
n_C
0
Si restituisce il controllo al
chiamante
Un esempio
hanoi(2,A,N_a,B,N_b,C, N_c);
A B through C
4
2
3
1
n_A
2
n_B
2
n_C
0
hanoi (2,------------------)
ha terminato le istruzioni
da eseguire.
Restituisce il controllo al
chiamante
Un esempio
hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
4
2
3
1
n_A
2
n_B
2
n_C
Aveva invocato:
hanoi (2, A, N_a, B, N_b, C, N_c);
AB through C
Questa invocazione ha ora ritornato
Il controllo
0
Un esempio
hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
4
2
3
1
n_A
2
n_B
Si esegue:
c[n_C]=a[n_A-1];
n_A--;
n_C++;
2
n_C
0
Un esempio
hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
4
1
n_A
2
3
1
n_B
Si esegue:
c[n_C]=a[n_A-1];
n_A--;
n_C++;
2
n_C
1
Un esempio
hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
4
1
n_A
2
3
1
n_B
Si esegue:
c[n_C]=a[n_A-1];
n_A--;
n_C++;
2
n_C
1
Si invoca:
hanoi (2, B, N_b, C, N_c, A, N_a);
BC through A
Un esempio
hanoi(2,B,N_b,C,N_c,A, N_a);
B C through A
4
1
n_A
2
3
1
n_B
2
n_C
1
Si invoca:
hanoi (1, B, N_b, A, N_a, C, N_c);
BA through C
Un esempio
hanoi(1,B,N_b,A,N_a,C, N_C);
B A through C
4
1
n_A
2
3
1
n_B
2
n_C
1
Un esempio
hanoi(1,B,N_b,A,N_a,C, N_C);
B A through C
4
1
n_A
2
3
2
n_B
1
n_C
1
Si restituisce il controllo al
chiamante
Un esempio
hanoi(2,B,N_b,C,N_c,A, N_a);
B C through A
4
1
n_A
2
3
2
n_B
1
Aveva invocato:
hanoi (1, B, N_b, A, N_a, C, N_c);
BA through C
Tale invocazione ha terminato
restituendo il controllo
n_C
1
Si esegue:
c[n_C]=b[n_A-1];
n_B--;
n_C++;
Un esempio
hanoi(2,B,N_b,C,N_c,A, N_a);
B C through A
Si invoca:
hanoi (1, A, N_a, C, N_c, B, N_b);
AC through B
3
4
2
1
n_A
2
n_B
0
n_C
2
Si esegue:
c[n_C]=b[n_B-1];
n_B--;
n_C++;
Un esempio
hanoi(1,A,N_a,C,N_c,B, N_c);
A C through B
3
4
2
1
n_A
2
n_B
0
n_C
2
Un esempio
hanoi(1,A,N_a,C,N_c,B, N_c);
A C through B
4
3
2
1
n_A
1
n_B
0
n_C
3
Si restituisce il controllo al chiamante
Un esempio
hanoi(2,B,N_b,C,N_c,A, N_a);
B C through A
4
3
2
1
n_A
1
n_B
0
n_C
3
Si restituisce il controllo al chiamante
Un esempio
hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
4
3
2
1
n_A
1
n_B
0
n_C
3
Si restituisce il controllo al chiamante
Un esempio
hanoi(4,A,&n_A,B,&n_B,C, &n_C);
A B through C
4
3
2
1
n_A
1
n_B
0
n_C
3
Si esegue:
b[n_B]=a[n_A-1];
n_B++;
n_A--;
Un esempio
hanoi(4,A,&n_A,B,&n_B,C, &n_C);
A B through C
4
3
2
1
n_A
0
n_B
Si invoca
hanoi(3,C,N_c,B,N_b,A,N_a);
1
n_C
3
Si esegue:
b[n_B]=a[n_A-1];
n_B++;
n_A--;
Un esempio
hanoi(3,C,N_c,B,N_b,A,N_a);
C B through A
4
3
2
1
n_A
0
n_B
Si invoca
hanoi(2,C,N_c,A,N_a,B,N_b);
1
n_C
3
Un esempio
hanoi(2,C,N_c,A,N_a,B,N_b);
C A through B
4
3
2
1
n_A
0
n_B
Si invoca
hanoi(1,C,N_c,B,N_b,A,N_a);
1
n_C
3
Un esempio
hanoi(1,C,N_c,B,N_b,A,N_a);
C B through A
4
3
2
1
n_A
0
n_B
1
n_C
3
Un esempio
hanoi(1,C,N_c,B,N_b,A,N_a);
C B through A
3
4
2
1
n_A
0
n_B
2
n_C
2
Si restituisce il controllo al chiamante
Un esempio
hanoi(2,C,N_c,A,N_a,B,N_b);
C A through B
3
4
2
1
n_A
0
n_B
2
Si esegue:
a[n_A]=c[n_C-1];
n_A++;
n_C--;
n_C
2
Un esempio
hanoi(2,C,N_c,A,N_a,B,N_b);
C A through B
4
n_A
2
1
3
1
n_B
2
Si esegue:
a[n_A]=c[n_C-1];
n_A++;
n_C--;
n_C
1
Si invoca
hanoi(1,B,N_b,A,N_a,C,N_c);
Un esempio
hanoi(1,B,N_b,A,N_a,C,N_c);
B A through C
4
n_A
2
1
3
1
n_B
2
n_C
1
Un esempio
hanoi(1,B,N_b,A,N_a,C,N_c);
B A through C
4
n_A
2
1
3
2
n_B
1
n_C
1
Si restituisce il controllo al chiamante
Un esempio
hanoi(2,C,N_c,A,N_a,B,N_b);
C A through B
4
n_A
2
1
3
2
n_B
1
n_C
1
Si restituisce il controllo al chiamante
Un esempio
hanoi(3,C,N_c,B,N_b,A,N_a);
C B through A
4
n_A
2
1
3
2
n_B
1
Si esegue:
b[n_C]=c[n_C-1];
n_B++;
n_C--;
n_C
1
Un esempio
hanoi(3,C,N_c,B,N_b,A,N_a);
C B through A
2
4
1
3
n_A
2
n_B
2
Si esegue:
b[n_C]=c[n_C-1];
n_B++;
n_C--;
n_C
0
Si invoca
hanoi(2,A,N_a,B,N_b,C,N_c);
Un esempio
hanoi(2,A,N_a,B,N_b,C,N_c);
A B through C
2
4
1
3
n_A
2
n_B
2
n_C
0
Si invoca
hanoi(1,A,N_a,C,N_c,B,N_b);
Un esempio
hanoi(1,A,N_a,C,N_c,B,N_b);
A C through B
2
4
1
3
n_A
2
n_B
2
n_C
0
Un esempio
hanoi(1,A,N_a,C,N_c,B,N_b);
A C through B
2
n_A
4
1
3
1
n_B
2
n_C
1
Si restituisce il controllo
al chiamante
Un esempio
hanoi(2,A,N_a,B,N_b,C,N_c);
A B through C
2
n_A
4
1
3
1
n_B
2
Si esegue:
b[n_C]=a[n_C-1];
n_B++;
n_A--;
n_C
1
Un esempio
hanoi(2,A,N_a,B,N_b,C,N_c);
A B through C
3
2
4
1
n_A
0
n_B
3
Si esegue:
b[n_C]=a[n_C-1];
n_B++;
n_A--;
n_C
1
Si invoca:
hanoi(1,C,N_c,B,N_b,A,N_a);
Un esempio
hanoi(1,C,N_c,B,N_b,A,N_a);
C B through A
3
2
4
1
n_A
0
n_B
3
n_C
1
Un esempio
hanoi(1,C,N_c,B,N_b,A,N_a);
C B through A
4
3
2
1
n_A
0
n_B
4
n_C
0
Si restituisce il controllo
al chiamante
Un esempio
hanoi(2,A,N_a,B,N_b,C,N_c);
A B through C
4
3
2
1
n_A
0
n_B
4
n_C
0
Si restituisce il controllo
al chiamante
Un esempio
hanoi(3,C,N_c,B,N_b,A,N_a);
C B through A
4
3
2
1
n_A
0
n_B
4
n_C
0
Si restituisce il controllo
al chiamante
Un esempio
hanoi(4,A,&n_A,B,&n_B,C, &n_C);
A B through C
4
3
2
1
n_A
0
n_B
4
n_C
0
Si restituisce il controllo
al main
Abbiamo correttamente
spostato i dischi dal primo
al secondo piolo
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Ricorsione e vettori
Si scriva una funzione ricorsiva somma_v che
dato un vettore di interi vett produca in output
la somma degli elementi di vett
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Ricorsione e vettori
Si scriva una funzione ricorsiva somma_v che
dato un vettore di interi vett produca in output
la somma degli elementi di vett
– Se il vettore ha un unico elemento allora la somma
dei suoi elementi è pari al valore dell’elemento
– Altrimenti la somma dei primi n elementi è pari al
valore dell’n-esimo elemento + la somma dei primi
n-1 elementi
0
Tale somma è
ottenuta tramite
chiamata ricorsiva
3
2
… -1
9
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
vett
Somma degli elementi di un vettore
/*pre: il vettore ha almeno un elemento*/
int somma_v(int vett[ ], int n)
{
if (n==1)
return (vett[0]);
else
return (vett[n-1]+somma_v(vett,n-1));
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Ricerca di un elemento in un vettore
Si scriva una funzione ricorsiva search_v che dato
un vettore di interi vett ed un intero key determini
se l’elemento key è presente tra gli elementi del
vettore
– Se il vettore ha un unico elemento allora la funzione
restituisce 1 se l’elemento del vettore ha valore pari a
key, 0 altrimenti
– Altrimenti la funzione restituisce 1 se e solo se O
l’elemento key è contenuto nell’ultimo elemento del
vettore OPPURE è contenuto nei primi n-1 elementi del
vettore
0
Tale verifica è
effettuata tramite
chiamata ricorsiva
3
2
… -1
9
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
vett
key=3
Ricerca di un elemento in un
vettore
/*pre: il vettore ha almeno un elemento*/
int search_v(int vett[ ], int n, int key)
{
if (n==1)
return (vett[0]==key);
else
return ((vett[n-1]==key)||
(search_v(vett,n-1,key)));
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Minimo in un vettore
Si scriva una funzione ricorsiva min_v che dato un
vettore di interi vett determini il valore
dell’elemento più piccolo del vettore
– Se il vettore ha un unico elemento allora la funzione
restituisce il valore dell’elemento
– Altrimenti si calcola il valore più piccolo tra i primi n-1
elementi. Se tale valore è più piccolo dell’n-esimo
elemento allora è il valore più piccolo del vettore.
ALTRIMENTI il valore più piccolo del vettore è costituito
dall’n-esimo elemento del vettore
Il valore più piccolo tra i
primi n-1 elementi è
restituito dalla chiamata
ricorsiva
0
3
2
… -1
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
9
vett
Minimo in un vettore
/*pre: il vettore ha almeno un elemento*/
int min_v(int vett[ ], int n)
{
int temp;
if (n==1)
return (vett[0]);
else
{
temp=min_v(vett,n-1);
if (temp<vett[n-1])
return temp;
else
return (vett[n-1]);
}
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizi
Esercizi su stringhe e caratteri
– Versioni iterative
– Versioni ricorsive ® per indicare una
soluzione ricorsiva
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 1
Si scriva una procedura Iterativa che,
dato un testo (di dimensione minore di
max_size), stampi il testo invertito e
senza gli spazi
Si memorizza il testo –tranne gli spaziin una stringa
 si stampano i caratteri della stringa
(dall’ultimo al primo)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 1-caratteri
void elimina_spazi_e_inverti (int max_size)
{
int c,count,i;
char str[max_size];
count=0;
while (((c=getchar()) != EOF) &&(count<max_size))
{
if (c!=‘ ‘)
{
str[count]=c;
Si scriva una procedura
count++;
Iterativa che, dato un
}
testo (di dimensione
}
minore di max_size),
str[count]=‘\0’;
stampi il testo
for (i=count-1;i>=0;i- -)
invertito e senza
printf(“%c”,str[i]);
gli spazi
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 1, versione ricorsiva
Si scriva una procedura ricorsiva che,
dato un testo stampi il testo invertito e
senza gli spazi
Leggi il carattere corrente e memorizzalo in c
Leggi il resto del testo stampandolo invertito e senza gli spazi
Se c è diverso da uno spazio stampa c
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 1-caratteri ®
void Relimina_spazi_e_inverti ()
{
int c;
if ((c=getchar()) != EOF)
{
Relimina_spazi_e_inverti();
if (c!=‘ ‘)
putchar ( c);
}
}
Si scriva una procedura
ricorsiva che, dato un
testo stampa il testo
invertito e senza
gli spazi
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 1-stringhe
/*stampa di una stringa */
void printstringa (char *);
main()
{
char str1[1024];
printf(“inserisci stringa \n”);
scanf(“%s”,str1);
printstringa(str1);
………………………
}
/*Post: stampa il contenuto della stringa*/
void printstringa (char *s)
{
for (;*s!=‘\0’;s++)
putchar(*s);
Prof.ssa Chiara Petrioli -- corso di
}
Si scriva una procedura
iterativa
che, data una stringa
s presa in
input ne stampi i caratteri
in output
programmazione 1, a.a. 2006/2007
OPPURE:
void printstringa (char *s)
{
int i;
for (i=0;s[i]!=‘\0’;i++)
putchar(s[i]);
}
Esercizio 1-stringhe
Si scriva una procedura ricorsiva
che, data una stringa s presa in input ne
stampi i caratteri in output
Stampa l’elemento corrente
Stampa il resto degli elementi della stringa
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 1-stringhe ®
/*stampa di una stringa (ricorsiva)*/
void Rprintstringa (char *);
main()
{
char str1[1024];
printf(“inserisci stringa \n”);
scanf(“%s”,str1);
Rprintstringa(str1);
………………………
}
Come dovremmo modificare il codice
per stampare i caratteri della stringa in
ordine inverso?
Si scriva una procedura
ricorsiva
che, data una stringa
s presa in
input ne stampi i caratteri
in output
/*Post: stampa il contenuto della stringa*/
void Rprintstringa (char *s)
{
if (*s != '\0')
{
Attenzione: qui abbiamo usato
putchar(*s);
l’aritmetica dei puntatori per
Rprintstringa (s+1);
chiamare la funzione ricorsiva
Prof.ssa Chiara Petrioli
corso di della stringa, escluso
}
sul--resto
programmazione 1, a.a. 2006/2007
}
l’elemento corrente
Esercizio 2-stringhe
Si scriva una procedura ricorsiva
che, data una stringa s presa in input ne
stampi i caratteri in output in ordine
inverso
Memorizza l’elemento corrente in c
Stampa il resto degli elementi della stringa in ordine inverso
Stampa quanto memorizzato in c
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 2-stringhe ®
/*stampa di una stringa (ricorsiva)*/
void Rprintstringa_invertita (char *);
main()
{
char str1[1024];
printf(“inserisci stringa \n”);
scanf(“%s”,str1);
Rprintstringa_invertita(str1);
………………………
}
Si scriva una procedura
ricorsiva
che, data una stringa
s presa in
input ne stampi i caratteri
in output in ordine
invertito
/*Post: stampa il contenuto della stringa invertito*/
void Rprintstringa_invertita (char *s)
{
if (*s != '\0')
{
Rprintstringa_invertita(s+1);
putchar(*s);
Prof.ssa Chiara Petrioli -- corso di
}
programmazione 1, a.a. 2006/2007
}
Cosa succede in memoria…
L’invocazione della chiamata
All’entrata
nella
funzione
si alloca memoria per il
ricorsiva
farà stampare
in ordine
inverso
il restopunta
della stringa
a partire
puntatore
s che
al primo
elemento della
dal secondo carattere
stringa(s+1)
corrente
è la locazione di memoria
dove è memorizzato il secondo
Non siamo
arrivati
al carattere di fine stringa
carattere
della stringa
quindi eul
si invoca la chiamata ricorsiva
7200
void Rprintstringa_invertita (char *s)
{
if (*s != '\0')
{
Rprintstringa_invertita(s+1);
putchar(*s);
}
}
b
l
7200
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
u
e
\0
s
Cosa succede in memoria…
L’invocazione della chiamata
All’entrata
nella
funzione
si alloca memoria per il
ricorsiva
farà stampare
in ordine
inverso
il restopunta
della stringa
a partire
puntatore
s che
al primo
elemento della
dal secondo carattere
stringa(s+1)
corrente
è la locazione di memoria
dove è memorizzato il secondo
Non siamo
arrivati
al carattere di fine stringa
carattere
della stringa
quindi eul
si invoca la chiamata ricorsiva
7200
void Rprintstringa_invertita (char *s)
{
if (*s != '\0')
{
Rprintstringa_invertita(s+1);
putchar(*s);
}
}
b
l
7200
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
u
e
\0
Basterà quindi stampare il
carattere puntato da s
eulb
s
Esercizio 3-stringhe
/*calcola la lunghezza di una stringa */
int String_length(char *);
main()
{
char str1[1024];
printf(“inserisci una stringa \n”);
scanf(“%s”,str1);
printf(“la lunghezza della stringa e’ %d \n”, String_length(str1));
………………………
}
/*calcola la lunghezza della stringa*/
int String_length(char *s1)
{
int count=0:
while (*s1 != ‘\0’)
{
count++;
s1++;
}
return count;
}
Si scriva una funzione
iterativa
che, data una stringa
ne calcoli il numero
di caratteri (escluso
il carattere di fine stringa)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esercizio 3-stringhe ®
/*calcola il numero di caratteri in una stringa*/
int Rsizestringa (char *, int);
main()
{
char str1[1024];
printf(“inserisci stringa \n”);
scanf(“%s”,str1);
printf(“il numero di caratteri della stringa e’ %d \n”,
Rsizestringa(str1,0) );
………………………
}
/*calcola il numero di caratteri in una stringa*/
/*Pre: s stringa, i>=0, chiamato con i==0 */
/*Post: restituisce il numero di caratteri della
stringa (escluso il carattere di fine stringa */
int Rsizestringa(char s[ ], int i)
{
if(s[i]=='\0')
return 0;
else
return (1+Rsizestringa(s,i+1));
}
Si scriva una procedura
ricorsiva
che, data una stringa
s presa in
input calcoli il numero
di caratteri della
stringa (escluso il
carattere di fine stringa)
OPPURE:
int Rsizestringa (char *s)
{
if (*s == '\0')
return 0;
else
return (1+Rsizestringa(s+1));
}
Manipolazione di reali in C
I numeri reali sono rappresentati in binario
nel computer
1/10=0.1 è rappresentato nella forma
frazionaria binaria come
0.00011001100110011001100110011001100
11001100110011...
La rappresentazione dei reali è binaria. Alcuni numeri che ci
Sembrerebbero perfettamente rappresentabili hanno dei problemi
di rappresentazione in binario.
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Manipolazione di reali in C
Ragionando in base 10 è facile comprendere un
problema:
Consideriamo la frazione 1/3
Corrisponde ad un numero periodico
– 0.333….
I numeri reali in una macchina sono memorizzati con
un numero limitato di byte  si perde in precisione
nella rappresentazione
 Il problema non riguarda solo i numero periodici!
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Errore nella rappresentazione dei
reali
Abbiamo un numero limitato di byte (es. 8)
per rappresentare un double.
Tra quanti numeri è possibile distinguere
usando 8*8=64 bit?
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Errore nella rappresentazione dei
reali
Abbiamo un numero limitato di byte (es. 8)
per rappresentare un double.
immaginate
che
il numero reale
che si trova nel
Tra quantiSe
numeri
è
possibile
distinguere
mezzo dell’intervallo sia rappresentato con la sequenza
di bit che è
associata all’intervallo, e che tutti gli altri
usando 8*8=64
bit?
valori che cadono nell’intervallo siano approssimati
con tale sequenza di bit l’errore massimo è q/2 con
264
q ampiezza dei sottointervallini.
c’è un errore di rappresentazione
 maggiore il numero di bit minore l’errore di rappresentazione
Che comunque non può essere totalmente annullato
L’intervallo dei reali rappresentati è quindi diviso in 264 sottointervallini
Non possiamo avere una rappresentazione dell’intervallo continuo
dei
Prof.ssa Chiara
Petrioli
corso di
È unnumeri
errorereali
di rappresentazione
che
ci --portiamo
dietro e che può anche
programmazione 1, a.a. 2006/2007
Accumularsi facendo operazioni sui reali
Esempio
Nel caso di 0.1
La stampa del valore decimale
dell’approssimazione binaria del numero
fornisce il seguente risultato
0.10000000000000001
Non è un bug! Come abbiamo visto dipende dalla rappresentazione
dei numeri reali
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
Esempio
Fare operazioni sui reali può portare a
sorprese
sum = 0.0
for (i=0;i<10;i++)
sum += 0.1;
Il valore di sum all’uscita dal ciclo è:
0.99999999999999989
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2006/2007
In sintesi
La rappresentazione dei reali porta ad approssimazioni,
che possono accumularsi o bilanciarsi facendo operazioni
sui reali
– Non è un bug, è q.sa di intrinseco nella rappresentazione di un
intervallo continuo in una macchina
Cosa si può fare:
– tenerne conto nello scrivere un programma (nessuna soluzione
prefatta, criteri generali-vedi qui di seguito- e buon senso portano
alla soluzione)
– Ad esempio anziché testare se A=B nel caso in cui A e B siano
diversi, testare se A e B sono pressochè uguali |A-B|<= epsilon
(cercando così di filtrare problemi di rappresentazione che si
ripercuotono tipicamente sulle cifre meno significative).
– Esistono librerie ‘a precisione infinita’ (o meglio a precisione
arbitraria)libreria BigDigits
Non sono a precisione infinita ma cercano di allocare dinamicamente
maggiore o minore memoria per memorizzare i numeri reali in modo da
aumentare l’accuratezza con cui sono rappresentati
 Memorizzano in strutture dati a dimensione variabile i numeri reali
 Rallentano l’esecuzione