Post on 01-May-2015
transcript
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Corso di Fondamenti di Corso di Fondamenti di programmazione a.a. programmazione a.a.
2009/20102009/2010Prof.ssa Chiara PetrioliProf.ssa Chiara Petrioli
Corso di Laurea in InformaticaCorso di Laurea in InformaticaUniversità degli Studi “La Sapienza”Università degli Studi “La Sapienza”
(lezioni 12-15)(lezioni 12-15)Puntatori e ricorsione
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
PuntatoriPuntatori
I puntatori sono delle variabili che come I puntatori sono delle variabili che come valore contengono degli indirizzi di valore contengono degli indirizzi di memoriamemoriaint count;int count;
count contiene un count contiene un _valore__valore_ intero intero int *countPtr;int *countPtr;
La variabile countPtr contiene l’indirizzo La variabile countPtr contiene l’indirizzo di una locazione di memoria che contiene di una locazione di memoria che contiene un valore intero.un valore intero.
2340
countPtr
5 2340
Il nome di una variabile intera (es. count) fadirettamente riferimento ad un valore intero;Una variabile puntatore fa indirettamente riferimentoad un valore intero (deriferimento).
Variabili di tipo puntatore devono esseredichiarate e inizializzateEs.int * countPtr; /*dichiarazoine*/float * fcountPtr;
countPtr = &count; /*inizializzazione*/fcountPtr=NULL; /*NULL è una costante simbolica predefinitaIn molti file di intestazione incluso stdio.h. Se una variabile puntatore è inizializzata a NULL non punta ad alcuna locazione di memoria*/
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Operatore di indirizzoOperatore di indirizzo
& (operatore unario di indirizzo) restituisce & (operatore unario di indirizzo) restituisce l’indirizzo di memoria associato al suo l’indirizzo di memoria associato al suo operando;operando;
int y=5;int y=5;
int *yPtr;int *yPtr;
yPtr=&y;yPtr=&y;
5 y3200
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Operatore di indirizzoOperatore di indirizzo
& (operatore unario di indirizzo) restituisce & (operatore unario di indirizzo) restituisce l’indirizzo di memoria associato al suo l’indirizzo di memoria associato al suo operando;operando;
int y=5;int y=5;
int *yPtr;int *yPtr;
yPtr=&y;yPtr=&y;
5 y3200
Viene allocata memoria per la variabile puntatoreyPtr. Nella locazione di yPtr viene memorizzatol’indirizzo di memoria associato alla variabile y
yPtr3200
& deve essere applicato ad una variabile. Non Può essere applicato a costanti, espressioni oa variabili dichiarate con la specifica di classedi memoria register
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Operatore di deriferimentoOperatore di deriferimento
L’operatore * (detto operatore di L’operatore * (detto operatore di deriferimentoderiferimento o di o di risoluzione dell’indirizzorisoluzione dell’indirizzo) ) consente di accedere al consente di accedere al valorevalore contenuto contenuto nella locazione di memoria puntata da una nella locazione di memoria puntata da una variabile puntatorevariabile puntatore
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Operatore di deriferimentoOperatore di deriferimento
L’operatore * (detto operatore di L’operatore * (detto operatore di deriferimentoderiferimento o di o di risoluzione dell’indirizzorisoluzione dell’indirizzo) ) consente di accedere al consente di accedere al valorevalore contenuto contenuto nella locazione di memoria puntata da una nella locazione di memoria puntata da una variabile puntatorevariabile puntatore
5 y3200
yPtr3200
*yPtr è il valore contenuto nellalocazione di memoria il cui indirizzo è memorizzato in yPtr
5
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
EsempioEsempioLa specifica di conversione %pdi printf consente di stampare in output indirizzi di locazioni dimemoria
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
EsempioEsempio
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Precedenza degli operatoriPrecedenza degli operatori
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Chiamata per riferimento delle Chiamata per riferimento delle funzionifunzioni
Come può essere realizzata in C?Come può essere realizzata in C?Se vogliamo poter modificare il contenuto Se vogliamo poter modificare il contenuto di una variabile x con cui invochiamo una di una variabile x con cui invochiamo una funzione e far sì che tali modifiche funzione e far sì che tali modifiche permangano anche all’uscita dalla permangano anche all’uscita dalla funzione possiamo usare come parametro funzione possiamo usare come parametro formale un puntatore (quindi passare lalla formale un puntatore (quindi passare lalla funzione l’indirizzo di x)…funzione l’indirizzo di x)…Un esempio..Un esempio..
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
EsempioEsempio/*eleva al cubo una variabile usando una chiamata per /*eleva al cubo una variabile usando una chiamata per
valore*/valore*/#include <stdio.h>#include <stdio.h>int cubeByValue(int);int cubeByValue(int);main()main(){{
int number =5;int number =5;printf(“Il valore originale del numero è: %d\n”,number);printf(“Il valore originale del numero è: %d\n”,number);number=cubeByValue(number);number=cubeByValue(number);printf(“il nuovo valore del numero è: %d\n”,number);printf(“il nuovo valore del numero è: %d\n”,number);return 0;return 0;
}}int cubeByValue(int n)int cubeByValue(int n){{
return n*n*n;return n*n*n;}}
Il valore originale del numero è: 5Il nuovo valore del numero è: 125
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Cosa succede in memoria…Cosa succede in memoria…
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Cosa succede in memoria…Cosa succede in memoria…
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Cosa succede in memoria…Cosa succede in memoria…
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Esempio 2Esempio 2/*eleva al cubo una variabile usando una chiamata per /*eleva al cubo una variabile usando una chiamata per
riferimento*/riferimento*/#include <stdio.h>#include <stdio.h>voidvoid cubeByReference(int *); cubeByReference(int *);main()main(){{
int number =5;int number =5;printf(“Il valore originale del numero è: %d\n”,number);printf(“Il valore originale del numero è: %d\n”,number);cubeByReference(&number);cubeByReference(&number);printf(“il nuovo valore del numero è: %d\n”,number);printf(“il nuovo valore del numero è: %d\n”,number);return 0;return 0;
}}void cubeByReference(int *nPtr)void cubeByReference(int *nPtr){{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);*nPtr=(*nPtr)*(*nPtr)*(*nPtr);}}
Il valore originale del numero è: 5Il nuovo valore del numero è: 125
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Cosa succede in memoria…Cosa succede in memoria…int number=5;cubeByReference(&number);cubeByReference(&number);
5number 6200
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Cosa succede in memoria…Cosa succede in memoria…int number=5;cubeByReference(&number);cubeByReference(&number);
5number 6200
void cubeByReference(int *nPtr)void cubeByReference(int *nPtr){{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);*nPtr=(*nPtr)*(*nPtr)*(*nPtr);}}
Invochiamo la funzione cubeByReference
Viene allocata memoriaper la variabile puntatorenPtr
Viene copiato in nPtr il valoredell’argomento con cui è statainvocata la funzione&number OVVERO l’indirizzodella locazione di memoria dellavariabile number OVVERO 6200
6200
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Cosa succede in memoria…Cosa succede in memoria…int number=5;cubeByReference(&number);cubeByReference(&number);
5number 6200
void cubeByReference(int *nPtr)void cubeByReference(int *nPtr){{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);*nPtr=(*nPtr)*(*nPtr)*(*nPtr);}}
Invochiamo la funzione cubeByReference
6200
Si esegue l’istruzione*nPtr=(*nPtr)*(*nPtr)*(*nPtr);*nPtr=(*nPtr)*(*nPtr)*(*nPtr);
*nPtr è il valore contenutonella locazione di memoria puntata da nPtr 5
L’istruzione quindi dice dielevare al cubo 5 e di memorizzareil valore risultante nella locazione dimemoria puntata da nPtr
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Cosa succede in memoria…Cosa succede in memoria…int number=5;cubeByReference(&number);cubeByReference(&number);
5number 6200
void cubeByReference(int *nPtr)void cubeByReference(int *nPtr){{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);*nPtr=(*nPtr)*(*nPtr)*(*nPtr);}}
Invochiamo la funzione cubeByReference
6200
L’istruzione quindi dice dielevare al cubo 5 e di memorizzareil valore risultante nella locazione dimemoria puntata da nPtr
Il cubo di 5 è 125125
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Cosa succede in memoria…Cosa succede in memoria…int number=5;cubeByReference(&number);cubeByReference(&number);printf(“il nuovo valore del numero è: printf(“il nuovo valore del numero è: %d\n”,number);%d\n”,number);return 0;return 0;
5number 6200
void cubeByReference(int *nPtr)void cubeByReference(int *nPtr){{
*nPtr=(*nPtr)*(*nPtr)*(*nPtr);*nPtr=(*nPtr)*(*nPtr)*(*nPtr);}}
Si ritorna il controllo al main che esegue la prossima istruzione
6200
Si stampa il valore di number 125
La memoria allocata per nPtr viene rilasciata
125
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Cosa succede in memoria…Cosa succede in memoria…
Passaggio per valore evita di compromettere i valori delle variabilicon cui sono invocate le funzioni (spesso non si vogliono modificaretali valori)Passaggio parametri per riferimento evita di dover allocare, ad ogni invocazionedi funzione, memoria per copiare quantità di dati di input grandi che possono dover essere passati alla funzioneesempio: se la funzione ha come input un vettore abbiamo bisognosolo di un parametro di tipo puntatore in cui copiare la locazione dimemoria associata al primo elemento del vettore
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Qualificatore constQualificatore const
Consente di specificare che il valore di una Consente di specificare che il valore di una particolare variabile NON dovrà essere particolare variabile NON dovrà essere modificatomodificatoIl compilatore intercetterà qualsiasi tentativo di Il compilatore intercetterà qualsiasi tentativo di modificare una variabile che sia stata dichiarata modificare una variabile che sia stata dichiarata const e, nel caso in cui tale variabile sia const e, nel caso in cui tale variabile sia modificata, darà un errore o un warning.modificata, darà un errore o un warning. serve a proteggere da errori serve a proteggere da errori nell’implementazione del codicenell’implementazione del codice rendere più rendere più facile il debuggingfacile il debugging
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Modi di passare un puntatore a una Modi di passare un puntatore a una funzionefunzione
‘‘Puntatore variabile a dati variabili’Puntatore variabile a dati variabili’– i dati possono essere modificati attraverso il i dati possono essere modificati attraverso il
puntatorepuntatore– Il valore della variabile puntatore potrà essere Il valore della variabile puntatore potrà essere
modificato in modo che il puntatore possa fare modificato in modo che il puntatore possa fare riferimento ad altri datiriferimento ad altri dati
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
EsempioEsempio#include <stdio.h>#include <stdio.h>void convertToUppercase (char *);void convertToUppercase (char *);main()main(){{
char string[ ]=“caratteri”;char string[ ]=“caratteri”;printf(“la stringa prima della conversione è %s\n”,string);printf(“la stringa prima della conversione è %s\n”,string);convertToUppercase(string); /*converte le lettere minuscole della stringa in convertToUppercase(string); /*converte le lettere minuscole della stringa in maiuscole*/maiuscole*/printf(“dopo la conversione la stringa è %s\n”,string);printf(“dopo la conversione la stringa è %s\n”,string);return 0;return 0;
}}void convertToUppercase(char *s)void convertToUppercase(char *s){{
while (*s != ‘\0’)while (*s != ‘\0’){{
if (*s >= ‘a’ && *s<= ‘z’)if (*s >= ‘a’ && *s<= ‘z’)*s-=32;*s-=32;
++s;++s;}}
}}La stringa prima della conversione è:pippo
Dopo la conversione la stringa è PIPPO
Vengono modificati i caratteri dellaStringa. s punta a caratteri diversi della stringadurante l’esecuzione della funzione
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Altri casi…Altri casi…Puntatore variabile a dati costanti (i dati non possono essere Puntatore variabile a dati costanti (i dati non possono essere modificati)modificati)
#include <stdio.h>#include <stdio.h>void printCharacters (void printCharacters (const char *);const char *);main()main(){{
char string [ ]=“stampa i caratteri”;char string [ ]=“stampa i caratteri”;printf (“la stringa è:\n”);printf (“la stringa è:\n”);printCharacters (string);printCharacters (string);putchar(‘\n’);putchar(‘\n’);return 0;return 0;
}}void printCharacters(const char *s)void printCharacters(const char *s){{
for (;*s!=‘\0’;s++)for (;*s!=‘\0’;s++)putchar(*s);putchar(*s);
}}la stringa è:
stampa i caratteri
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Altri casi…Altri casi…
Puntatore costante a dati variabiliPuntatore costante a dati variabili– il puntatore fa sempre riferimento alla stessa il puntatore fa sempre riferimento alla stessa
locazione di memorialocazione di memoria– Tramite il puntatore si può cambiare il valore della Tramite il puntatore si può cambiare il valore della
locazione di memorialocazione di memoria
int *const ptr;int *const ptr;Puntatore costante a dati costantiPuntatore costante a dati costanti– il puntatore fa sempre riferimento alla stessa il puntatore fa sempre riferimento alla stessa
locazione di memorialocazione di memoria– Il valore della locazione di memoria non può essere Il valore della locazione di memoria non può essere
modificatomodificato
const int *const ptr;const int *const ptr;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
EsempioEsempio
#include <stdio.h>#include <stdio.h>main ()main (){{
int x=5,y;int x=5,y;const int *const ptr=&x;const int *const ptr=&x;*ptr=7;*ptr=7; ptr=&y;ptr=&y; return 0;return 0;
}}
Cannot modify a const object
Cannot modify a const object
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Bubblesort (versione 2)Bubblesort (versione 2)#include <stdio.h>#include <stdio.h>#define SIZE 10#define SIZE 10void bubbleSort(int *,const int);void bubbleSort(int *,const int);void swap (int *,int*);void swap (int *,int*);main()main(){{
int i,a[SIZE]={2,6,4,8,10,12,89,68,45,37};int i,a[SIZE]={2,6,4,8,10,12,89,68,45,37};printf(“ordine originale \n”);printf(“ordine originale \n”);for (i=0;i<=SIZE-1;i++)for (i=0;i<=SIZE-1;i++)
printf(“%d”,a[i]);printf(“%d”,a[i]);bubbleSort (a,SIZE);bubbleSort (a,SIZE);printf(“dati in ordine crescente \n”);printf(“dati in ordine crescente \n”);for (i=0;i<=SIZE-1;i++)for (i=0;i<=SIZE-1;i++)
printf(“%d”,a[i]);printf(“%d”,a[i]);printf(“\n”);printf(“\n”);return 0;return 0;
}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
BubblesortBubblesortvoid bubbleSort(int *array, const int size)void bubbleSort(int *array, const int size)
{{
int pass,j;int pass,j;
for (pass=1;pass <=size-1;pass++)for (pass=1;pass <=size-1;pass++)
for (j=0;j<=size-2;j++)for (j=0;j<=size-2;j++)
if(array[j]>array[j+1])if(array[j]>array[j+1])
swap(&array[j],&array[j+1]);swap(&array[j],&array[j+1]);
} }
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
SwapSwap
void swap (int *element1Ptr, int void swap (int *element1Ptr, int *element2Ptr)*element2Ptr)
{{int temp;int temp;temp=*element1Ptr;temp=*element1Ptr;*element1Ptr=*element2Ptr;*element1Ptr=*element2Ptr;*element2Ptr=temp;*element2Ptr=temp;
}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Aritmetica dei puntatoriAritmetica dei puntatori
I puntatori sono degli operandi validi per le I puntatori sono degli operandi validi per le espressioni aritmetiche (insieme limitato di espressioni aritmetiche (insieme limitato di operatori aritmetici possono essere applicati a operatori aritmetici possono essere applicati a puntatori), le espressioni di assegnamento e le puntatori), le espressioni di assegnamento e le espressioni di confronto espressioni di confronto – un puntatore potrà essere incrementato e un puntatore potrà essere incrementato e
decrementato con gli operatori ++ o --, ad un decrementato con gli operatori ++ o --, ad un puntatore potrà essere sommato o sottratto un intero puntatore potrà essere sommato o sottratto un intero (operatori +, -,-=, +=). Infine ad un puntatore potrà (operatori +, -,-=, +=). Infine ad un puntatore potrà essere sottratto un secondo puntatore.essere sottratto un secondo puntatore.
Devono però essere puntatori allo stesso tipo di dato
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Aritmetica dei puntatori per operare Aritmetica dei puntatori per operare sui vettorisui vettori
int i;int i;
int v[100];int v[100];
int * vPtr;int * vPtr;
for (i=0; i<100;i++)for (i=0; i<100;i++)
v[i]=i;v[i]=i;
vPtr=&v[0];vPtr=&v[0];
00 11 22 …… 9898 9999 v
3000
3000 vPtr
vPtr poteva anche essere inizializzatoScrivendo vPtr=v;
In quale locazione di memoria si trova v[1]? Ed il generico elemento v[i]?
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Operatore sizeofOperatore sizeofsizeof(nome_di variabile o sizeof(nome_di variabile o tipo di datotipo di dato o costante) o costante)È l’operatore che consente di determinare quante celle di È l’operatore che consente di determinare quante celle di
memoria sono associate ad un certo tipo di dato memoria sono associate ad un certo tipo di dato printf(“sizeof(char)=%d\n”printf(“sizeof(char)=%d\n”
“ “sizeof(short)=%d\n”sizeof(short)=%d\n” “ “sizeof(int)=%d\n”sizeof(int)=%d\n” “ “sizeof(long)=%d\n”sizeof(long)=%d\n” “ “sizeof(float)=%d\n”sizeof(float)=%d\n” “ “sizeof(double)=%d\n”sizeof(double)=%d\n” “ “sizeof(long double)=%d\n”,sizeof(long double)=%d\n”, sizeof(char),sizeof(short),sizeof(int),sizeof(long),sizeof(char),sizeof(short),sizeof(int),sizeof(long), sizeof(long),sizeof(float),sizeof(double),sizeof(long),sizeof(float),sizeof(double), sizeof(long double));sizeof(long double)); sizeof(char)=1
sizeof(short)=2sizeof(int)=2sizeof(long)=4sizeof(float)=4sizeof(double)=8sizeof(long double)=10
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Aritmetica dei puntatori per operare Aritmetica dei puntatori per operare sui vettorisui vettori
int i;int i;
int v[100];int v[100];
for (i=0; i<100;i++)for (i=0; i<100;i++)
v[i]=i;v[i]=i;
vPtr=&v[0];vPtr=&v[0];
00 11 22 …… 9898 9999 v
3000
3000 vPtr
Supponendo che il numero di celle associate ad unIntero sia 2…
vPtr+=2 fa puntare vPtr a v[2]
3004
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Aritmetica dei puntatori per operare Aritmetica dei puntatori per operare sui vettorisui vettori
int i;int i;
int v[100];int v[100];
for (i=0; i<100;i++)for (i=0; i<100;i++)
v[i]=i;v[i]=i;
vPtr=&v[0];vPtr=&v[0];
00 11 22 …… 9898 9999 v
3000
3004 vPtr
Supponendo che il numero di celle associate ad unIntero 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 decrementatadi una quantità di celle pari a quelle che servono per memorizzareil tipo di dato in modo da far puntare all’elemento precedentedel vettore
3002
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Aritmetica dei puntatori per operare Aritmetica dei puntatori per operare sui vettorisui vettoriint i;int i;
int v[100];int v[100];
int *vPtr;int *vPtr;
int *vPtr2;int *vPtr2;
for (i=0; i<100;i++)for (i=0; i<100;i++)
v[i]=i;v[i]=i;
vPtr=&v[0];vPtr=&v[0];
vPtr2=&v[99];vPtr2=&v[99];
00 11 22 …… 9898 9999 v
3000
3000 vPtr
Supponendo che il numero di celle associate ad unIntero sia 2…
x=vPtr2-vPtr;Assegna ad x il numero di elementi del vettore compresitra l’elemento puntato da vPtr2 e vPtr (infatti il valore delle differenza viene normalizzato al numero di celle necessarieper contenere un intero)in questo caso 99
3198 vPtr2
L’aritmetica dei puntatori ha senso con gli elementi di un vettore altrimentiNon si può assumere che variabili dello stesso tipo siano immagazzinate incelle consecutive di memoria
Un confronto tra puntatoriha senso solo per puntatoriche puntano ad elementidiversi dello stesso vettoree può ad esempio essereusato per controllare qualedei due elementi puntati haIndice maggiore
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Puntatori e vettoriPuntatori e vettori
00 11 22 …… 9898 9999 v
3000
3000 vPtr
v==&v[0]Se vPtr==vv[4] e *(vPtr+4) sono due notazioni equivalenti per far riferimento al valore del quinto elemento del vettore
notazione conpuntatore e offset
Attenzione: il nome del vettore è un puntatore costante punterà sempre allaPrima posizione del vettore, non può essere modificato
vPtr[4] e *(vPtr+4)sono anche notazioniequivalenti
notazione con puntatore e indice
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio#include <stdio.h>#include <stdio.h>main()main(){{
int i, offset, b[ ]={10,20,30,40};int i, offset, b[ ]={10,20,30,40};int *bPtr=b;int *bPtr=b;printf(“stampa del vettore con notazione con indici”);printf(“stampa del vettore con notazione con indici”);for (i=0;i<=3;i++)for (i=0;i<=3;i++)
printf(“b[%d]=%d\n”,i,b[i]);printf(“b[%d]=%d\n”,i,b[i]);printf(“stampa del vettore con notazione con puntatore e printf(“stampa del vettore con notazione con puntatore e offset”);offset”);for (offset=0;offset<=3;offset++)for (offset=0;offset<=3;offset++)
printf(“*(bPtr+%d)=%d\n”,offset,*(bPtr+offset));printf(“*(bPtr+%d)=%d\n”,offset,*(bPtr+offset));printf(“stampa del vettore con notazione con puntatore e printf(“stampa del vettore con notazione con puntatore e indice”);indice”);for (i=0;i<=3;i++)for (i=0;i<=3;i++)
printf(“bPtr[%d]=%d\n”,i,bPtr[i]);printf(“bPtr[%d]=%d\n”,i,bPtr[i]);return 0;return 0;
}}
b[0]=10b[1]=20b[2]=30b[3]=40
*(bPtr+0)=10*(bPtr+1)= 20*(bPtr+2)= 30*(bPtr+3)= 40
bPtr[0]=10bPtr[1]=20bPtr[2]=30bPtr[3]=40
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Alcuni esercizi sulle stringhe…Alcuni esercizi sulle stringhe…
Si scriva una funzione che copia la stringa s2 nel vettore Si scriva una funzione che copia la stringa s2 nel vettore s1. s1.
/*Pre: dim del vettore s1 sufficienti per contenere s2*//*Pre: dim del vettore s1 sufficienti per contenere s2*//*Post: s1 contiene la stringa s2*//*Post: s1 contiene la stringa s2*/void stringcopy(char *s1, char *s2)void stringcopy(char *s1, char *s2){{
for (;*s2 !='\0';s1++,s2++)for (;*s2 !='\0';s1++,s2++)*s1=*s2;*s1=*s2;
*s1='\0';*s1='\0';}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Alcuni esercizi sulle stringhe…Alcuni esercizi sulle stringhe…/*Post: confronta s1 e s2. Restituisce -1 se s1 e' minore in ordine /*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 lessicografico di s2, 0 se sono uguali ,1 se s1 e' maggiore in ordine lessicografico di s2 */ordine lessicografico di s2 */
int stringcmp(char *s1, char *s2)int stringcmp(char *s1, char *s2){{
while (*s1==*s2)while (*s1==*s2){{
if (*s1=='\0')if (*s1=='\0')return 0;return 0;
s1++;s1++;s2++;s2++;
}}if (*s1 == '\0')if (*s1 == '\0')
return -1;return -1;else if (*s2 == '\0')else if (*s2 == '\0')
return 1;return 1;elseelse
return (((*s1 - *s2)>0)?1:-1);return (((*s1 - *s2)>0)?1:-1);}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Alcuni esercizi sulle stringheAlcuni esercizi sulle stringhesi scriva una funzione che, date due stringhe, si scriva una funzione che, date due stringhe,
restituisce 1 se la prima stringa compare restituisce 1 se la prima stringa compare come sottostringa della seconda, 0 altrimenti. come sottostringa della seconda, 0 altrimenti. Se la prima stringa e' vuota restituisce 1 (una Se la prima stringa e' vuota restituisce 1 (una stringa vuota e' sottostringa di q.siasi stringa. stringa vuota e' sottostringa di q.siasi stringa. Se la seconda stringa e' vuota e la prima no Se la seconda stringa e' vuota e la prima no allora restituisce 0.allora restituisce 0.
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Alcuni esercizi sulle stringheAlcuni esercizi sulle stringheint findstr (char *s1, char *s2)int findstr (char *s1, char *s2){{
char *temp_s1;char *temp_s1;char *temp_s2;char *temp_s2;while (*s2!='\0')while (*s2!='\0') {{
temp_s2=s2;temp_s2=s2;temp_s1=s1;temp_s1=s1;while ((*s1 == *s2)&&(*s1!='\0')&&(*s2!='\0'))while ((*s1 == *s2)&&(*s1!='\0')&&(*s2!='\0')){{
s1++;s1++;s2++;s2++;
}}if (*s1=='\0')if (*s1=='\0')
return 1;return 1;else if (*s2=='\0')else if (*s2=='\0')
return 0;return 0;else else {{
s2=temp_s2+1;s2=temp_s2+1;s1=temp_s1;s1=temp_s1;
}}}}
return ((s1=='\0')?1:0);return ((s1=='\0')?1:0);}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Vettori di puntatoriVettori di puntatoriI vettori possono contenere elementi di tipo puntatoreI vettori possono contenere elementi di tipo puntatore
Esempio: array di stringheEsempio: array di stringhe
const char *suit[4]={“Cuori”,”Quadri”,”Picche”,”Fiori”};const char *suit[4]={“Cuori”,”Quadri”,”Picche”,”Fiori”};
CC uu oo rr ii \0\0
suit
FF ii oo rr ii \0\0
QQ uu aa dd rr ii \0\0
PP ii cc cc hh ee \0\0
Gli elementi di suit sonopuntatori allaposizione dove è memorizzatoil primo carattere di ciascunastringaciascuno punta in manieraStabile ad una determinata stringa
La memoria allocata per suit è quella necessaria per contenere4 puntatoriCiascuna stringa ha poi allocata memoria separatamente perContenerne i caratteri incluso quello di fine stringa
6200
3100
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Vettori di puntatoriVettori di puntatoriI vettori possono contenere elementi di tipo puntatoreI vettori possono contenere elementi di tipo puntatore
Esempio: array di stringheEsempio: array di stringhe
const char *suit[4]={“Cuori”,”Quadri”,”Picche”,”Fiori”};const char *suit[4]={“Cuori”,”Quadri”,”Picche”,”Fiori”};
CC uu oo rr ii \0\0
suit
FF ii oo rr ii \0\0
QQ uu aa dd rr ii \0\0
PP ii cc cc hh ee \0\0
Non si poteva usare una matrice di caratteri?Si MA l’uso di vettori di puntatori a caratteri fa risparmiare memoriaPer ogni stringaSi alloca la memoria sufficiente a memorizzare la stringaNON la memoria necessaria a memorizzare la stringa più lunga
6200
3100
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
Si scriva un programma che mescoli un mazzo di Si scriva un programma che mescoli un mazzo di carte, stampando l’ordine delle carte ottenutocarte, stampando l’ordine delle carte ottenuto
Cuori
Quadri
Picche
Fiori
0
1
2
3
0 1 10 11 129
Ass
o
Du
e
Die
ci
Fan
te
Do
nn
a
Re
mazzo_carte
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
PseudocodicePseudocodiceInizializza la matrice mazzo_carte a 0Inizializza la matrice mazzo_carte a 0Inizializza una variabile contatore k a 1Inizializza una variabile contatore k a 1Fino a quando non è stato assegnato un Fino a quando non è stato assegnato un ordine a ciascuna carta (52 iterazioni)ordine a ciascuna carta (52 iterazioni)– Scegli la prossima cartaScegli la prossima carta
Scegli casualmente una riga iScegli casualmente una riga iScegli casualmente una colonna j Scegli casualmente una colonna j Se mazzo_carte[i][j] è diverso da zero scegli una Se mazzo_carte[i][j] è diverso da zero scegli una nuova riga e colonna, ALTRIMENTI mazzo_carte[i]nuova riga e colonna, ALTRIMENTI mazzo_carte[i][j]=k[j]=kincrementa kincrementa k
Stampa una a una le carte nell’ordine Stampa una a una le carte nell’ordine selezionatoselezionato
Critico …potrei avere lunghe attese(attesa ‘infinita’) prima di trovare una posizione libera. Come potrei risolvereil problema? Posso scegliere casualmentesolo tra le posizioni non ancora riempite per esercizio
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
CodiceCodice
#include<stdio.h>#include<stdio.h>
#include<stdlib.h>#include<stdlib.h>
#include<time.h>#include<time.h>
void shuffle(int wDeck[ ][13]);void shuffle(int wDeck[ ][13]);
void deal(const int wDeck[ ][13],void deal(const int wDeck[ ][13],
const char *wFace[ ], const char *wsuit[ ]);const char *wFace[ ], const char *wsuit[ ]);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
CodiceCodice
int main()int main(){{
const char *suit[4]={“Cuori”,”Quadri”,”Picche”,”Fiori”};const char *suit[4]={“Cuori”,”Quadri”,”Picche”,”Fiori”};const char *face[13]={“Uno”,”Due”,”Tre”,”Quattro”, const char *face[13]={“Uno”,”Due”,”Tre”,”Quattro”, “Cinque”,”Sei”,”Sette”,”Otto”,”Nove”,”Dieci”,”Fante”, “Donna”, “Cinque”,”Sei”,”Sette”,”Otto”,”Nove”,”Dieci”,”Fante”, “Donna”, “Re”};“Re”};int deck[4][13]={0}; int deck[4][13]={0}; srand(time(0));srand(time(0));shuffle(deck);shuffle(deck);deal(deck,face,suit);deal(deck,face,suit);
}}
Alloco memoria peruna matrice di 52 interi. Inizializzo lamatrice a 0
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
ShuffleShuffle
void shuffle(int wDeck[ ][13])void shuffle(int wDeck[ ][13]){{
int i,j,k;int i,j,k;for (k=1; k<=52; k++) {for (k=1; k<=52; k++) {
do{do{i=rand()%4;i=rand()%4;j=rand()%13;j=rand()%13;
} while (wDeck[i][j] !=0);} while (wDeck[i][j] !=0);wDeck[i][j]=k;wDeck[i][j]=k;
}}}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
ShuffleShuffle
Cuori
Quadri
Picche
Fiori
0
1
2
3
0 1 10 11 129
Ass
o
Du
e
Die
ci
Fan
te
Do
nn
a
Re
k=1
i1j3
1
k=2 i3j10
2
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
ShuffleShuffle
Cuori
Quadri
Picche
Fiori
0
1
2
3
0 1 10 11 129
Ass
o
Du
e
Die
ci
Fan
te
Do
nn
a
Re
SCEGLIAMOUN ALTRO i ej, LA POSIZIONEÈ GIA’ OCCUPATA
i1j3
1
k=3i2j12
2
3
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Stampa delle carte nell’ordine Stampa delle carte nell’ordine selezionatoselezionato
void deal(const int wDeck[][13],const char *wFace[ ], const void deal(const int wDeck[][13],const char *wFace[ ], const char *wSuit[ ])char *wSuit[ ])
{{int i,j,k;int i,j,k;for (k=1;k<=52;k++){for (k=1;k<=52;k++){
for (i=0;i<=3;i++){for (i=0;i<=3;i++){for (j=0;j<=12;j++){for (j=0;j<=12;j++){
if (wDeck[i][j]==k){if (wDeck[i][j]==k){printf(“%s di %s\n”,wFace[j],wSuit[i]);printf(“%s di %s\n”,wFace[j],wSuit[i]);}}
}}}}
}}
} }
Quattro di QuadriFante di FioriRe di Picche---
Scandiamo sempre tutta la matriceanche quando abbiamo trovato l’elemento che corrisponde allak-esima cartainefficiente. Qualche idea su comeevitare questo problema?
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Puntatori a funzioniPuntatori a funzioni
Un nome di funzione indica l’indirizzo di Un nome di funzione indica l’indirizzo di memoria in cui è memorizzata la prima memoria in cui è memorizzata la prima istruzione della funzioneistruzione della funzione
Esempio di uso:Esempio di uso:
una versione del bubblesort che consenta una versione del bubblesort che consenta di inserire da input se il vettore deve di inserire da input se il vettore deve essere ordinato in ordine crescente o essere ordinato in ordine crescente o decrescentedecrescente
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
BubblesortBubblesort
#include<stdio.h>#include<stdio.h>
#define SIZE 10#define SIZE 10
void bubble(int work[ ], const int size, void bubble(int work[ ], const int size,
int (*compare)(int a,int b));int (*compare)(int a,int b));
int ascending(int a, int b);int ascending(int a, int b);
int descending(int a,int b);int descending(int a,int b);
Puntatore ad una funzioneche prende come parametridue interi e restituisce uninteroCompare è un puntatore a funzione
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
BubblesortBubblesortint main()int main(){{
int order; /* 1 per ordine crescente, 2 per decrescente*/int order; /* 1 per ordine crescente, 2 per decrescente*/int counter;int counter;int a[SIZE]={2,6,4,8,10,12,89,68,45,37};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 printf(“si inserisca 1 per ordinare in ordine crescente, 2 per un ordinamento decrescente del vettore \n”);decrescente del vettore \n”);scanf(“%d”, &order);scanf(“%d”, &order);printf(“dati nell’ordine originale \n”);printf(“dati nell’ordine originale \n”);for (counter=0;counter<SIZE;counter++){for (counter=0;counter<SIZE;counter++){
printf(“%d”,a[counter]);printf(“%d”,a[counter]);}}if(order==1){if(order==1){
bubble(a,SIZE,ascending);bubble(a,SIZE,ascending);}}else{else{
bubble(a,SIZE,descending);bubble(a,SIZE,descending);}}for (counter=0,counter<SIZE; counter++){for (counter=0,counter<SIZE; counter++){
printf(“%d”,a[counter]);printf(“%d”,a[counter]);}}return 0;return 0;
}}
puntatore a funzione
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
BubbleBubblevoid bubble(int work[ ],const int size, void bubble(int work[ ],const int size,
int (*compare)(int a, int b))int (*compare)(int a, int b)){{
int pass;int pass;int count;int count;void swap(int *element1Ptr,int *element2ptr);void swap(int *element1Ptr,int *element2ptr);for (pass=1;pass<size;pass++){for (pass=1;pass<size;pass++){
for (count=0;count<size-1;count++){for (count=0;count<size-1;count++){if ((*compare)(work[count],work[count+1])){if ((*compare)(work[count],work[count+1])){
swap(&work[count],&work[count+1]);swap(&work[count],&work[count+1]);}}
}}}}
}}
compare è unpuntatore ad unafunzione che prendedue parametri interi e restituisce un intero
int (*) (int,int);
un puntatore a funzione è dereferenziato perusare la funzioneInvoca la funzione puntata da compare conparametri work[count] e work[count+1]
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Swap, ascending, descendingSwap, ascending, descendingvoid swap(int *element1Ptr, int *element2Ptr)void swap(int *element1Ptr, int *element2Ptr){{
int hold;int hold;hold=*element1Ptr;hold=*element1Ptr;*element1Ptr=*element2Ptr;*element1Ptr=*element2Ptr;*element2Ptr=hold;*element2Ptr=hold;
}}/*ritorna 1 se non si segue l’ordinamento crescente*/ /*ritorna 1 se non si segue l’ordinamento crescente*/ int ascending(int a,int b)int ascending(int a,int b){{
return b<a;return b<a;}}int descending(int a,int b)int descending(int a,int b){{
return b>a;return b>a;}}
A seconda che si voglia ordinarein ordine crescente o decrescenteoccorre testare due condizionidiverse per verificare se due elementiconsecutivi sono ordinati correttamenteo meno
printf(“si inserisca 1 per ordinare in ordine printf(“si inserisca 1 per ordinare in ordine crescente, 2 per un ordinamento decrescente crescente, 2 per un ordinamento decrescente del vettore \n”);del vettore \n”);scanf(“%d”, &order);scanf(“%d”, &order);printf(“dati nell’ordine originale \n”);printf(“dati nell’ordine originale \n”);for (counter=0;counter<SIZE;counter++){for (counter=0;counter<SIZE;counter++){
printf(“%d”,a[counter]);printf(“%d”,a[counter]);}}if(order==1){if(order==1){
bubble(a,SIZE,ascending);bubble(a,SIZE,ascending);}}else{else{
bubble(a,SIZE,descending);bubble(a,SIZE,descending);}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Puntatori a funzione Puntatori a funzione (secondo esempio)(secondo esempio)
Un utente seleziona un’opzione da un menu. Un utente seleziona un’opzione da un menu. Ciascuna opzione è servita da una Ciascuna opzione è servita da una funzione differente.funzione differente.
I diversi puntatori a funzione sono I diversi puntatori a funzione sono memorizzati in un array di puntatori a memorizzati in un array di puntatori a funzione. La scelta dell’utente fornisce funzione. La scelta dell’utente fornisce l’indice del vettore. Il puntatore a funzione l’indice del vettore. Il puntatore a funzione è usato per invocare la funzione opportuna è usato per invocare la funzione opportuna in base alla scelta dell’utente.in base alla scelta dell’utente.
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
CodiceCodice#include<stdio.h>#include<stdio.h>void function1(int a);void function1(int a);void function2 (int b);void function2 (int b);void function3 (int c);void function3 (int c);int main()int main(){{
void (*f[3])(int)={function1,function2,function3};void (*f[3])(int)={function1,function2,function3};int choice,i;int choice,i;printf(“inserisci la scelta della funzione da invocare: 0, 1, 2 a seconda che 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 vogliate moltiplicare per uno, due o tre il valore inserito. Inserire il valore 3 per terminare l’esecuzione”);terminare l’esecuzione”);scanf(“%d”,&choice);scanf(“%d”,&choice);printf(“inserisci intero \n”);printf(“inserisci intero \n”);scanf(“%d”,&i);scanf(“%d”,&i);while(choice>=0 && choice <3){while(choice>=0 && choice <3){
(*f[choice])(i);(*f[choice])(i);printf(“inserisci la scelta della funzione da invocare: 0, 1, 2 a seconda che 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 vogliate moltiplicare per uno, due o tre il valore inserito. Inserire il valore 3 per terminare l’esecuzione”);terminare l’esecuzione”);scanf(“%d”, &choice);scanf(“%d”, &choice);printf(“inserisci intero \n”);printf(“inserisci intero \n”);scanf(“%d”,&i);scanf(“%d”,&i);}}return 0;return 0;
}}
inizializza un arraydi tre puntatori a funzioneQueste funzioni prendonoin input un intero e nonrestituiscono valori
invoca la funzione puntatada f[choice] sul valore interoinserito da input i
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Codice delle tre funzioni…Codice delle tre funzioni…
void function1(int a)void function1(int a){{
printf(“il valore di a moltiplicato per uno è %d\n”,a*1);printf(“il valore di a moltiplicato per uno è %d\n”,a*1);}}void function2(int a)void function2(int a){{
printf(“il valore di a moltiplicato per due è %d\n”,a*2);printf(“il valore di a moltiplicato per due è %d\n”,a*2);}}void function3(int a)void function3(int a){{
printf(“il valore di a moltiplicato per tre è %d\n”,a*3);printf(“il valore di a moltiplicato per tre è %d\n”,a*3);}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Argomenti avanzati sulle funzioni…Argomenti avanzati sulle funzioni…
Classi di memoriaClassi di memoria
Regole di scopeRegole di scope
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Classi di memoriaClassi di memoriaUna variabile ha associato un tipo, un nome, una Una variabile ha associato un tipo, un nome, una dimensione ed un valoredimensione ed un valoreAltri attributi di una variabile sono Altri attributi di una variabile sono
la sua classe di memoriala sua classe di memoria– autoauto– registerregister– externextern– staticstatic
il periodo durante il quale l’identificatore ha associata memoria il periodo durante il quale l’identificatore ha associata memoria (storage duration)(storage duration)lo scope (in quali parti del programma si può far riferimento alla lo scope (in quali parti del programma si può far riferimento alla variabile)variabile)linkage (se il programma è suddiviso in più file se l’identificatore linkage (se il programma è suddiviso in più file se l’identificatore può essere usato solo in questo file oppure in altri file previa può essere usato solo in questo file oppure in altri file previa opportune dichiarazioni)opportune dichiarazioni)
ARGOMENTO CHE TRATTERETE AD ESERCITAZIONE/PROG2ARGOMENTO CHE TRATTERETE AD ESERCITAZIONE/PROG2
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Automatic storage durationAutomatic storage duration
Classi di memoriaClassi di memoria autoauto
registerregister
Le variabili di tipo auto o register permangono in memoria Le variabili di tipo auto o register permangono in memoria fino a quando è attivo il blocco di istruzioni all’interno fino a quando è attivo il blocco di istruzioni all’interno del quale la variabile è definitadel quale la variabile è definita
Le variabili locali alle funzioni sono tipicamente di tipo Le variabili locali alle funzioni sono tipicamente di tipo auto (è la loro classe di memoria di default)auto (è la loro classe di memoria di default)
Se una variabile è di tipo register di suggerisce che venga Se una variabile è di tipo register di suggerisce che venga memorizzata in un registromemorizzata in un registro
I compilatori sanno ottimizzare l’uso dei registri meglio I compilatori sanno ottimizzare l’uso dei registri meglio di un programmatoredi un programmatore
possono decidere di ignorare la richiesta di mettere in possono decidere di ignorare la richiesta di mettere in un registro una variabileun registro una variabile
Le variabili visteFinora erano implicitamente dichiaratecome autoSe dichiarateall’inizio del mainè loro allocatamemoria fino all’uscita dalprogrammase dichiarateall’inizio di unafunzione la variabileha allocata memoriafino a quando non si esce dallafunzione
register int counter=1;dice che la variabileintera counter dovrebbeessere memorizzata in unregistro e inizializzata a 1
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Static storage durationStatic storage durationLe parole chiaveLe parole chiave
externextern staticstatic
sono usate per identificare variabili e funzioni di tipo static storagesono usate per identificare variabili e funzioni di tipo static storageMemoria è allocata una volta per tutte e le variabili sono Memoria è allocata una volta per tutte e le variabili sono
inizializzate all’inizio del programma. Tale memoria è inizializzate all’inizio del programma. Tale memoria è disponibile per l’intera durata del programmadisponibile per l’intera durata del programma
Le variabili globali sono di tipo extern per default. Sono dichiarate Le variabili globali sono di tipo extern per default. Sono dichiarate fuori da ogni funzione e mantengono memoria a loro allocata fuori da ogni funzione e mantengono memoria a loro allocata durante l’intera durata del programma. Possono essere riferite durante l’intera durata del programma. Possono essere riferite da una qualsiasi funzione che segue la loro dichiarazione.da una qualsiasi funzione che segue la loro dichiarazione.
Le variabili di tipo static invece sono note solo all’interno della Le variabili di tipo static invece sono note solo all’interno della funzione dove sono definite. Tuttavia quando si esce dalla funzione dove sono definite. Tuttavia quando si esce dalla funzione si continua a memorizzare il loro valore. La prossima funzione si continua a memorizzare il loro valore. La prossima volta che si invoca la funzione la variabile locale static avrà volta che si invoca la funzione la variabile locale static avrà come valore quello che aveva alla fine della precedente come valore quello che aveva alla fine della precedente invocazione.invocazione.
static int count=1;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Regole di scopeRegole di scope
Lo scope di un identificatore è la porzione Lo scope di un identificatore è la porzione del programma all’interno della quale si del programma all’interno della quale si può fare riferimento all’identificatorepuò fare riferimento all’identificatore– function scopefunction scope– file scopefile scope– block scopeblock scope– function-prototype scopefunction-prototype scope
etichetteusate nel costruttoswitchpossono essereusate solo all’internodella funzione nellaquale compaiono(e possono essereriferite in qualsiasipunto della funzione)
Un identificatore dichiarato all’esterno di ognifunzione ha uno scope di tipo file scopePossono essere riferite in qualsiasi puntoall’interno del file a partire dal punto in cuil’identificatore è dichiaratoEsempi: variabili globali, definizioni di funzioni,prototipi)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Regole di scopeRegole di scope
Lo scope di un identificatore è la porzione Lo scope di un identificatore è la porzione del programma all’interno della quale si del programma all’interno della quale si può fare riferimento all’identificatorepuò fare riferimento all’identificatore– function scopefunction scope– file scopefile scope– block scopeblock scope– function-prototype scopefunction-prototype scope
Identificatori block scope possono essereriferiti all’interno delBlocco in cui sono dichiarateIl blocco è delimitato da {}Variabili static hanno uno scopedi bloccoVariabili locali ad una funzionehanno scope di bloccoGli unici identificatori di tipo function prototype scope sono quelli
usati nella lista dei parametri di un prototipo di funzione. Dato chetali nomi, se usati, sono ignorati dal compilatore, hanno valoresolo all’interno del prototipo. Gli stessi identificatori possono essere riutilizzati in altre parti del programma senza problemi di ambiguità
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…#include <stdio.h>#include <stdio.h>
void useLocal (void);void useLocal (void);void useStaticLocal (void);void useStaticLocal (void);void useGlobal (void);void useGlobal (void);int x=1; /*variabile globale*/int x=1; /*variabile globale*/
int main()int main(){{
int x=5;int x=5; /*variabile locale al main*//*variabile locale al main*/printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);{/*comincia un nuovo scope*/{/*comincia un nuovo scope*/int x=7; /*variabile locale al blocco*/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 all’interno dello scope più interno del main è: %d”,x);}}printf(“il valore di x nello scope più esterno del main è: %d”, x);printf(“il valore di x nello scope più esterno del main è: %d”, x);useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();return 0;return 0;
}}
Se lo stesso identificatoreè usato in un blocco più internoall’interno del blocco internovale la definizione e inizializzazionedel blocco interno.
Il valore di x all’interno dello scope più esterno del main è: 5
Il valore di x all’interno dello scope più interno del main è: 7
Il valore di x all’interno dello scope più esterno del main è: 5
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…
void useLocal (void)void useLocal (void){{
int x=25; /*è di classe di memoria auto*/int x=25; /*è di classe di memoria auto*/printf(“”)printf(“”)printf(“valore di x entrati in useLocal, all’inizio printf(“valore di x entrati in useLocal, all’inizio della funzione: %d\n”,x);della funzione: %d\n”,x);x++;x++;printf(“valore di x entrati in useLocal, alla fine printf(“valore di x entrati in useLocal, alla fine della funzione: %d\n”,x);della funzione: %d\n”,x);
}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…#include <stdio.h>#include <stdio.h>
void useLocal (void);void useLocal (void);void useStaticLocal (void);void useStaticLocal (void);void useGlobal (void);void useGlobal (void);int x=1; /*variabile globale*/int x=1; /*variabile globale*/
int main()int main(){{
int x=5;int x=5; /*variabile locale al main*//*variabile locale al main*/printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);{/*comincia un nuovo scope*/{/*comincia un nuovo scope*/int x=7; /*variabile locale al blocco*/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 all’interno dello scope più interno del main è: %d”,x);}}printf(“il valore di x nello scope più esterno del main è: %d”, x);printf(“il valore di x nello scope più esterno del main è: %d”, x);useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();return 0;return 0;
}}
Il valore di x entrati in UseLocal all’iniziodella funzione è: 25Il valore di x entrati in UseLocal alla finedella funzione è: 26
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…
void useStaticLocal()void useStaticLocal(){{
static int x=50; /*inizializzata solo la prima volta static int x=50; /*inizializzata solo la prima volta che si entra nella funzione*/che si entra nella funzione*/printf(“local static vale %d all’inizio della funzione printf(“local static vale %d all’inizio della funzione useStaticLocal”,x);useStaticLocal”,x);x++;x++;printf(“local static vale %d alla fine della funzione printf(“local static vale %d alla fine della funzione useStaticLocal”,x);useStaticLocal”,x);
}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…
void useGlobal()void useGlobal()
{{
printf(“global x vale %d all’entrata di printf(“global x vale %d all’entrata di useGlobal\n”,x);useGlobal\n”,x);
x*=10;x*=10;
printf(“global x vale %d alla fine di printf(“global x vale %d alla fine di useGlobal\n”,x);useGlobal\n”,x);
}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…#include <stdio.h>#include <stdio.h>
void useLocal (void);void useLocal (void);void useStaticLocal (void);void useStaticLocal (void);void useGlobal (void);void useGlobal (void);int x=1; /*variabile globale*/int x=1; /*variabile globale*/
int main()int main(){{
int x=5;int x=5; /*variabile locale al main*//*variabile locale al main*/printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);{/*comincia un nuovo scope*/{/*comincia un nuovo scope*/int x=7; /*variabile locale al blocco*/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 all’interno dello scope più interno del main è: %d”,x);}}printf(“il valore di x nello scope più esterno del main è: %d”, x);printf(“il valore di x nello scope più esterno del main è: %d”, x);useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();return 0;return 0;
}}
local static vale 50 all’inizio della funzione local static vale 50 all’inizio della funzione useStaticLocaluseStaticLocallocal static vale 51 alla fine della funzione local static vale 51 alla fine della funzione useStaticLocaluseStaticLocal
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…#include <stdio.h>#include <stdio.h>
void useLocal (void);void useLocal (void);void useStaticLocal (void);void useStaticLocal (void);void useGlobal (void);void useGlobal (void);int x=1; /*variabile globale*/int x=1; /*variabile globale*/
int main()int main(){{
int x=5;int x=5; /*variabile locale al main*//*variabile locale al main*/printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);{/*comincia un nuovo scope*/{/*comincia un nuovo scope*/int x=7; /*variabile locale al blocco*/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 all’interno dello scope più interno del main è: %d”,x);}}printf(“il valore di x nello scope più esterno del main è: %d”, x);printf(“il valore di x nello scope più esterno del main è: %d”, x);useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();return 0;return 0;
}}
Global x vale 1 all’entrata diuseGlobal Global x vale 10 alla fine diuseGlobal
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…#include <stdio.h>#include <stdio.h>
void useLocal (void);void useLocal (void);void useStaticLocal (void);void useStaticLocal (void);void useGlobal (void);void useGlobal (void);int x=1; /*variabile globale*/int x=1; /*variabile globale*/
int main()int main(){{
int x=5;int x=5; /*variabile locale al main*//*variabile locale al main*/printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);{/*comincia un nuovo scope*/{/*comincia un nuovo scope*/int x=7; /*variabile locale al blocco*/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 all’interno dello scope più interno del main è: %d”,x);}}printf(“il valore di x nello scope più esterno del main è: %d”, x);printf(“il valore di x nello scope più esterno del main è: %d”, x);useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();return 0;return 0;
}}
Il valore di x entrati in UseLocal all’iniziodella funzione è: 25Il valore di x entrati in UseLocal alla finedella funzione è: 26
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…#include <stdio.h>#include <stdio.h>
void useLocal (void);void useLocal (void);void useStaticLocal (void);void useStaticLocal (void);void useGlobal (void);void useGlobal (void);int x=1; /*variabile globale*/int x=1; /*variabile globale*/
int main()int main(){{
int x=5;int x=5; /*variabile locale al main*//*variabile locale al main*/printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);{/*comincia un nuovo scope*/{/*comincia un nuovo scope*/int x=7; /*variabile locale al blocco*/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 all’interno dello scope più interno del main è: %d”,x);}}printf(“il valore di x nello scope più esterno del main è: %d”, x);printf(“il valore di x nello scope più esterno del main è: %d”, x);useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();return 0;return 0;
}}
local static vale 51 all’inizio della funzione local static vale 51 all’inizio della funzione useStaticLocaluseStaticLocallocal static vale 52 alla fine della funzione local static vale 52 alla fine della funzione useStaticLocaluseStaticLocal
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…#include <stdio.h>#include <stdio.h>
void useLocal (void);void useLocal (void);void useStaticLocal (void);void useStaticLocal (void);void useGlobal (void);void useGlobal (void);int x=1; /*variabile globale*/int x=1; /*variabile globale*/
int main()int main(){{
int x=5;int x=5; /*variabile locale al main*//*variabile locale al main*/printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);printf(“il valore di x all’interno dello scope più esterno del main è: %d”,x);{/*comincia un nuovo scope*/{/*comincia un nuovo scope*/int x=7; /*variabile locale al blocco*/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 all’interno dello scope più interno del main è: %d”,x);}}printf(“il valore di x nello scope più esterno del main è: %d”, x);printf(“il valore di x nello scope più esterno del main è: %d”, x);useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();useLocal();useLocal();useStaticLocal();useStaticLocal();useGlobal();useGlobal();return 0;return 0;
}}
Global x vale 10 all’entrata diuseGlobal Global x vale 100 alla fine diuseGlobal
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
RicorsioneRicorsione
Abbiamo visto come un problema complesso Abbiamo visto come un problema complesso possa essere scomposto in task, ciascuno possa essere scomposto in task, ciascuno realizzato tramite una funzionerealizzato tramite una funzioneUna funzione può invocare altre funzioniUna funzione può invocare altre funzioniE’ possibile anche invocare la STESSA E’ possibile anche invocare la STESSA funzione, su un input diversofunzione, su un input diverso– Un task complesso può essere risolto invocando la Un task complesso può essere risolto invocando la
funzione che realizza il task su dei sottoproblemi, funzione che realizza il task su dei sottoproblemi, usando la capacità di svolgere il task su sottoproblemi usando la capacità di svolgere il task su sottoproblemi per riuscire a svolgere il task sull’intero problema per riuscire a svolgere il task sull’intero problema
ricorsionericorsione
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Ricorsione…un esempioRicorsione…un esempioVogliamo scrivere una funzione che consenta di Vogliamo scrivere una funzione che consenta di calcolare il fattoriale n!calcolare il fattoriale n!n!= n*(n-1)*(n-2)*(n-3)*…*2*1Approccio 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 nAbbiamo 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 diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Fattoriale (versione ricorsiva)Fattoriale (versione ricorsiva)
int fatt (int n)int fatt (int n)
{{
if (n==1) if (n==1)
return 1;return 1;
elseelse
return (fatt(n-1)*n);return (fatt(n-1)*n);
}}
Caso base. Occorre saper risolvere direttamente i casi base.
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 5!Calcolo di 5!
Viene invocata Viene invocata
x=fatt(5);x=fatt(5);int fatt (int n)int fatt (int n){{
if (n==1) if (n==1) return 1;return 1;
elseelsereturn (fatt(n-1)*n);return (fatt(n-1)*n);
}}
PRIMA INVOCAZIONE DI FATTfatt(5)
All’entrata della funzionesi alloca memoria per la var.locale nSi copia in tale locazione ilvalore 5
n5 Si invoca fatt(4)
3200
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 5!Calcolo di 5!
Viene invocata Viene invocata
fatt(4);fatt(4);int fatt (int n)int fatt (int n){{
if (n==1) if (n==1) return 1;return 1;
elseelsereturn (fatt(n-1)*n);return (fatt(n-1)*n);
}}
SECONDA INVOCAZIONE DI FATTfatt(4)
All’entrata della funzionesi alloca memoria per la var.locale n, relativa A QUESTAINVOCAZIONE DI FUNZIONESi copia in tale locazione ilvalore 4
n4 Si invoca fatt(3)
5200
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 5!Calcolo di 5!
Viene invocata Viene invocata
fatt(3);fatt(3);int fatt (int n)int fatt (int n){{
if (n==1) if (n==1) return 1;return 1;
elseelsereturn (fatt(n-1)*n);return (fatt(n-1)*n);
}}
TERZA INVOCAZIONE DI FATTfatt(3)
All’entrata della funzionesi alloca memoria per la var.locale n, relativa A QUESTAINVOCAZIONE DI FUNZIONESi copia in tale locazione ilvalore 3
n3 Si invoca fatt(2)
7800
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 5!Calcolo di 5!
Viene invocata Viene invocata
fatt(2);fatt(2);int fatt (int n)int fatt (int n){{
if (n==1) if (n==1) return 1;return 1;
elseelsereturn (fatt(n-1)*n);return (fatt(n-1)*n);
}}
QUARTA INVOCAZIONE DI FATTfatt(2)
All’entrata della funzionesi alloca memoria per la var.locale n, relativa A QUESTAINVOCAZIONE DI FUNZIONESi copia in tale locazione ilvalore 2
n2 Si invoca fatt(1)
9800
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 5!Calcolo di 5!
Viene invocata Viene invocata
fatt(1);fatt(1);int fatt (int n)int fatt (int n){{
if (n==1) if (n==1) return 1;return 1;
elseelsereturn (fatt(n-1)*n);return (fatt(n-1)*n);
}}
QUINTA INVOCAZIONE DI FATTfatt(1)
All’entrata della funzionesi alloca memoria per la var.locale n, relativa A QUESTAINVOCAZIONE DI FUNZIONESi copia in tale locazione ilvalore 1
n 1Si restituisce il controlloalla funzione chiamantefatt(2), restituendo 1
3900
fatt(5)fatt(4)
fatt(2)fatt(3)
fatt(1)
Fondamentale cheLa sequenza di Invocazioni terminiSEMPRE con l’invocazionedella funzione su un casoche sappiamo risolveredirettamente (caso base)
La memoria allocata pern viene rilasciata
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 5!Calcolo di 5!
Viene invocata Viene invocata
fatt(2);fatt(2);int fatt (int n)int fatt (int n){{
if (n==1) if (n==1) return 1;return 1;
elseelsereturn (fatt(n-1)*n);return (fatt(n-1)*n);
}}
QUARTA INVOCAZIONE DI FATTfatt(2)
All’entrata della funzionesi alloca memoria per la var.locale n, relativa A QUESTAINVOCAZIONE DI FUNZIONESi copia in tale locazione ilvalore 2
n2
9800 restituisce 1
Viene calcolato fatt(2)2*1=2e viene restituito tale valorealla funzione chiamante fatt(3)
fatt(5)fatt(4)
fatt(2)fatt(3)
fatt(1)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 5!Calcolo di 5!
Viene invocata Viene invocata
fatt(3);fatt(3);int fatt (int n)int fatt (int n){{
if (n==1) if (n==1) return 1;return 1;
elseelsereturn (fatt(n-1)*n);return (fatt(n-1)*n);
}}
TERZA INVOCAZIONE DI FATTfatt(3)
n3
7800 restituisce 2
Viene calcolato fatt(3)3*2=6e viene restituito tale valorealla funzione chiamante fatt(4)
fatt(5)fatt(4)
fatt(2)fatt(3)
fatt(1)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 5!Calcolo di 5!
Viene invocata Viene invocata
fatt(4);fatt(4);int fatt (int n)int fatt (int n){{
if (n==1) if (n==1) return 1;return 1;
elseelsereturn (fatt(n-1)*n);return (fatt(n-1)*n);
}}
SECONDA INVOCAZIONE DI FATTfatt(4)
n4
5200 restituisce 6
Viene calcolato fatt(4)4*6=24e viene restituito tale valorealla funzione chiamante fatt(5)
fatt(5)fatt(4)
fatt(2)fatt(3)
fatt(1)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 5!Calcolo di 5!
Viene invocata Viene invocata
x=fatt(5);x=fatt(5);int fatt (int n)int fatt (int n){{
if (n==1) if (n==1) return 1;return 1;
elseelsereturn (fatt(n-1)*n);return (fatt(n-1)*n);
}}
PRIMA INVOCAZIONE DI FATTfatt(5)
n5
3200 restituisce 24
Viene calcolato fatt(5)5*24=120e viene restituito tale valorealla funzione chiamante main()
fatt(5)fatt(4)
fatt(2)fatt(3)
fatt(1)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Alcuni commenti…Alcuni commenti…Approccio ricorsivoApproccio ricorsivo– richiede l’invocazione di molte chiamate a funzione, di richiede l’invocazione di molte chiamate a funzione, di
allocare ogni volta memoria per i parametri e le variabili allocare ogni volta memoria per i parametri e le variabili localilocali
può essere inefficientepuò essere inefficienteTUTTAVIA ragionare in modo ricorsivo è molto utile e TUTTAVIA ragionare in modo ricorsivo è molto utile e
vedrete di qui a poco (PROG2) che esistono strutture vedrete di qui a poco (PROG2) che esistono strutture dati molto importanti quali gli alberi sui quali si riesce a dati molto importanti quali gli alberi sui quali si riesce a ragionare efficamente solo in modo ricorsivoragionare efficamente solo in modo ricorsivo
RAGIONARE IN MODO RICORSIVO E’ COMPLESSO MA RAGIONARE IN MODO RICORSIVO E’ COMPLESSO MA E’ Q.SA DI FONDAMENTALE PER UN INFORMATICO!!E’ Q.SA DI FONDAMENTALE PER UN INFORMATICO!!
Abbiamo visto cosa succede in memoria quando Abbiamo visto cosa succede in memoria quando invochiamo una sequenza di chiamate ricorsive…è invochiamo una sequenza di chiamate ricorsive…è importante capire come si ragiona ricorsivamenteimportante capire come si ragiona ricorsivamente
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Come si ragiona ricorsivamenteCome si ragiona ricorsivamente
INPUT OUTPUT
funzione
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 generaleSe gli output della invocazioni su casi più piccoli possono essere elaborati ed usati per trovare la soluzione al problema (OUTPUT) peril caso più grandeAVER DETERMINATO IL MODO DI FARE CIO’ CI DARA’ IL NOSTROCODICE RICORSIVO
output1
output2
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Come si ragiona ricorsivamenteCome si ragiona ricorsivamente
INPUT OUTPUT
funzione
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 generaleSe gli output della invocazioni su casi più piccoli possono essere elaborati ed usati per trovare la soluzione al problema (OUTPUT) peril caso più grandeAVER DETERMINATO IL MODO DI FARE CIO’ CI DARA’ IL NOSTROCODICE RICORSIVO
output1
output2
Sarà poi fondamentaleindividuare i casi basee assicurarci che tuttele sequenze di chiamatericorsive termininosempre con l’invocazionedi un caso base
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio…Un esempio…
SI scriva una funzione ricorsiva che dati due SI scriva una funzione ricorsiva che dati due numeri interi a e b calcoli a+bnumeri interi a e b calcoli a+b
Se so calcolare x+y, x<=a, y<b, come posso Se so calcolare x+y, x<=a, y<b, come posso usarlo per calcolare a+busarlo per calcolare a+b
a+b=(a+b-1)+1a+b=(a+b-1)+1
Calcolato dall’invocazione della funzione su a e b-1
Caso base: se b==0, a+b=a
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
SoluzioneSoluzione
int somma (int a, int b)int somma (int a, int b)
{{
if (b==0)if (b==0)
return a;return a;
elseelse
return (somma(a,b-1)+1);return (somma(a,b-1)+1);
}}Vediamo cosa succede invocando somma (3,2)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 3+2Calcolo di 3+2
Viene invocata Viene invocata
x=somma(3,2);x=somma(3,2);int somma (int a, int b)int somma (int a, int b){{
if (b==0)if (b==0)return a;return a;
elseelsereturn (somma(a,b-1)+1);return (somma(a,b-1)+1);
}}
PRIMA INVOCAZIONE DI SOMMA
All’entrata della funzionesi alloca memoria per le var.locale a e bSi copia in tali locazioni ivalori 3 e 2
a3
Si invoca somma(3,1)3200
b2
3800
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 3+2Calcolo di 3+2
Viene invocata Viene invocata
somma(3,1);somma(3,1);int somma (int a, int b)int somma (int a, int b){{
if (b==0)if (b==0)return a;return a;
elseelsereturn (somma(a,b-1)+1);return (somma(a,b-1)+1);
}}
SECONDA INVOCAZIONE DI SOMMA
All’entrata della funzionesi alloca memoria per le var.locale a e b RELATIVE A QUESTA INVOCAZIONESi copia in tali locazioni ivalori 3 e 1
a3
Si invoca somma(3,0)5700
b1
8100
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 3+2Calcolo di 3+2
Viene invocata Viene invocata
somma(3,0);somma(3,0);int somma (int a, int b)int somma (int a, int b){{
if (b==0)if (b==0)return a;return a;
elseelsereturn (somma(a,b-1)+1);return (somma(a,b-1)+1);
}}
TERZA INVOCAZIONE DI SOMMA
All’entrata della funzionesi alloca memoria per le var.locale a e b RELATIVE A QUESTA INVOCAZIONESi copia in tali locazioni ivalori 3 e 0
a3
Si ritorna il controllo restituendo 32700
b0
9000
somma(3,2)
somma(3,1)somma(3,0)
La memoria allocata viene rilasciata
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 3+2Calcolo di 3+2
Viene invocata Viene invocata
somma(3,1);somma(3,1);int somma (int a, int b)int somma (int a, int b){{
if (b==0)if (b==0)return a;return a;
elseelsereturn (somma(a,b-1)+1);return (somma(a,b-1)+1);
}}
SECONDA INVOCAZIONE DI SOMMA
All’entrata della funzionesi alloca memoria per le var.locale a e b RELATIVE A QUESTA INVOCAZIONESi copia in tali locazioni ivalori 3 e 1
a3
Si ritorna il controllo restituendo 4a somma (3,2)5700
b1
8100
La memoria allocata viene rilasciata
Ha restituito 3
somma(3,2)
somma(3,1)somma(3,0)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..
Calcolo di 3+2Calcolo di 3+2
Viene invocata Viene invocata
somma(3,2);somma(3,2);int somma (int a, int b)int somma (int a, int b){{
if (b==0)if (b==0)return a;return a;
elseelsereturn (somma(a,b-1)+1);return (somma(a,b-1)+1);
}}
PRIMA INVOCAZIONE DI SOMMA
All’entrata della funzionesi alloca memoria per le var.locale a e b RELATIVE A QUESTA INVOCAZIONESi copia in tali locazioni ivalori 3 e 2
a3
Si ritorna il controllo restituendo 5a main()3200
b2
3800
La memoria allocata viene rilasciata
Ha restituito 4
somma(3,2)
somma(3,1)somma(3,0)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un terzo esempioUn terzo esempio
Calcolo di a*bCalcolo di a*ba*b= a+a+… …+aa*b= a+a+… …+a
a*b=(a*(b-1))+aa*b=(a*(b-1))+aCaso baseCaso basea*1=aa*1=aa*0=0a*0=0
b volte
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Moltiplicazione tra due interiMoltiplicazione tra due interi
int prodotto (int a,int b)int prodotto (int a,int b){{
if (b==0)if (b==0)return 0;return 0;
if (b==1)if (b==1)return a;return a;
elseelsereturn (prodotto(a,b-1)+a);return (prodotto(a,b-1)+a);
}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un quarto esempioUn quarto esempio
Precondizione: a>=1Precondizione: a>=1Calcolo di aCalcolo di abb
aabb = a*a*… …*a = a*a*… …*a
aabb =(a =(ab-1b-1)*a)*aCaso baseCaso baseaa00 =1 =1
b volte
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Moltiplicazione tra due interiMoltiplicazione tra due interi
int potenza (int a,int b)int potenza (int a,int b)
{{
if (b==0)if (b==0)
return 1;return 1;
elseelse
return (potenza(a,b-1)*a);return (potenza(a,b-1)*a);
}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Numeri di FibonacciNumeri di Fibonacci
La serie di FibonacciLa serie di Fibonacci0,1,1,2,3,5,8,13,21,..0,1,1,2,3,5,8,13,21,..Comincia con i numero 0 e 1 ed ha la proprietà che se si 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)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 E’ una serie che occorre in natura. Il rapporto tra due
numeri consecutivi della serie di Fibonacci converge al numeri consecutivi della serie di Fibonacci converge al numero 1.618.. che è chiamata sezione aureanumero 1.618.. che è chiamata sezione aurea
Usare come rapporto tra dimensioni la sezione aurea è Usare come rapporto tra dimensioni la sezione aurea è esteticamente piacevoleesteticamente piacevole usato sin dall’antichità in usato sin dall’antichità in architettura (esempio rapporto tra le dimensioni di una architettura (esempio rapporto tra le dimensioni di una finestra, le dimensioni relative dei lati di una cartolina finestra, le dimensioni relative dei lati di una cartolina etc.) etc.)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
CodiceCodice
long Fibonacci (long n)long Fibonacci (long n)
{{
if ((n==0)||(n==1))if ((n==0)||(n==1))
return n;return n;
else else
return (Fibonacci(n-1)+Fibonacci(n-return (Fibonacci(n-1)+Fibonacci(n-2));2));
}}
Calcola F(n)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..Calcolo di Fibonacci(3)Calcolo di Fibonacci(3)
Viene invocata Viene invocata
x=Fibonacci(3);x=Fibonacci(3); long Fibonacci (long n)long Fibonacci (long n){{
if ((n==0)||(n==1))if ((n==0)||(n==1))return n;return n;
else else return (Fibonacci(n-1)+return (Fibonacci(n-1)+Fibonacci(n-2));Fibonacci(n-2));
}}
PRIMA INVOCAZIONE DI FIBONACCI
All’entrata della funzionesi alloca memoria per le var.nSi copia in tale locazione ilvalore 3
n3
Si invoca Fibonacci(2) E Fibonacci(1)
3200Attenzione: non si può sapere severrà valutata prima la chiamataFibonacci(2) O Fibonacci(1)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..Calcolo di Fibonacci(3)Calcolo di Fibonacci(3)
Viene invocata Viene invocata
Fibonacci(2);Fibonacci(2); long Fibonacci (long n)long Fibonacci (long n){{
if ((n==0)||(n==1))if ((n==0)||(n==1))return n;return n;
else else return (Fibonacci(n-1)+return (Fibonacci(n-1)+Fibonacci(n-2));Fibonacci(n-2));
}}
SECONDA INVOCAZIONE DI FIBONACCI
All’entrata della funzionesi alloca memoria per le var.n RELATIVA A QUESTAINVOCAZIONESi copia in tale locazione ilvalore 2
n2
Si invoca Fibonacci(1) E Fibonacci(0)
4000Attenzione: non si può sapere severrà valutata prima la chiamataFibonacci(1) O Fibonacci(0)
F(3)
F(1)F(2)
F(0)F(1)
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..Calcolo di Fibonacci(3)Calcolo di Fibonacci(3)
Viene invocata Viene invocata
Fibonacci(1);Fibonacci(1); long Fibonacci (long n)long Fibonacci (long n){{
if ((n==0)||(n==1))if ((n==0)||(n==1))return n;return n;
else else return (Fibonacci(n-1)+return (Fibonacci(n-1)+Fibonacci(n-2));Fibonacci(n-2));
}}
TERZA INVOCAZIONE DI FIBONACCI
All’entrata della funzionesi alloca memoria per le var.n RELATIVA A QUESTAINVOCAZIONESi copia in tale locazione ilvalore 1
n1
Si restituisce al chiamanteFibonacci(2) il valore 1
5900
F(3)
F(1)F(2)
F(0)F(1)
1
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..Calcolo di Fibonacci(3)Calcolo di Fibonacci(3)
Viene invocata Viene invocata
Fibonacci(0);Fibonacci(0); long Fibonacci (long n)long Fibonacci (long n){{
if ((n==0)||(n==1))if ((n==0)||(n==1))return n;return n;
else else return (Fibonacci(n-1)+return (Fibonacci(n-1)+Fibonacci(n-2));Fibonacci(n-2));
}}
QUARTA INVOCAZIONE DI FIBONACCI
All’entrata della funzionesi alloca memoria per le var.n RELATIVA A QUESTAINVOCAZIONESi copia in tale locazione ilvalore 0
n0
Si restituisce al chiamanteFibonacci(2) il valore 0
9900
F(3)
F(1)F(2)
F(0)F(1)
1
0
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..Calcolo di Fibonacci(3)Calcolo di Fibonacci(3)
Viene invocata Viene invocata
Fibonacci(1);Fibonacci(1); long Fibonacci (long n)long Fibonacci (long n){{
if ((n==0)||(n==1))if ((n==0)||(n==1))return n;return n;
else else return (Fibonacci(n-1)+return (Fibonacci(n-1)+Fibonacci(n-2));Fibonacci(n-2));
}}
QUINTA INVOCAZIONE DI FIBONACCI
All’entrata della funzionesi alloca memoria per le var.n RELATIVA A QUESTAINVOCAZIONESi copia in tale locazione ilvalore 1
n1
Si restituisce al chiamanteFibonacci(3) il valore 1
15000
F(3)
F(1)F(2)
F(0)F(1)
1
0
1
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..Calcolo di Fibonacci(3)Calcolo di Fibonacci(3)
Viene invocata Viene invocata
Fibonacci(2);Fibonacci(2); long Fibonacci (long n)long Fibonacci (long n){{
if ((n==0)||(n==1))if ((n==0)||(n==1))return n;return n;
else else return (Fibonacci(n-1)+return (Fibonacci(n-1)+Fibonacci(n-2));Fibonacci(n-2));
}}
All’entrata della funzionesi alloca memoria per le var.n RELATIVA A QUESTAINVOCAZIONESi copia in tale locazione ilvalore 2
n2
Si restituisce al chiamanteFibonacci(3) il valore 1
4000
10
F(3)
F(1)F(2)
F(0)F(1)
1
0
11
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempio..Un esempio..Calcolo di Fibonacci(3)Calcolo di Fibonacci(3)
Viene invocata Viene invocata
Fibonacci(3);Fibonacci(3); long Fibonacci (long n)long Fibonacci (long n){{
if ((n==0)||(n==1))if ((n==0)||(n==1))return n;return n;
else else return (Fibonacci(n-1)+return (Fibonacci(n-1)+Fibonacci(n-2));Fibonacci(n-2));
}}
All’entrata della funzionesi alloca memoria per le var.n RELATIVA A QUESTAINVOCAZIONESi copia in tale locazione ilvalore 3
n2
Si restituisce al chiamantemain il valore 2
3200
11
F(3)
F(1)F(2)
F(0)F(1)
1
0
11
2
Numero di chiamate necessariePer calcolare F(n) dell’ordine di2n complessità esponenziale
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
FibonacciFibonacciValore di nValore di n F(n)F(n) Numero di chiamate di Numero di chiamate di
funzione F(n)funzione F(n)00 00 1111 11 1122 11 3333 22 55……2323 2865728657 92735927352424 4636846368 1500491500492525 7502575025 242785242785……4141 165580141165580141 5358285915358285914242 267914296267914296 866988873866988873
La ricorsione in molti casi è utile però può ridurre l’efficienza. Numero dichiamate elevato significa che paghiamo un overhead elevato (tempo e spazio) per invocare le funzioni, allocare memoria per le variabili locali
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di HanoiTorri di Hanoi La leggenda narra che in un tempio del profondo La leggenda narra che in un tempio del profondo oriente i monaci fossero occupati nel compito di oriente i monaci fossero occupati nel compito di spostare dei dischi di pietra impilati in ordine di spostare dei dischi di pietra impilati in ordine di dimensione decrescente in un paletto A,dal dimensione decrescente in un paletto A,dal paletto (A) al paletto B. Il numero dei dischi era paletto (A) al paletto B. Il numero dei dischi era 64, esisteva anche un terzo paletto d’appoggio C.64, esisteva anche un terzo paletto d’appoggio C.
A B C
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di HanoiTorri di Hanoi La leggenda narra che in un tempio del profondo La leggenda narra che in un tempio del profondo oriente i monaci fossero occupati nel compito di oriente i monaci fossero occupati nel compito di spostare dei dischi di pietra impilati in ordine di spostare dei dischi di pietra impilati in ordine di dimensione decrescente in un paletto A,dal dimensione decrescente in un paletto A,dal paletto (A) al paletto B. Il numero dei dischi era paletto (A) al paletto B. Il numero dei dischi era 64, esisteva anche un terzo paletto d’appoggio C.64, esisteva anche un terzo paletto d’appoggio C.
A B C
Ogni mossa poteva portareallo spostamento di un unicodisco E in ogni momentoi dischi dovevanoessere posizionati inordine decrescente su ciascuno dei paletti
La leggenda narra che il mondo finirà primache i monaci siano riusciti a completarequesto compito!
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di Hanoi…un esempioTorri di Hanoi…un esempio La leggenda narra che in un tempio del profondo La leggenda narra che in un tempio del profondo oriente i monaci fossero occupati nel compito di oriente i monaci fossero occupati nel compito di spostare dei dischi di pietra impilati in ordine di spostare dei dischi di pietra impilati in ordine di dimensione decrescente in un paletto A,dal dimensione decrescente in un paletto A,dal paletto (A) al paletto B. Il numero dei dischi era paletto (A) al paletto B. Il numero dei dischi era 64, esisteva anche un terzo paletto d’appoggio C.64, esisteva anche un terzo paletto d’appoggio C.
A B C
Ad esempio il disco viola può esserespostato in una mossa da A a B
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di Hanoi…un esempioTorri di Hanoi…un esempio La leggenda narra che in un tempio del profondo La leggenda narra che in un tempio del profondo oriente i monaci fossero occupati nel compito di oriente i monaci fossero occupati nel compito di spostare dei dischi di pietra impilati in ordine di spostare dei dischi di pietra impilati in ordine di dimensione decrescente in un paletto A,dal dimensione decrescente in un paletto A,dal paletto (A) al paletto B. Il numero dei dischi era paletto (A) al paletto B. Il numero dei dischi era 64, esisteva anche un terzo paletto d’appoggio C.64, esisteva anche un terzo paletto d’appoggio C.
A B C
Nella mossa successiva il disco azzurro può essere spostato da A a C
Il disco azzurro NONpoteva essere spostatoda A a B perché talespostamento non avrebbesoddisfatto il vincolo diordinamento decrescentedei dischi in B
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di Hanoi…un esempioTorri di Hanoi…un esempio La leggenda narra che in un tempio del profondo La leggenda narra che in un tempio del profondo oriente i monaci fossero occupati nel compito di oriente i monaci fossero occupati nel compito di spostare dei dischi di pietra impilati in ordine di spostare dei dischi di pietra impilati in ordine di dimensione decrescente in un paletto A,dal dimensione decrescente in un paletto A,dal paletto (A) al paletto B. Il numero dei dischi era paletto (A) al paletto B. Il numero dei dischi era 64, esisteva anche un terzo paletto d’appoggio C.64, esisteva anche un terzo paletto d’appoggio C.
A B C
Nella mossa successiva nonpossiamo direttamente spostare il disco verde
Possiamo ad esempio prima spostare ildisco viola in C e poi il disco verde in B
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di HanoiTorri di HanoiProblema di difficile risoluzione iterativa se Problema di difficile risoluzione iterativa se abbiamo molti dischi (e dobbiamo trovare abbiamo molti dischi (e dobbiamo trovare un algoritmo che valga sempre, per un algoritmo che valga sempre, per qualsiasi numero di dischi)qualsiasi numero di dischi)Ragionare in modo ricorsivo aiuta a Ragionare in modo ricorsivo aiuta a trovare una soluzionetrovare una soluzione
A B
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di HanoiTorri di HanoiCosa vogliamo fare?Cosa vogliamo fare?– Muovere n dischi dal paletto A al paletto B Muovere n dischi dal paletto A al paletto B
usando C come appoggiousando C come appoggio
Come lo possiamo fare?Come lo possiamo fare?– Muovere n-1 dischi dal paletto A al paletto C Muovere n-1 dischi dal paletto A al paletto C
usando B come appoggiousando B come appoggio
A B
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di HanoiTorri di HanoiCosa vogliamo fare?Cosa vogliamo fare?– Muovere n dischi dal paletto A al paletto B usando C Muovere n dischi dal paletto A al paletto B usando C
come appoggiocome appoggio
Come lo possiamo fare?Come lo possiamo fare?– Muovere n-1 dischi dal paletto A al paletto C usando Muovere n-1 dischi dal paletto A al paletto C usando
B come appoggioB come appoggio– Spostare il disco più grande da A in BSpostare il disco più grande da A in B
A B
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di HanoiTorri di HanoiCosa vogliamo fare?Cosa vogliamo fare?– Muovere n dischi dal paletto A al paletto B usando C Muovere n dischi dal paletto A al paletto B usando C
come appoggiocome appoggio
Come lo possiamo fare?Come lo possiamo fare?– Muovere n-1 dischi dal paletto A al paletto C usando Muovere n-1 dischi dal paletto A al paletto C usando
B come appoggioB come appoggio– Spostare il disco più grande da A in BSpostare il disco più grande da A in B– Muovere n-1 dischi da C a B usando A come Muovere n-1 dischi da C a B usando A come
appoggioappoggio
A B
Chiamate ricorsive
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di Hanoi-CodiceTorri di Hanoi-Codice#include<stdio.h>#include<stdio.h>void hanoi (int,int[ ], int *, int [ ], int *, int [ ], int *);void hanoi (int,int[ ], int *, int [ ], int *, int [ ], int *);main()main(){{
int i,n,n_A,n_B,n_C;int i,n,n_A,n_B,n_C;int A[100]={0};int A[100]={0};int B[100]={0};int B[100]={0};int C[100]={0};int C[100]={0};n_A=n_B=n_C=0;n_A=n_B=n_C=0;printf(“inserisci un numero di dischi tra 1 e 100 \n”);printf(“inserisci un numero di dischi tra 1 e 100 \n”);scanf(“%d”, &n);scanf(“%d”, &n);while ((n>100)||(n<1))while ((n>100)||(n<1)){{
printf(“inserisci un numero di dischi tra 1 e 100 \n”);printf(“inserisci un numero di dischi tra 1 e 100 \n”);scanf(“%d”, &n);scanf(“%d”, &n);
}}for (i=0;i<n;i++)for (i=0;i<n;i++)
A[i]=i+1;A[i]=i+1;n_A=n;n_A=n;hanoi (n,A,&n_A, B, &n_B, C, &n_C);hanoi (n,A,&n_A, B, &n_B, C, &n_C);return 0;return 0;
}}
I vettori A, B, Cconterranno i dischi(ed il loro ordine)impilati nei pioli A,B, e C
Dato un vettore A, n_Aindicherà il numero didischi impilati in A (memorizzati nelle locazioni di memoria0,…,n_A-1)n_A sarà quindi anchel’indice della prossimaposizione libera del vettore
Numero di dischiVettore che rappresenta il primo pioloPuntatore alla prima locazionelibera relativa al primo piolo
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di Hanoi-CodiceTorri di Hanoi-Codice#include<stdio.h>#include<stdio.h>void hanoi (int,int[ ], int *, int [ ], int *, int [ ], int *);void hanoi (int,int[ ], int *, int [ ], int *, int [ ], int *);main()main(){{
int i,n,n_A,n_B,n_C;int i,n,n_A,n_B,n_C;int A[100]={0};int A[100]={0};int B[100]={0};int B[100]={0};int C[100]={0};int C[100]={0};n_A=n_B=n_C=0;n_A=n_B=n_C=0;printf(“inserisci un numero di dischi tra 1 e 100 \n”);printf(“inserisci un numero di dischi tra 1 e 100 \n”);scanf(“%d”, &n);scanf(“%d”, &n);while ((n>100)||(n<1))while ((n>100)||(n<1)){{
printf(“inserisci un numero di dischi tra 1 e 100 \n”);printf(“inserisci un numero di dischi tra 1 e 100 \n”);scanf(“%d”, &n);scanf(“%d”, &n);
}}for (i=0;i<n;i++)for (i=0;i<n;i++)
A[i]=i+1;A[i]=i+1;n_A=n;n_A=n;hanoi (n,A,&n_A, B, &n_B, C, &n_C);hanoi (n,A,&n_A, B, &n_B, C, &n_C);return 0;return 0;
}}
I dischi hanno associatoun indice da 1,..,n I dischi più grandi avrannoassociato un indice piùpiccolo
Se il primo piolo contieneI dischi in figura il corrispettivovettore A conterrà nelle primen_A=4 posizioni i valori 1,2,3,4
4
3
2
1
A11 22 33 44
4
n_A
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di Hanoi-CodiceTorri di Hanoi-Codice#include<stdio.h>#include<stdio.h>void hanoi (int,int[ ], int *, int [ ], int *, int [ ], int *);void hanoi (int,int[ ], int *, int [ ], int *, int [ ], int *);main()main(){{
int i,n,n_A,n_B,n_C;int i,n,n_A,n_B,n_C;int A[100]={0};int A[100]={0};int B[100]={0};int B[100]={0};int C[100]={0};int C[100]={0};n_A=n_B=n_C=0;n_A=n_B=n_C=0;printf(“inserisci un numero di dischi tra 1 e 100 \n”);printf(“inserisci un numero di dischi tra 1 e 100 \n”);scanf(“%d”, &n);scanf(“%d”, &n);while ((n>100)||(n<1))while ((n>100)||(n<1)){{
printf(“inserisci un numero di dischi tra 1 e 100 \n”);printf(“inserisci un numero di dischi tra 1 e 100 \n”);scanf(“%d”, &n);scanf(“%d”, &n);
}}for (i=0;i<n;i++)for (i=0;i<n;i++)
A[i]=i+1;A[i]=i+1;n_A=n;n_A=n;hanoi (n,A,&n_A, B, &n_B, C, &n_C);hanoi (n,A,&n_A, B, &n_B, C, &n_C);return 0;return 0;
}}
Inizializza i vettori A, B e C a zeron_A,n_B,n_C a zero (i vettori non hannoelementi memorizzati)
Prende da input un numero valido didischi n
Mette in A i vari dischi dal più grande al più piccolo(situazione quando si comincia a spostare da A a Bi dischi). Si aggiorna coerentemente n_A.
Si invoca la funzione hanoi il cuiCompito sarà spostare n dischi daA a B seguendo le regole per ilmovimento dei dischi e mantenendoaggiornate le informazioni sulcontenuto e num. Di elementi delvettore
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Torri di Hanoi-CodiceTorri di Hanoi-Codice/*pre: num >=1*//*pre: num >=1*/void hanoi(int num, int a[ ], int *N_a, int b[ ], int *N_b, int c[ ], int void hanoi(int num, int a[ ], int *N_a, int b[ ], int *N_b, int c[ ], int
*N_c)*N_c){{
if (num==1)if (num==1){{
b[(*N_b)]=a[(*N_a)-1];b[(*N_b)]=a[(*N_a)-1];(*N_b)=(*N_b)+1;(*N_b)=(*N_b)+1;(*N_a)=(*N_a)-1;(*N_a)=(*N_a)-1;
}}elseelse{{
hanoi(num-1,a,N_a,c,N_c,b,N_b);hanoi(num-1,a,N_a,c,N_c,b,N_b);b[(*N_b)]=a[(*N_a)-1];b[(*N_b)]=a[(*N_a)-1];(*N_b)=(*N_b)+1;(*N_b)=(*N_b)+1;(*N_a)=(*N_a)-1;(*N_a)=(*N_a)-1;hanoi (num-1,c,N_c,b,N_b,a,N_a);hanoi (num-1,c,N_c,b,N_b,a,N_a);
}}}}
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(4,A,&n_A,B,&n_B,C, &n_C); hanoi(4,A,&n_A,B,&n_B,C, &n_C);
43
2
1
4n_A 0n_B 0n_C
A B through C
hanoi (3, A, N_a, C, N_c, B, N_b);AC through B
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(3,A,N_a,C,N_c,B, N_b); hanoi(3,A,N_a,C,N_c,B, N_b);
43
2
1
4 0 0
A C through B
hanoi (2, A, N_a, B, N_b, C, N_c);AB through C
n_A n_B n_C
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(2,A,N_a,B,N_b,C, N_c); hanoi(2,A,N_a,B,N_b,C, N_c);
43
2
1
4 0 0
A B through C
hanoi (1, A, N_a, C, N_c, B, N_b);AC through B
n_A n_B n_C
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(1,A,N_a,C,N_c,B, N_b); hanoi(1,A,N_a,C,N_c,B, N_b);
43
2
1
4 0 0
A C through B
c[n_C]=a[n_A-1];n_A--;n_C++;
n_A n_B n_C
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(1,A,N_a,C,N_c,B, N_b); hanoi(1,A,N_a,C,N_c,B, N_b);
4
3
2
1
3 0 1
A C through B
c[n_C]=a[n_A-1];n_A--;n_C++;
n_A n_B n_C
Viene restituito ilcontrollo
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(2,A,N_a,B,N_b,C, N_c); hanoi(2,A,N_a,B,N_b,C, N_c);
A B through C
Viene restituito ilcontrollo a questachiamata
4
3
2
1
3 0 1n_A n_B n_C
b[n_B]=a[n_A-1];n_A--;n_B++;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(2,A,N_a,B,N_b,C, N_c); hanoi(2,A,N_a,B,N_b,C, N_c);
A B through C
Si invoca:hanoi (1, C, N_c, B, N_b, A, N_a);CB through A
43
2
1
2 1 1n_A n_B n_C
b[n_B]=a[n_A-1];n_A--;n_B++;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(1,C,N_c,B,N_b,A, N_a); hanoi(1,C,N_c,B,N_b,A, N_a);
C B through A
43
2
1
2 1 1n_A n_B n_C
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(1,C,N_c,B,N_b,A, N_a); hanoi(1,C,N_c,B,N_b,A, N_a);
C B through A
4
3
2
1
2 2 0n_A n_B n_C
Si restituisce il controllo alchiamante
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(2,A,N_a,B,N_b,C, N_c); hanoi(2,A,N_a,B,N_b,C, N_c);
A B through C
4
3
2
1
2 2 0n_A n_B n_C
hanoi (2,------------------)ha terminato le istruzioni da eseguire.Restituisce il controllo alchiamante
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(3,A,N_a,C,N_c,B, N_b); hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
Aveva invocato:hanoi (2, A, N_a, B, N_b, C, N_c);AB through C Questa invocazione ha ora ritornatoIl controllo
4
3
2
1
2 2 0n_A n_B n_C
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(3,A,N_a,C,N_c,B, N_b); hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
4
3
2
1
2 2 0n_A n_B n_C
Si esegue:c[n_C]=a[n_A-1];n_A--;n_C++;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(3,A,N_a,C,N_c,B, N_b); hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
4
3 21
1 2 1n_A n_B n_C
Si esegue:c[n_C]=a[n_A-1];n_A--;n_C++;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(3,A,N_a,C,N_c,B, N_b); hanoi(3,A,N_a,C,N_c,B, N_b);
A C through B
4
3 21
1 2 1n_A n_B n_C
Si esegue:c[n_C]=a[n_A-1];n_A--;n_C++;
Si invoca:hanoi (2, B, N_b, C, N_c, A, N_a);BC through A
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(2,B,N_b,C,N_c,A, N_a); hanoi(2,B,N_b,C,N_c,A, N_a);
B C through A
4
3 21
1 2 1n_A n_B n_C
Si invoca:hanoi (1, B, N_b, A, N_a, C, N_c);BA through C
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(1,B,N_b,A,N_a,C, N_C); hanoi(1,B,N_b,A,N_a,C, N_C);
B A through C
4
3 21
1 2 1n_A n_B n_C
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(1,B,N_b,A,N_a,C, N_C); hanoi(1,B,N_b,A,N_a,C, N_C);
B A through C
43 2
1
2 1 1n_A n_B n_C
Si restituisce il controllo alchiamante
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(2,B,N_b,C,N_c,A, N_a); hanoi(2,B,N_b,C,N_c,A, N_a);
B C through A
Aveva invocato:hanoi (1, B, N_b, A, N_a, C, N_c);BA through C Tale invocazione ha terminatorestituendo il controllo
43 2
1
2 1 1n_A n_B n_C
Si esegue:c[n_C]=b[n_A-1];n_B--;n_C++;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(2,B,N_b,C,N_c,A, N_a); hanoi(2,B,N_b,C,N_c,A, N_a);
B C through A
43
21
2 0 2n_A n_B n_C
Si esegue:c[n_C]=b[n_B-1];n_B--;n_C++;
Si invoca:hanoi (1, A, N_a, C, N_c, B, N_b);AC through B
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(1,A,N_a,C,N_c,B, N_c); hanoi(1,A,N_a,C,N_c,B, N_c);
A C through B
43
21
2 0 2n_A n_B n_C
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempiohanoi(1,A,N_a,C,N_c,B, N_c); hanoi(1,A,N_a,C,N_c,B, N_c);
A C through B
4
3
21
1 0 3n_A n_B n_C
Si restituisce il controllo al chiamante
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
B C through A
4
3
21
1 0 3n_A n_B n_C
Si restituisce il controllo al chiamante
hanoi(2,B,N_b,C,N_c,A, N_a); hanoi(2,B,N_b,C,N_c,A, N_a);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
A C through B
4
3
21
1 0 3n_A n_B n_C
Si restituisce il controllo al chiamante
hanoi(3,A,N_a,C,N_c,B, N_b); hanoi(3,A,N_a,C,N_c,B, N_b);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
A B through C
4
3
21
1 0 3n_A n_B n_C
hanoi(4,A,&n_A,B,&n_B,C, &n_C); hanoi(4,A,&n_A,B,&n_B,C, &n_C);
Si esegue:b[n_B]=a[n_A-1];n_B++;n_A--;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
A B through C
4
3
21
0 1 3n_A n_B n_C
hanoi(4,A,&n_A,B,&n_B,C, &n_C); hanoi(4,A,&n_A,B,&n_B,C, &n_C);
Si esegue:b[n_B]=a[n_A-1];n_B++;n_A--;
Si invocahanoi(3,C,N_c,B,N_b,A,N_a);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
C B through A
4
3
21
0 1 3n_A n_B n_C
hanoi(3,C,N_c,B,N_b,A,N_a);
Si invocahanoi(2,C,N_c,A,N_a,B,N_b);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
C A through B
4
3
21
0 1 3n_A n_B n_C
hanoi(2,C,N_c,A,N_a,B,N_b);
Si invocahanoi(1,C,N_c,B,N_b,A,N_a);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
C B through A
4
3
21
0 1 3n_A n_B n_C
hanoi(1,C,N_c,B,N_b,A,N_a);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
C B through A
4 3
21
0 2 2n_A n_B n_C
hanoi(1,C,N_c,B,N_b,A,N_a);
Si restituisce il controllo al chiamante
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
C A through B
4 3
21
0 2 2n_A n_B n_C
hanoi(2,C,N_c,A,N_a,B,N_b);
Si esegue:a[n_A]=c[n_C-1];n_A++;n_C--;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
C A through B
4
3 21
1 2 1n_A n_B n_C
hanoi(2,C,N_c,A,N_a,B,N_b);
Si esegue:a[n_A]=c[n_C-1];n_A++;n_C--;
Si invoca hanoi(1,B,N_b,A,N_a,C,N_c);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
B A through C
4
3 21
1 2 1n_A n_B n_C
hanoi(1,B,N_b,A,N_a,C,N_c);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
B A through C
4
3 21
2 1 1n_A n_B n_C
hanoi(1,B,N_b,A,N_a,C,N_c);
Si restituisce il controllo al chiamante
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
C A through B
4
3 21
2 1 1n_A n_B n_C
Si restituisce il controllo al chiamante
hanoi(2,C,N_c,A,N_a,B,N_b);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3 21
2 1 1n_A n_B n_C
C B through A
hanoi(3,C,N_c,B,N_b,A,N_a);
Si esegue:b[n_C]=c[n_C-1];n_B++;n_C--;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3
2
1
2 2 0n_A n_B n_C
C B through A
hanoi(3,C,N_c,B,N_b,A,N_a);
Si esegue:b[n_C]=c[n_C-1];n_B++;n_C--;
Si invoca hanoi(2,A,N_a,B,N_b,C,N_c);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3
2
1
2 2 0n_A n_B n_C
A B through C
hanoi(2,A,N_a,B,N_b,C,N_c);
Si invoca hanoi(1,A,N_a,C,N_c,B,N_b);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3
2
1
2 2 0n_A n_B n_C
A C through B
hanoi(1,A,N_a,C,N_c,B,N_b);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
43
2
1
1 2 1n_A n_B n_C
A C through B
hanoi(1,A,N_a,C,N_c,B,N_b);
Si restituisce il controlloal chiamante
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
43
2
1
1 2 1n_A n_B n_C
A B through C
hanoi(2,A,N_a,B,N_b,C,N_c);
Si esegue:b[n_C]=a[n_C-1];n_B++;n_A--;
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3
2
1
0 3 1n_A n_B n_C
A B through C
hanoi(2,A,N_a,B,N_b,C,N_c);
Si esegue:b[n_C]=a[n_C-1];n_B++;n_A--;
Si invoca: hanoi(1,C,N_c,B,N_b,A,N_a);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3
2
1
0 3 1n_A n_B n_C
C B through A
hanoi(1,C,N_c,B,N_b,A,N_a);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3
2
1
0 4 0n_A n_B n_C
C B through A
hanoi(1,C,N_c,B,N_b,A,N_a);
Si restituisce il controlloal chiamante
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3
2
1
0 4 0n_A n_B n_C
Si restituisce il controlloal chiamante
A B through C
hanoi(2,A,N_a,B,N_b,C,N_c);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3
2
1
0 4 0n_A n_B n_C
Si restituisce il controlloal chiamante
C B through A
hanoi(3,C,N_c,B,N_b,A,N_a);
Prof.ssa Chiara Petrioli -- Fondamenti diProf.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 programmazione, a.a. 2009/2010
Un esempioUn esempio
4
3
2
1
0 4 0n_A n_B n_C
Si restituisce il controlloal mainAbbiamo correttamentespostato i dischi dal primoal secondo piolo
A B through C
hanoi(4,A,&n_A,B,&n_B,C, &n_C); hanoi(4,A,&n_A,B,&n_B,C, &n_C);