Corso di Fondamenti di
programmazione a.a.
2009/2010
Prof.ssa Chiara Petrioli
Corso di Laurea in Informatica
Università degli Studi “La Sapienza”
(lezioni 12-15)
Puntatori e ricorsione
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Puntatori
I puntatori sono delle variabili che come
valore contengono
deglidevono
indirizzi
Variabili di tipo puntatore
essere di
e inizializzate
memoriadichiarate
Es.
int * countPtr; /*dichiarazoine*/
int count;
float * fcountPtr;
Il nome di una variabile intera (es. count) fa
count contiene
un _valore_
intero
direttamente
riferimento ad
un valore intero;
countPtr = &count; /*inizializzazione*/
Una variabile puntatore fa indirettamente riferimento
fcountPtr=NULL;
int *countPtr;
ad un valore intero (deriferimento).
/*NULL è una costante simbolica predefinita
In molti file
di intestazione
incluso stdio.h.
Se
 La variabile
countPtr
contiene
l’indirizzo
una variabile puntatore è inizializzata a NULL non
di una locazione
memoria
che contiene
punta ad alcunadi
locazione
di memoria*/
un valore intero.
5
2340
countPtr
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
2340
Operatore di indirizzo
& (operatore unario di indirizzo) restituisce
l’indirizzo di memoria associato al suo
operando;
int y=5;
int *yPtr;
yPtr=&y;
3200
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
5
y
Operatore di indirizzo
& deve essere
applicato ad una
variabile. Non
& (operatore unario
di indirizzo)
restituisce
Può essere applicato a costanti, espressioni o
l’indirizzo di amemoria
associato
al suo
variabili dichiarate
con la specifica
di classe
di memoria register
operando;
int y=5;
int *yPtr;
yPtr=&y;
5
3200
3200
y
yPtr
Viene allocata memoria per la variabile puntatore
yPtr. Nella locazione di yPtr viene memorizzato
Prof.ssa Chiaradi
Petrioli
-- Fondamenti
di
l’indirizzo
memoria
associato
alla variabile y
programmazione, a.a. 2009/2010
Operatore di deriferimento
L’operatore * (detto operatore di
deriferimento o di risoluzione dell’indirizzo)
consente di accedere al valore contenuto
nella locazione di memoria puntata da una
variabile puntatore
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Operatore di deriferimento
L’operatore * (detto operatore di
deriferimento o di risoluzione dell’indirizzo)
consente di accedere al valore contenuto
nella locazione di memoria puntata da una
variabile puntatore
*yPtr è il valore contenuto nella
locazione di memoria il cui
indirizzo è memorizzato in yPtr
3200
5
5
3200
yPtr
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
y
Esempio
La specifica di conversione %p
di printf consente di stampare
in output indirizzi di locazioni di
memoria
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esempio
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Precedenza degli operatori
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Chiamata per riferimento delle
funzioni
Come può essere realizzata in C?
Se vogliamo poter modificare il contenuto
di una variabile x con cui invochiamo una
funzione e far sì che tali modifiche
permangano anche all’uscita dalla
funzione possiamo usare come parametro
formale un puntatore (quindi passare lalla
funzione l’indirizzo di x)…
Un esempio..
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esempio
/*eleva al cubo una variabile usando una chiamata per
valore*/
#include <stdio.h>
int cubeByValue(int);
main()
{
int number =5;
printf(“Il valore originale del numero è: %d\n”,number);
number=cubeByValue(number);
printf(“il nuovo valore del numero è: %d\n”,number);
return 0;
}
int cubeByValue(int n)
Il valore originale del numero è: 5
Il nuovo valore del numero è: 125
{
return n*n*n;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
}
Cosa succede in memoria…
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esempio 2
/*eleva al cubo una variabile usando una chiamata per
riferimento*/
#include <stdio.h>
void cubeByReference(int *);
main()
{
int number =5;
printf(“Il valore originale del numero è: %d\n”,number);
cubeByReference(&number);
printf(“il nuovo valore del numero è: %d\n”,number);
return 0;
}
void cubeByReference(int *nPtr)
Il valore originale del numero è: 5
Il nuovo valore del numero è: 125
{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
}
Cosa succede in memoria…
int number=5;
cubeByReference(&number);
number
5
6200
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
int number=5;
cubeByReference(&number);
number
6200
5
Viene copiato in nPtr il valore
dell’argomento con cui è stata
invocata la funzione
&number OVVERO l’indirizzo
della locazione di memoria della
variabile number OVVERO 6200
Invochiamo la funzione cubeByReference
6200
Viene allocata memoria
per la variabile puntatore
nPtr
void cubeByReference(int *nPtr)
{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
int number=5;
cubeByReference(&number);
number
5
6200
*nPtr è il valore contenuto
nella locazione di memoria
puntata da nPtr
5
L’istruzione quindi dice di
elevare al cubo 5 e di memorizzare
il valore risultante nella locazione di
memoria puntata da nPtr
Invochiamo la funzione cubeByReference
6200
Si esegue l’istruzione
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);
void cubeByReference(int *nPtr)
{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
int number=5;
cubeByReference(&number);
number
125
5
6200
L’istruzione quindi dice di
elevare al cubo 5 e di memorizzare
il valore risultante nella locazione di
memoria puntata da nPtr
Il cubo di 5 è 125
Invochiamo la funzione cubeByReference
6200
void cubeByReference(int *nPtr)
{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
int number=5;
cubeByReference(&number);
printf(“il nuovo valore del numero è:
%d\n”,number);
return 0;
number
125
5
Si stampa il valore di number
 125
6200
Si ritorna il controllo al main che esegue
la prossima istruzione
6200
La memoria allocata per
nPtr viene rilasciata
void cubeByReference(int *nPtr)
{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
Passaggio per valore evita di compromettere i valori delle variabili
con cui sono invocate le funzioni (spesso non si vogliono modificare
tali valori)
Passaggio parametri per riferimento evita di dover allocare, ad ogni invocazione
di funzione, memoria per copiare quantità di dati di input grandi che possono
dover essere passati alla funzione
esempio: se la funzione ha come input un vettore abbiamo bisogno
solo di un parametro di tipo puntatore in cui copiare la locazione di
memoria associata al primo elemento del vettore
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Qualificatore const
Consente di specificare che il valore di una
particolare variabile NON dovrà essere
modificato
Il compilatore intercetterà qualsiasi tentativo di
modificare una variabile che sia stata dichiarata
const e, nel caso in cui tale variabile sia
modificata, darà un errore o un warning.
 serve a proteggere da errori
nell’implementazione del codice rendere più
facile il debugging
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Modi di passare un puntatore a una
funzione
‘Puntatore variabile a dati variabili’
– i dati possono essere modificati attraverso il
puntatore
– Il valore della variabile puntatore potrà essere
modificato in modo che il puntatore possa fare
riferimento ad altri dati
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esempio
#include <stdio.h>
void convertToUppercase (char *);
main()
{
char string[ ]=“caratteri”;
printf(“la stringa prima della conversione è %s\n”,string);
convertToUppercase(string); /*converte le lettere minuscole della stringa in
maiuscole*/
printf(“dopo la conversione la stringa è %s\n”,string);
return 0;
}
void convertToUppercase(char *s)
{
Vengono modificati i caratteri della
while (*s != ‘\0’)
Stringa.
{
s punta a caratteri diversi della stringa
if (*s >= ‘a’ && *s<= ‘z’)
durante l’esecuzione della funzione
*s-=32;
++s;
}
La stringa prima della conversione è:pippo
}
Prof.ssa Chiara
Petrioli
Fondamenti di
Dopo
la --conversione
la stringa è PIPPO
programmazione, a.a. 2009/2010
Altri casi…
Puntatore variabile a dati costanti (i dati non possono essere
modificati)
#include <stdio.h>
void printCharacters (const char *);
main()
{
char string [ ]=“stampa i caratteri”;
printf (“la stringa è:\n”);
printCharacters (string);
putchar(‘\n’);
return 0;
}
void printCharacters(const char *s)
{
for (;*s!=‘\0’;s++)
putchar(*s);
}
la stringa è:
Prof.ssa Chiara Petrioli -- Fondamenti
di i caratteri
stampa
programmazione, a.a. 2009/2010
Altri casi…
Puntatore costante a dati variabili
– il puntatore fa sempre riferimento alla stessa
locazione di memoria
– Tramite il puntatore si può cambiare il valore della
locazione di memoria
int *const ptr;
Puntatore costante a dati costanti
– il puntatore fa sempre riferimento alla stessa
locazione di memoria
– Il valore della locazione di memoria non può essere
modificato
const int *const ptr;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esempio
#include <stdio.h>
main ()
{
int x=5,y;
const int *const ptr=&x;
Cannot modify a const object
*ptr=7;
Cannot modify a const object
ptr=&y;
return 0;
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Bubblesort (versione 2)
#include <stdio.h>
#define SIZE 10
void bubbleSort(int *,const int);
void swap (int *,int*);
main()
{
int i,a[SIZE]={2,6,4,8,10,12,89,68,45,37};
printf(“ordine originale \n”);
for (i=0;i<=SIZE-1;i++)
printf(“%d”,a[i]);
bubbleSort (a,SIZE);
printf(“dati in ordine crescente \n”);
for (i=0;i<=SIZE-1;i++)
printf(“%d”,a[i]);
printf(“\n”);
return 0;
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Bubblesort
void bubbleSort(int *array, const int size)
{
int pass,j;
for (pass=1;pass <=size-1;pass++)
for (j=0;j<=size-2;j++)
if(array[j]>array[j+1])
swap(&array[j],&array[j+1]);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Swap
void swap (int *element1Ptr, int
*element2Ptr)
{
int temp;
temp=*element1Ptr;
*element1Ptr=*element2Ptr;
*element2Ptr=temp;
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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
Petrioli
Fondamenti
di
il tipo di datoProf.ssa
 inChiara
modo
da--far
puntare
all’elemento precedente
programmazione, a.a. 2009/2010
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
Prof.ssa
Chiara Petrioli
-- Fondamenti
ditipo siano immagazzinate in
Non si può assumere
che
variabili
dello
stesso
per contenere
un
intero)in
questo
caso 99
programmazione, a.a. 2009/2010
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 -- Fondamenti
di
Attenzione: il nome del vettore
un puntatore
costante
punterà sempre alla
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
}
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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
-- Fondamenti
di
Invoca
laPetrioli
funzione
puntata
da compare con
programmazione,
a.a.
2009/2010
}
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 -- Fondamenti di
programmazione, a.a. 2009/2010
}
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
}
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Argomenti avanzati sulle variabili e
funzioni…
Classi di memoria
Regole di scope
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Classi di memoria
Una variabile ha associato un tipo, un nome, una
dimensione ed un valore
Altri attributi di un identificatore (e.g. variabile,
nome di funzione) usato in un programma 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 all’
identificatore)
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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 registro
una
variabile
Prof.ssa
Chiara
Petrioli -- Fondamenti di
si esce dalla
programmazione, a.a. 2009/2010
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-- Fondamenti
count=1;
Prof.ssa Chiara
Petrioli
di
programmazione, a.a. 2009/2010
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
Prof.ssadefinizioni
Chiara Petrioli -- di
Fondamenti
di
Esempi: variabili globali,
funzioni,
programmazione, a.a. 2009/2010
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à
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
#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 -- Fondamenti di
esterno del
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
#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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
#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 -- Fondamenti di
programmazione, a.a. 2009/2010
#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 -- Fondamenti di
programmazione, a.a. 2009/2010
#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 -- Fondamenti di
programmazione, a.a. 2009/2010
#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 -- Fondamenti di
programmazione, a.a. 2009/2010
#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 -- Fondamenti di
programmazione, a.a. 2009/2010
Chiamata a funzione-cosa succede
in memoria
Il call stack è una struttura dati speciale
(stack o pila) usata dal sistema per gestire
le informazioni di una funzione attiva (che
è stata chiamata e non ha ancora
completato la sua esecuzione)
Cosa memorizza
– indirizzo di ritorno
– variabili locali
– parametri passati alla funzione
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Call stack
Funzionamento:
ogni volta che si invoca una funzione si inserisce
nello stack l’indirizzo di ritorno ed i vari parametri
del chiamante
ogni volta che termina l’esecuzione di una
funzione questa passa il controllo all’indirizzo
memorizzato nello stack
– In questo modo si sa da dove riprendere l’esecuzione
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Call stack
Un call stack è composto da call frames (uno per ogni
funzione)
Esempio: se una funzione DrawSquares chiama una
funzione DrawLine (che è quella attualmente in esecuzione) il
call stack conterrà informazioni di questo tipo
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio. Come si implementa una
pila con i vettori?
Struttura dati in cui memorizzare
informazioni. Supponete di saper definire
un tipo di dato record che contenga le
informazioni di ciascun stack frame e che
se x è una variabile di tipo record e y è
una variabile di tipo record possiate
scrivere istruzioni tipo y=x.
– Un nuovo record viene inserito in cima (push)
– E’ possibile rimuovere e leggere solo
l’elemento in cima (pop)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Gestione a pila
Come realizzereste la pila usando i vettori?
record Pila[MAX_DIM];
int top_Stack;
Assumete di avere a disposizione due funzioni
isempty (record P[ ], int N, int topstack) e isfull
(record P[ ], int N, int topstack) in grado di dirvi
se lo stack è vuoto o è pieno (e quindi non
possono essere inseriti altri record)
come potete realizzare la funzioni pop e push?
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Funzioni isempty e isfull
int isempty (record P[ ], int N, int topstack)
{
return (topstack==0);
}
int isfull (record P[ ], int N, int topstack)
{
return (topstack==N);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Funzioni pop e push
/* pre: la funzione viene invocata solo su pile non vuote*/
record pop(record P[ ], int N, int* top_stack)
{
record temp_r;
temp_r= P[*top_stack];
*top_stack=*top_stack-1;
return temp_r;
void push (record P[ ], int N, int* top_stack, record R)
{
if (! isfull(P,N,top_stack))
{
P[*top_stack]=R;
*top_stack+=1;
}
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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
VERSIONE
ITERATIVA
invocazione
per calcolare
il fattoriale di n
int fattoriale_iter(int
number)
{
– Possiamo
sfruttare il fatto che n!=n*(n-1)!
int counter;
– Per calcolare
il fattoriale di n invoco la funzione
int factorial=1;
fatt su n-1
e moltiplico ilcounter>=1;
risultatocounter--)
per n
for (counter=number;
Abbiamo ridotto
la complessità del problema
factorial*=counter;
esprimendo
return factorial;
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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
La memoria allocata per Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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);
}
fatt(3)
Prof.ssa Chiara Petrioli -- Fondamenti di fatt(2)
programmazione, a.a. 2009/2010
restituisce 1
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)
fatt(3)
Prof.ssa Chiara Petrioli -- Fondamenti di fatt(2)
programmazione, a.a. 2009/2010
restituisce 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)
fatt(3)
Prof.ssa Chiara Petrioli -- Fondamenti di fatt(2)
programmazione, a.a. 2009/2010
restituisce 6
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)
fatt(3)
Prof.ssa Chiara Petrioli -- Fondamenti di fatt(2)
programmazione, a.a. 2009/2010
restituisce 24
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
ogni problema che ammette una soluzione ricorsiva ammette anche
una soluzione iterativa
TUTTAVIA ragionare in modo ricorsivo è molto utile e vedrete di qui a
poco (corso del secondo semestre/algoritmi) 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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 Prof.ssa
memoria
viene dirilasciata
Chiaraallocata
Petrioli -- Fondamenti
programmazione, a.a. 2009/2010
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 Prof.ssa
memoria
viene dirilasciata
Chiaraallocata
Petrioli -- Fondamenti
programmazione, a.a. 2009/2010
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 Prof.ssa
memoria
viene dirilasciata
Chiaraallocata
Petrioli -- Fondamenti
programmazione, a.a. 2009/2010
Ha restituito 4
Un terzo esempio
Calcolo di a*b
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Un terzo esempio
Calcolo di a*b
a*b= a+a+…
…+a
b volte
a*b=(a*(b-1))+a
Caso base
a*0=0
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Moltiplicazione tra due interi
int prodotto (int a,int b)
{
if (b==0)
return 0;
else
return (prodotto(a,b-1)+a);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 Petrioli
-- Fondamenti di
verrà valutata
prima
la chiamata
programmazione, a.a. 2009/2010
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
4000
n
SECONDA INVOCAZIONE DI
FIBONACCI
Attenzione: non si può sapere se
Prof.ssa
Chiara Petrioli
-- Fondamenti di
verrà valutata
prima
la chiamata
programmazione, a.a. 2009/2010
Fibonacci(1) O Fibonacci(0)
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti
di
n complessità
2
esponenziale
programmazione, a.a. 2009/2010
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 un
-- Fondamenti
di
chiamate elevato significa che
paghiamo
overhead
elevato (tempo e
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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!
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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.
Nella mossa successiva il
disco azzurro può essere
spostato da A a 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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di B
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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 prima locazione
int i,n,n_A,n_B,n_C;
al primo
piolopiolo (ed il loro ordine)
Numero
Vettore
dilibera
dischi
che relativa
rappresenta
il primo
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti
di
contenuto
e num. Di elementi del
programmazione,
a.a.
2009/2010
}
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)
{
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 -- Fondamenti di
programmazione, a.a. 2009/2010
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);
Prof.ssa
AC through
B Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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);
Prof.ssa
AB through
C Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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);
Prof.ssa
AC through
B Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
0
n_C
c[n_C]=a[n_A-1];
n_A--;
n_C++;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
0
n_C
c[n_C]=a[n_A-1];
n_A--;
n_C++;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
0
n_C
b[n_B]=a[n_A-1];
n_A--;
n_B++;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti
di
programmazione, a.a. 2009/2010
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 controlloProf.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
2
n_C
Si esegue:
c[n_C]=a[n_A-1];
n_A--;
n_C++;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
2
n_C
Si esegue:
c[n_C]=a[n_A-1];
n_A--;
n_C++;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
n_C
Aveva invocato:
hanoi (1, B, N_b, A, N_a, C, N_c);
BA through C
Tale invocazione ha terminato
restituendo il controllo
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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++;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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--;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
1
n_C
Si invoca
hanoi(3,C,N_c,B,N_b,A,N_a);
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
1
n_C
Si invoca
hanoi(2,C,N_c,A,N_a,B,N_b);
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
1
n_C
Si invoca
hanoi(1,C,N_c,B,N_b,A,N_a);
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
n_C
Si esegue:
a[n_A]=c[n_C-1];
n_A++;
n_C--;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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);
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
n_C
Si esegue:
b[n_C]=c[n_C-1];
n_B++;
n_C--;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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);
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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);
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
n_C
Si esegue:
b[n_C]=a[n_C-1];
n_B++;
n_A--;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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);
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
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 -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizi di consolidamento delle conoscenze
Cicli e costrutti annidati
Matrici
Funzioni
Lettura e scrittura da
I/O e da file
Puntatori
Ricorsione
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Vettori
Stringhe
Strutture e liste
Calcolo del minimo comun divisore
di due numeri
Il massimo comune divisore (M.C.D.) di due
numeri interi, che non siano entrambi uguali a
zero, è il numero naturale più grande per il quale
possono entrambi essere divisi.
Algoritmo di Euclide: Dati due numeri naturali a
e b, si controlla se b è zero. Se lo è, a è il MCD.
Se non lo è, si divide a / b e si assegna ad r il
resto della divisione (r=a%b). Se r = 0 allora si
può terminare affermando che b è il MCD
cercato altrimenti occorre assegnare a = b e b =
r e si ripete nuovamente la divisione.
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Funzione ricorsiva per il calcolo di
MCD
int mcd(int a, int b)
{
if (b == 0) return a;
else return mcd(b, a % b);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 1
Si scriva una funzione che dati due vettori
ordinati di interi t1 e t2 e date le loro
dimensioni d1 e d2 calcoli la loro
intersezione (memorizzandola in un terzo
vettore t3 dato in input). La funzione
restituira’ la cardinalita’ dell’insieme
intersezione.
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 1
int intersezione(int *t1, int d1, int *t2, int d2, int *t3)
{
int i,j,cnt;
i=j=cnt=0; /* inzializzo i contatori */
while((i<d1) && (j < d2))
{
if (t1[i]==t2[j])
{
/* ho trovato un elemento comune */
*(t3+cnt)=t1[i]; /* salvo in t3 l'elemento comune */
++cnt; /* incremento cnt */
++i; /* incremento i */
++j; /* incremento j*/
}
else if (t1[i]<t2[j])
i++; /* incremento solo il minimo tra i due */
else
j++;
}
return cnt;
Prof.ssa Chiara Petrioli -- Fondamenti di
}
programmazione, a.a. 2009/2010
Esercizio 2
Si scriva una funzione che dato un vettore
ed una sua dimensione, inverta il vettore
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 2
Versione iterativa esercizio 2
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 3
Si scriva una funzione ricorsiva che dato
un vettore ed un intervallo di indici degli
elementi del vettore [min,max] inverta la
parte del vettore con indici in questo
intervallo
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione ricorsiva esercizio 3
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 4
Si scriva una funzione ricorsiva che calcoli
il massimo di un vettore
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 4
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 5
Si scriva una funzione ricorsiva che dato
un vettore calcoli la somma dei suoi
elementi
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 5
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizi di consolidamento delle conoscenze
Cicli e costrutti annidati
Matrici
Funzioni
Lettura e scrittura da
I/O e da file
Puntatori
Ricorsione
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Vettori
Stringhe
Strutture e liste
Esercizio 1
Si scriva una funzione ricorsiva che data
una stringa la stampi
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 1
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 2
Si scriva una funzione ricorsiva che data
una stringa ne stampi i caratteri dall’ultimo
al primo
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 2
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 3
Si scriva una funzione ricorsiva che data
una stringa calcoli il numero dei suoi
elementi (notazione vettore e indice)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 3
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 5
Si scriva una funzione ricorsiva che data
una stringa ed un carattere restituisce il
puntatore alla prima occorrenza del
carattere nella stringa, NULL se tale
carattere non compare nella stringa
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 5
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 6
Si scriva una funzione ricorsiva che data
una stringa ed un carattere restituisca il
puntatore all’ultima occorrenza del
carattere nella stringa
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 6
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 4
Si scriva una funzione ricorsiva che calcoli
il numero di caratteri di una stringa a
partire da un determinato carattere della
stringa (il puntatore a tale carattere iniziale
viene fornito in input)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione esercizio 4
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010