Prof.ssa Chiara Petrioli -- corso di programmazione 1, a.a. 2006/2007 Corso di Programmazione 1 a.a.2007/2008 Prof.ssa Chiara Petrioli Corso di Laurea

Prof.ssa Chiara Petrioli -- corso di progrProf.ssa Chiara Petrioli -- corso di programmazione 1, a.a. 2006/2007ammazione 1, a.a. 2006/2007

Corso di Programmazione 1Corso di Programmazione 1a.a.2007/2008a.a.2007/2008Prof.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


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


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]?


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



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;


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



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;


00 11 22 …… 9898 9999 v

3000

3004 vPtr


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


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;


vPtr2=&v[99];vPtr2=&v[99];

00 11 22 …… 9898 9999 v

3000

3000 vPtr


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


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


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


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


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


Esercizio 1, Compito BEsercizio 1, Compito B

Si scriva una funzione che dato un vettore Si scriva una funzione che dato un vettore di interi ORDINATO calcoli il numero di di interi ORDINATO calcoli il numero di valori che compaiono ripetuti almeno una valori che compaiono ripetuti almeno una volta nel vettore volta nel vettore


Soluzioni compito BSoluzioni compito B/* conta il numero di elementi del vettore che vengono ripetuti *//* conta il numero di elementi del vettore che vengono ripetuti */int numRipetizioni (int vett[ ], int n) { int numRipetizioni (int vett[ ], int n) {

int check;int check;int done = 0;int done = 0;int count = 0;int count = 0;int i = 0;int i = 0;check = vett[0];check = vett[0];for (i = 1; i < n; i++) {for (i = 1; i < n; i++) {

if (check == vett[i]) { if (check == vett[i]) { if(done == 0) {if(done == 0) {

done = 1;done = 1;count++;count++;

}}} } else {else {

check = vett[i];check = vett[i];done = 0;done = 0;

}}}}



Esercizio 2, compito DEsercizio 2, compito D

Denominiamo un elemento di una matrice Denominiamo un elemento di una matrice di interi n*m un minimo diagonale se è di interi n*m un minimo diagonale se è l’elemento con il valore (strettamente) l’elemento con il valore (strettamente) minore tra quelli delle (due) diagonali a cui minore tra quelli delle (due) diagonali a cui appartiene. appartiene. Si scriva una funzione che data una Si scriva una funzione che data una matrice di interi ed un intero h calcoli il matrice di interi ed un intero h calcoli il numero dei suoi minimi diagonali con numero dei suoi minimi diagonali con valore > h valore > h


Soluzione esercizioSoluzione esercizioint minimoDiagonale2(int righe, int colonne, int matrix[][colonne], int h) {int minimoDiagonale2(int righe, int colonne, int matrix[][colonne], int h) {

int k, i ,j ;int k, i ,j ;int count = 0;int count = 0;for (i = 0; i < righe; i++) {for (i = 0; i < righe; i++) {

for (j = 0; j < righe; j++) {for (j = 0; j < righe; j++) {if (matrix[i][j] > h) {if (matrix[i][j] > h) { if (controlloDiagonale1(colonne, i, j, matrix) && if (controlloDiagonale1(colonne, i, j, matrix) && controlloDiagonale2(colonne, i, j, matrix) &&controlloDiagonale2(colonne, i, j, matrix) && controlloDiagonale3(righe, colonne, i, j, matrix) &&controlloDiagonale3(righe, colonne, i, j, matrix) && controlloDiagonale4(righe, colonne, i, j, matrix)) {controlloDiagonale4(righe, colonne, i, j, matrix)) {

count++;count++;}}

}}}}

}}return count;return count;

}}


Sol esercizio 2 compito DSol esercizio 2 compito Dint controlloDiagonale1(int num_colonne, int indice_riga, int int controlloDiagonale1(int num_colonne, int indice_riga, int

indice_colonna, int matrix[][num_colonne]) {indice_colonna, int matrix[][num_colonne]) {int valore = matrix[indice_riga][indice_colonna];int valore = matrix[indice_riga][indice_colonna];indice_riga--;indice_riga--;indice_colonna++;indice_colonna++;while (indice_riga >= 0 && indice_colonna < num_colonne) {while (indice_riga >= 0 && indice_colonna < num_colonne) {

if (valore >= matrix[indice_riga][indice_colonna]) {if (valore >= matrix[indice_riga][indice_colonna]) {return 0;return 0;

}}else {else {

indice_riga--;indice_riga--;indice_colonna++;indice_colonna++;

}}}}return 1;return 1;

}}


Sol esercizio 2 compito DSol esercizio 2 compito Dint controlloDiagonale2(int num_colonne, int indice_riga, int int controlloDiagonale2(int num_colonne, int indice_riga, int

indice_colonna, int matrix[][num_colonne]) {indice_colonna, int matrix[][num_colonne]) {int valore = matrix[indice_riga][indice_colonna];int valore = matrix[indice_riga][indice_colonna];indice_riga--;indice_riga--;indice_colonna--;indice_colonna--;while (indice_riga >= 0 && indice_colonna >= 0) {while (indice_riga >= 0 && indice_colonna >= 0) {


}}else {else {

indice_riga--;indice_riga--;indice_colonna--;indice_colonna--;


}}


Sol esercizio 2 compito DSol esercizio 2 compito Dint controlloDiagonale3(int num_righe, int num_colonne, int indice_riga, int controlloDiagonale3(int num_righe, int num_colonne, int indice_riga,

int indice_colonna, int matrix[][num_colonne]) {int indice_colonna, int matrix[][num_colonne]) {int valore = matrix[indice_riga][indice_colonna];int valore = matrix[indice_riga][indice_colonna];indice_riga++;indice_riga++;indice_colonna--;indice_colonna--;while (indice_riga < num_righe && indice_colonna >= 0) {while (indice_riga < num_righe && indice_colonna >= 0) {


}}else {else {

indice_riga++;indice_riga++;indice_colonna--;indice_colonna--;


}}


Sol esonero 2 compito DSol esonero 2 compito D

int controlloDiagonale4(int num_righe, int num_colonne, int indice_riga, int int controlloDiagonale4(int num_righe, int num_colonne, int indice_riga, int indice_colonna, int matrix[][num_colonne]) {indice_colonna, int matrix[][num_colonne]) {int valore = matrix[indice_riga][indice_colonna];int valore = matrix[indice_riga][indice_colonna];indice_riga++;indice_riga++;indice_colonna++;indice_colonna++;while (indice_riga < num_righe && indice_colonna < num_colonne) {while (indice_riga < num_righe && indice_colonna < num_colonne) {


}}else {else {

indice_riga++;indice_riga++;indice_colonna++;indice_colonna++;


}}


Esercizio 2 compito BEsercizio 2 compito B

Denominiamo un elemento di una matrice Denominiamo un elemento di una matrice di interi n*m un massimo diagonale se è di interi n*m un massimo diagonale se è l’elemento con il valore (strettamente) l’elemento con il valore (strettamente) maggiore tra quelli delle (due) diagonali a maggiore tra quelli delle (due) diagonali a cui appartiene. cui appartiene.

Si scriva una funzione che data una Si scriva una funzione che data una matrice di interi calcoli il numero dei suoi matrice di interi calcoli il numero dei suoi massimi diagonali. massimi diagonali.


EsempioEsempio


Compito B, secondo esercizioCompito B, secondo esercizioint massimoDiagonale(int righe, int colonne, int matrix[][colonne]) {int massimoDiagonale(int righe, int colonne, int matrix[][colonne]) {

int k, i ,j ;int k, i ,j ;int count = 0;int count = 0;/*scorre le diagonali che partono da (i, 0) con "i" indice di riga e controlla/*scorre le diagonali che partono da (i, 0) con "i" indice di riga e controllase tale diagonale contiene un massimo diagonale. In caso affermativo se tale diagonale contiene un massimo diagonale. In caso affermativo aumenta il contatore*/aumenta il contatore*/for (k = 0; k < righe; k++) {for (k = 0; k < righe; k++) {

count += esisteMassimoDiagonale(righe, colonne, k, 0, matrix);count += esisteMassimoDiagonale(righe, colonne, k, 0, matrix);}}/*scorre le diagonali che partono da (0, j) con "j" indice di colonna /*scorre le diagonali che partono da (0, j) con "j" indice di colonna (j > 0 perché tale caso è già stato controllato nel for precedente) e (j > 0 perché tale caso è già stato controllato nel for precedente) e controlla se tale diagonale contiene un massimo diagonale. In caso controlla se tale diagonale contiene un massimo diagonale. In caso affermativo affermativo aumenta il contatore*/aumenta il contatore*/for (k = 1; k < colonne; k++) {for (k = 1; k < colonne; k++) {

count += esisteMassimoDiagonale(righe, colonne, 0, k, matrix);count += esisteMassimoDiagonale(righe, colonne, 0, k, matrix);}}return count;return count;

}}


Compito B, secondo esercizioCompito B, secondo esercizioint esisteMassimoDiagonale(int num_righe, int num_colonne, int indice_riga, int indice_colonna, int esisteMassimoDiagonale(int num_righe, int num_colonne, int indice_riga, int indice_colonna,

int matrix[ ][num_colonne])int matrix[ ][num_colonne]){{

int i, j, k, aux_riga, aux_colonna;int i, j, k, aux_riga, aux_colonna;int check = matrix[indice_riga][indice_colonna];int check = matrix[indice_riga][indice_colonna];aux_riga = indice_riga;aux_riga = indice_riga;aux_colonna = indice_colonna;aux_colonna = indice_colonna;j = aux_colonna + 1;j = aux_colonna + 1;i = aux_riga + 1;i = aux_riga + 1;while (i < num_righe && j < num_colonne) {while (i < num_righe && j < num_colonne) {

if (check < matrix[i][j]) {if (check < matrix[i][j]) {check = matrix[i][j];check = matrix[i][j];aux_riga = i;aux_riga = i;aux_colonna = j;aux_colonna = j;

}}else {else {

if (check == matrix[i][j]) {if (check == matrix[i][j]) {aux_riga = -1;aux_riga = -1;aux_colonna = -1;aux_colonna = -1;

}}}}i++;i++;j++;j++;

}}


……fine funzionefine funzioneint check_diagonale1 = 1;int check_diagonale1 = 1;int check_diagonale2 = 1;int check_diagonale2 = 1;int uscita;int uscita;if (aux_riga != -1) {if (aux_riga != -1) {

i = aux_riga - 1;i = aux_riga - 1;j = aux_colonna + 1;j = aux_colonna + 1;uscita = 1;uscita = 1;while (i >= 0 && j < num_colonne && uscita) {while (i >= 0 && j < num_colonne && uscita) {

if (matrix[aux_riga][aux_colonna] <= matrix[i][j]) {if (matrix[aux_riga][aux_colonna] <= matrix[i][j]) {check_diagonale1 = 0;check_diagonale1 = 0;uscita = 0;uscita = 0;

}}else {else {

i--;i--;j++;j++;

}}}}


…….fine funzione.fine funzioneif (check_diagonale1) {if (check_diagonale1) {

i = aux_riga + 1;i = aux_riga + 1;j = aux_colonna - 1;j = aux_colonna - 1;uscita = 1;uscita = 1;while (i < num_righe && j >= 0 && uscita) {while (i < num_righe && j >= 0 && uscita) {

if (matrix[aux_riga][aux_colonna] <= matrix[i][j]) {if (matrix[aux_riga][aux_colonna] <= matrix[i][j]) {check_diagonale2 = 0;check_diagonale2 = 0;uscita = 0;uscita = 0;

}}else {else {

i++;i++;j--;j--;

}}}}

}}if (check_diagonale1 && check_diagonale2) { if (check_diagonale1 && check_diagonale2) {

return 1;return 1;}}

}}return 0;return 0;

}}

Siamo all’interno di ifaux_riga !=-1


Terzo esercizio, compito BTerzo esercizio, compito Bvoid eliminaInvertiStringa(int k) {void eliminaInvertiStringa(int k) {

char parola[255];char parola[255]; int count = 0;int count = 0; char testo[255];char testo[255]; char c;char c; while ((c = getchar()) != EOF) {while ((c = getchar()) != EOF) {

testo[count] = c;testo[count] = c; count++;count++;

}} testo [count] = '\0';testo [count] = '\0';

int len = strlen(testo);int len = strlen(testo);count=0;count=0;

while (len > 0) {while (len > 0) {if (testo[len-1] == '\n' || testo[len-1] == ' ') {if (testo[len-1] == '\n' || testo[len-1] == ' ') {

parola[count] = '\0';parola[count] = '\0';if (strlen(parola) <= k) {if (strlen(parola) <= k) {

printf("%s",parola);printf("%s",parola);}}count = 0;count = 0;if (testo[len-1] == '\n') {printf("\n"); }if (testo[len-1] == '\n') {printf("\n"); }if (testo[len-1]== ‘ ‘) {printf(” “); }if (testo[len-1]== ‘ ‘) {printf(” “); }}}

else {else {parola[count] = testo[len-1];parola[count] = testo[len-1];count++;count++;

}}len--;len--;

}}if (strlen(parola) <= k) {if (strlen(parola) <= k) {

parola[count] = '\0';parola[count] = '\0';printf("%s ",parola);printf("%s ",parola);

}}}}

Prende da input un testo e lo memorizza in unastringa

Calcola la lunghezza della stringa Contenente il testo

Stampa in ordine invertito le paroleche sono di al massimo k caratteriA mano a mano che legge una parolaLa mette in un vettore di appoggio parola


Soluzioni compito DSoluzioni compito D


Si scriva una funzione che dato un vettore Si scriva una funzione che dato un vettore di interi verifichi se è vero che ogni di interi verifichi se è vero che ogni elemento del vettore contenente un valore elemento del vettore contenente un valore dispari abbia un valore maggiore alla dispari abbia un valore maggiore alla somma degli elementi successivi.somma degli elementi successivi.



int dispariMaggiore (int vett[], int n) {int dispariMaggiore (int vett[], int n) {int somma = vett[n-1]; int somma = vett[n-1]; int i;int i;for (i = n-2; i >= 0; i--) {for (i = n-2; i >= 0; i--) {

if ((vett[i] % 2 != 0) && vett[i] <= somma) { if ((vett[i] % 2 != 0) && vett[i] <= somma) { return 0;return 0;

} } somma += vett[i];somma += vett[i];

}}return 1;return 1;

}}

/*Pre: vettore non vuoto*/



Si scriva una funzione che prenda da input Si scriva una funzione che prenda da input una stringa di testo composto da una stringa di testo composto da sequenze di caratteri divise da spazi e sequenze di caratteri divise da spazi e ritorni a capo. La funzione stampa i ritorni a capo. La funzione stampa i caratteri del testo in ordine invertito dopo caratteri del testo in ordine invertito dopo aver cancellato le sequenze di caratteri del aver cancellato le sequenze di caratteri del testo che contengono cifre.testo che contengono cifre.Vediamo la variante in cui invece il testo Vediamo la variante in cui invece il testo sia dato in una stringasia dato in una stringa


Soluzione esercizio 3, compito DSoluzione esercizio 3, compito Dvoid eliminaInvertiStringaNumeri(char testo[]) {void eliminaInvertiStringaNumeri(char testo[]) {

int len = strlen(testo);int len = strlen(testo);char parola[255];char parola[255];int count = 0;int count = 0;int check_num = 1;int check_num = 1;while (len > 0) {while (len > 0) {

if (testo[len-1] == '\n' || testo[len-1] == ' ' || testo[len-1] == '\0') {if (testo[len-1] == '\n' || testo[len-1] == ' ' || testo[len-1] == '\0') {parola[count] = '\0';parola[count] = '\0';

if (check_num) {if (check_num) {printf("%s",parola);printf("%s",parola);

}}else {else {

check_num = 1;check_num = 1;}}count = 0;count = 0;if (testo[len-1] == '\n') {if (testo[len-1] == '\n') {

printf("\n");printf("\n");}}if (testo[len-1] == ‘ ') {if (testo[len-1] == ‘ ') {

printf(“ ");printf(“ ");}}

}}else { else {

parola[count] = testo[len-1];parola[count] = testo[len-1];if (parola[count] >= '0' && parola[count] <= '9') {if (parola[count] >= '0' && parola[count] <= '9') {

check_num = 0;check_num = 0;}}count++;count++;

}}len--;len--;

}}if (check_num) {if (check_num) {

parola[count] = '\0';parola[count] = '\0';printf("%s ",parola);printf("%s ",parola);

}}}}

/*Pre: stringa di testo contenente soloCaratteri alfanumerici, spazi e newline*/


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.


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


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


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


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


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


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[ ]);


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


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;

}}}}


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


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


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?


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


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


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


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]


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


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.


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


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



Argomenti avanzati sulle funzioni…Argomenti avanzati sulle funzioni…

Classi di memoriaClassi di memoria

Regole di scopeRegole di scope


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


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 si suggerisce che venga Se una variabile è di tipo register si 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


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;



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)



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à


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


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

}}






}}

Il valore di x entrati in UseLocal all’iniziodella funzione è: 25Il valore di x entrati in UseLocal alla finedella funzione è: 26



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

}}



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

}}






}}

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






}}

Global x vale 1 all’entrata diuseGlobal Global x vale 10 alla fine diuseGlobal






}}

Il valore di x entrati in UseLocal all’iniziodella funzione è: 25Il valore di x entrati in UseLocal alla finedella funzione è: 26






}}

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






}}

Global x vale 10 all’entrata diuseGlobal Global x vale 100 alla fine diuseGlobal


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


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


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.


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





fatt(4);fatt(4);int fatt (int n)int fatt (int 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


5200








}}

TERZA INVOCAZIONE DI FATTfatt(3)



7800








}}

QUARTA INVOCAZIONE DI FATTfatt(2)



9800








}}

QUINTA INVOCAZIONE DI FATTfatt(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








}}

QUARTA INVOCAZIONE DI FATTfatt(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)








}}

TERZA INVOCAZIONE DI FATTfatt(3)

n3

7800 restituisce 2


fatt(5)fatt(4)

fatt(2)fatt(3)

fatt(1)








}}

SECONDA INVOCAZIONE DI FATTfatt(4)

n4

5200 restituisce 6


fatt(5)fatt(4)

fatt(2)fatt(3)

fatt(1)





x=fatt(5);x=fatt(5);int fatt (int n)int fatt (int 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)


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


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


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



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


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)



Calcolo di 3+2Calcolo di 3+2


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





somma(3,1);somma(3,1);int somma (int a, int b)int somma (int a, int b){{



}}

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








}}

TERZA INVOCAZIONE DI SOMMA


a3

Si ritorna il controllo restituendo 32700

b0

9000

somma(3,2)

somma(3,1)somma(3,0)

La memoria allocata viene rilasciata








}}

SECONDA INVOCAZIONE DI SOMMA


a3

Si ritorna il controllo restituendo 4a somma (3,2)5700

b1

8100


Ha restituito 3

somma(3,2)









}}

PRIMA INVOCAZIONE DI SOMMA


a3

Si ritorna il controllo restituendo 5a main()3200

b2

3800


Ha restituito 4

somma(3,2)



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


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;


elseelsereturn (prodotto(a,b-1)+a);return (prodotto(a,b-1)+a);

}}


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


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

}}


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.)


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)


Un esempio..Un esempio..Calcolo di Fibonacci(3)Calcolo di Fibonacci(3)


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)




Fibonacci(2);Fibonacci(2); long Fibonacci (long n)long Fibonacci (long n){{



}}

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)







}}

TERZA INVOCAZIONE DI FIBONACCI


n1

Si restituisce al chiamanteFibonacci(2) il valore 1

5900

F(3)

F(1)F(2)

F(0)F(1)

1







}}

QUARTA INVOCAZIONE DI FIBONACCI


n0


9900

F(3)

F(1)F(2)

F(0)F(1)

1

0







}}

QUINTA INVOCAZIONE DI FIBONACCI


n1


15000

F(3)

F(1)F(2)

F(0)F(1)

1

0

1







}}


n2


4000

10

F(3)

F(1)F(2)

F(0)F(1)

1

0

11







}}


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


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


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


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!


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



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



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


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


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


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


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


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 locazione che contiene La prima locazione libera relativa al primo piolo





}}for (i=0;i<n;i++)for (i=0;i<n;i++)


}}

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





}}for (i=0;i<n;i++)for (i=0;i<n;i++)


}}

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


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

}}}}

Sposto direttamente da a a b


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


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


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



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



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



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



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


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


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



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



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



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



A C through B

4

3 21

1 2 1n_A n_B n_C




A C through B

4

3 21

1 2 1n_A n_B n_C


Si invoca:hanoi (2, B, N_b, C, N_c, A, N_a);BC through A


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


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


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



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



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


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


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



B C through A

4

3

21

1 0 3n_A n_B n_C


hanoi(2,B,N_b,C,N_c,A, N_a); hanoi(2,B,N_b,C,N_c,A, N_a);



A C through B

4

3

21

1 0 3n_A n_B n_C


hanoi(3,A,N_a,C,N_c,B, N_b); hanoi(3,A,N_a,C,N_c,B, N_b);



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



A B through C

4

3

21

0 1 3n_A n_B 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);



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



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



C B through A

4

3

21

0 1 3n_A n_B n_C




C B through A

4 3

21

0 2 2n_A n_B n_C





C A through B

4 3

21

0 2 2n_A n_B n_C


Si esegue:a[n_A]=c[n_C-1];n_A++;n_C--;



C A through B

4

3 21

1 2 1n_A n_B n_C


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



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



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




C A through B

4

3 21

2 1 1n_A n_B n_C





4

3 21

2 1 1n_A n_B n_C

C B through A


Si esegue:b[n_C]=c[n_C-1];n_B++;n_C--;



4

3

2

1

2 2 0n_A n_B n_C

C B through 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);



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



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



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



43

2

1

1 2 1n_A n_B n_C

A B through C


Si esegue:b[n_C]=a[n_C-1];n_B++;n_A--;



4

3

2

1

0 3 1n_A n_B n_C

A B through 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);



4

3

2

1

0 3 1n_A n_B n_C

C B through A




4

3

2

1

0 4 0n_A n_B n_C

C B through A





4

3

2

1

0 4 0n_A n_B n_C


A B through C




4

3

2

1

0 4 0n_A n_B n_C


C B through A




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




Ricorsione e vettoriRicorsione e vettori

Si scriva una funzione ricorsiva somma_v che Si scriva una funzione ricorsiva somma_v che dato un vettore di interi vett produca in output dato un vettore di interi vett produca in output la somma degli elementi di vettla somma degli elementi di vett


Ricorsione e vettoriRicorsione e vettori

Si scriva una funzione ricorsiva somma_v che Si scriva una funzione ricorsiva somma_v che dato un vettore di interi vett produca in output dato un vettore di interi vett produca in output la somma degli elementi di vettla somma degli elementi di vett– Se il vettore ha un unico elemento allora la somma Se il vettore ha un unico elemento allora la somma

dei suoi elementi è pari al valore dell’elementodei suoi elementi è pari al valore dell’elemento– Altrimenti la somma dei primi n elementi è pari al Altrimenti la somma dei primi n elementi è pari al

valore dell’n-esimo elemento + la somma dei primi valore dell’n-esimo elemento + la somma dei primi n-1 elementi n-1 elementi

00 33 22 …… -1-1 99 vett

Tale somma èottenuta tramitechiamata ricorsiva


Somma degli elementi di un vettoreSomma degli elementi di un vettore

/*pre: il vettore ha almeno un elemento*//*pre: il vettore ha almeno un elemento*/int somma_v(int vett[ ], int n)int somma_v(int vett[ ], int n){{

if (n==1)if (n==1)return (vett[0]);return (vett[0]);

elseelsereturn (vett[n-1]+somma_v(vett,n-1));return (vett[n-1]+somma_v(vett,n-1));

}}


Ricerca di un elemento in un vettoreRicerca di un elemento in un vettoreSi scriva una funzione ricorsiva search_v che dato Si scriva una funzione ricorsiva search_v che dato un vettore di interi vett ed un intero key determini un vettore di interi vett ed un intero key determini se l’elemento key è presente tra gli elementi del se l’elemento key è presente tra gli elementi del vettorevettore– Se il vettore ha un unico elemento allora la funzione Se il vettore ha un unico elemento allora la funzione

restituisce 1 se l’elemento del vettore ha valore pari a restituisce 1 se l’elemento del vettore ha valore pari a key, 0 altrimentikey, 0 altrimenti

– Altrimenti la funzione restituisce 1 se e solo se O Altrimenti la funzione restituisce 1 se e solo se O l’elemento key è contenuto nell’ultimo elemento del l’elemento key è contenuto nell’ultimo elemento del vettore OPPURE è contenuto nei primi n-1 elementi del vettore OPPURE è contenuto nei primi n-1 elementi del vettore vettore

00 33 22 …… -1-1 99 vett

Tale verifica èeffettuata tramitechiamata ricorsiva

key=3


Ricerca di un elemento in un Ricerca di un elemento in un vettorevettore

/*pre: il vettore ha almeno un elemento*//*pre: il vettore ha almeno un elemento*/int search_v(int vett[ ], int n, int key)int search_v(int vett[ ], int n, int key){{

if (n==1)if (n==1)return (vett[0]==key);return (vett[0]==key);

elseelsereturn ((vett[n-1]==key)||return ((vett[n-1]==key)||

(search_v(vett,n-1,key)));(search_v(vett,n-1,key)));}}


Minimo in un vettoreMinimo in un vettoreSi scriva una funzione ricorsiva min_v che dato un Si scriva una funzione ricorsiva min_v che dato un vettore di interi vett determini il valore vettore di interi vett determini il valore dell’elemento più piccolo del vettoredell’elemento più piccolo del vettore– Se il vettore ha un unico elemento allora la funzione Se il vettore ha un unico elemento allora la funzione

restituisce il valore dell’elementorestituisce il valore dell’elemento– Altrimenti si calcola il valore più piccolo tra i primi n-1 Altrimenti si calcola il valore più piccolo tra i primi n-1

elementi. Se tale valore è più piccolo dell’n-esimo elementi. Se tale valore è più piccolo dell’n-esimo elemento allora è il valore più piccolo del vettore. elemento allora è il valore più piccolo del vettore. ALTRIMENTI il valore più piccolo del vettore è costituito ALTRIMENTI il valore più piccolo del vettore è costituito dall’n-esimo elemento del vettore dall’n-esimo elemento del vettore

00 33 22 …… -1-1 99 vettIl valore più piccolo tra i primi n-1 elementi è restituito dalla chiamataricorsiva


Minimo in un vettoreMinimo in un vettore/*pre: il vettore ha almeno un elemento*//*pre: il vettore ha almeno un elemento*/int min_v(int vett[ ], int n)int min_v(int vett[ ], int n){{

int temp;int temp;if (n==1)if (n==1)

return (vett[0]);return (vett[0]);elseelse{{

temp=min_v(vett,n-1);temp=min_v(vett,n-1);if (temp<vett[n-1])if (temp<vett[n-1])

return temp;return temp;elseelse

return (vett[n-1]);return (vett[n-1]);}}

}}


EserciziEsercizi

Esercizi su stringhe e caratteri Esercizi su stringhe e caratteri – Versioni iterativeVersioni iterative– Versioni ricorsive Versioni ricorsive ® per indicare una ® per indicare una

soluzione ricorsivasoluzione ricorsiva


Esercizio 1Esercizio 1

Si scriva una procedura Iterativa che, dato un testo (di dimensione minore di max_size), stampi il testo invertito e senza gli spazi

Si memorizza il testo –tranne gli spazi-in una stringa

si stampano i caratteri della stringa (dall’ultimo al primo)


Esercizio 1-caratteriEsercizio 1-caratteri

void elimina_spazi_e_inverti (int max_size)void elimina_spazi_e_inverti (int max_size){{ int c,count,i;int c,count,i; char str[max_size];char str[max_size]; count=0;count=0; while (((c=getchar()) != EOF) &&(count<max_size)) while (((c=getchar()) != EOF) &&(count<max_size)) {{ if (c!=‘ ‘)if (c!=‘ ‘) {{ str[count]=c;str[count]=c; count++;count++; }} }} str[count]=‘\0’;str[count]=‘\0’; for (i=count-1;i>=0;i- -)for (i=count-1;i>=0;i- -) printf(“%c”,str[i]);printf(“%c”,str[i]);}}

Si scriva una procedura Iterativa che, dato un testo (di dimensioneminore di max_size),

stampi il testoinvertito e senza

gli spazi


Esercizio 1, versione ricorsivaEsercizio 1, versione ricorsiva

Si scriva una procedura ricorsiva che, dato un testo stampi il testo invertito e senza gli spazi

Leggi il carattere corrente e memorizzalo in cLeggi il resto del testo stampandolo invertito e senza gli spaziSe c è diverso da uno spazio stampa c


Esercizio 1-caratteri ®Esercizio 1-caratteri ®

void Relimina_spazi_e_inverti ()void Relimina_spazi_e_inverti (){{ int c;int c; if ((c=getchar()) != EOF) if ((c=getchar()) != EOF) {{ Relimina_spazi_e_inverti();Relimina_spazi_e_inverti(); if (c!=‘ ‘)if (c!=‘ ‘) putchar ( c);putchar ( c);}}}}

Si scriva una procedura ricorsiva che, dato un testo stampa il testo

invertito e senzagli spazi


Esercizio 1-stringheEsercizio 1-stringhe/*stampa di una stringa *//*stampa di una stringa */void printstringa (char *);void printstringa (char *);

main()main(){{char str1[1024];char str1[1024];printf(“inserisci stringa \n”);printf(“inserisci stringa \n”);scanf(“%s”,str1);scanf(“%s”,str1);printstringa(str1);printstringa(str1);………………………………………………}}

/*Post: stampa il contenuto della stringa*//*Post: stampa il contenuto della stringa*/void printstringa (char *s)void printstringa (char *s){{

for (;*s!=‘\0’;s++) for (;*s!=‘\0’;s++) putchar(*s);putchar(*s);

}}

Si scriva una procedura iterativa

che, data una stringa s presa in

input ne stampi i caratteri in output

OPPURE:void printstringa (char *s){ int i; for (i=0;s[i]!=‘\0’;i++) putchar(s[i]);}


Esercizio 1-stringheEsercizio 1-stringhe

Si scriva una procedura ricorsiva

che, data una stringa s presa in input ne stampi i caratteri in output

Stampa l’elemento correnteStampa il resto degli elementi della stringa


Esercizio 1-stringhe ®Esercizio 1-stringhe ®/*stampa di una stringa (ricorsiva)*//*stampa di una stringa (ricorsiva)*/void Rprintstringa (char *);void Rprintstringa (char *);

main()main(){{char str1[1024];char str1[1024];printf(“inserisci stringa \n”);printf(“inserisci stringa \n”);scanf(“%s”,str1);scanf(“%s”,str1);Rprintstringa(str1);Rprintstringa(str1);………………………………………………}}

/*Post: stampa il contenuto della stringa*//*Post: stampa il contenuto della stringa*/void Rprintstringa (char *s)void Rprintstringa (char *s){{

if (*s != '\0')if (*s != '\0'){{putchar(*s);putchar(*s);Rprintstringa (s+1);Rprintstringa (s+1);

}}}}



input ne stampi i caratteri in output

Attenzione: qui abbiamo usatol’aritmetica dei puntatori perchiamare la funzione ricorsivasul resto della stringa, esclusol’elemento corrente

Come dovremmo modificare il codiceper stampare i caratteri della stringa inordine inverso?


Esercizio 2-stringheEsercizio 2-stringhe


che, data una stringa s presa in input ne stampi i caratteri in output in ordine inverso

Memorizza l’elemento corrente in cStampa il resto degli elementi della stringa in ordine inversoStampa quanto memorizzato in c


Esercizio 2-stringhe ®Esercizio 2-stringhe ®/*stampa di una stringa (ricorsiva)*//*stampa di una stringa (ricorsiva)*/void Rprintstringa_invertita (char *);void Rprintstringa_invertita (char *);

main()main(){{char str1[1024];char str1[1024];printf(“inserisci stringa \n”);printf(“inserisci stringa \n”);scanf(“%s”,str1);scanf(“%s”,str1);Rprintstringa_invertita(str1);Rprintstringa_invertita(str1);………………………………………………}}

/*Post: stampa il contenuto della stringa invertito*//*Post: stampa il contenuto della stringa invertito*/void Rprintstringa_invertita (char *s)void Rprintstringa_invertita (char *s){{

if (*s != '\0')if (*s != '\0'){{

Rprintstringa_invertita(s+1);Rprintstringa_invertita(s+1); putchar(*s);putchar(*s);

}}}}



input ne stampi i caratteri in output in ordine

invertito


Cosa succede in memoria…Cosa succede in memoria…All’entrata nella funzione si alloca memoria per il All’entrata nella funzione si alloca memoria per il puntatore s che punta al primo elemento della puntatore s che punta al primo elemento della stringa correntestringa corrente

Non siamo arrivati al carattere di fine stringa Non siamo arrivati al carattere di fine stringa quindi si invoca la chiamata ricorsivaquindi si invoca la chiamata ricorsiva

void Rprintstringa_invertita (char *s)void Rprintstringa_invertita (char *s){{

if (*s != '\0')if (*s != '\0'){{


}}}}

bb ll uu ee \0\0

7200 s

7200

L’invocazione della chiamataricorsiva farà stampare in ordineinverso il resto della stringa a partiredal secondo carattere(s+1) è la locazione di memoriadove è memorizzato il secondocarattere della stringaeul


Cosa succede in memoria…Cosa succede in memoria…All’entrata nella funzione si alloca memoria per il All’entrata nella funzione si alloca memoria per il puntatore s che punta al primo elemento della puntatore s che punta al primo elemento della stringa correntestringa corrente

Non siamo arrivati al carattere di fine stringa Non siamo arrivati al carattere di fine stringa quindi si invoca la chiamata ricorsivaquindi si invoca la chiamata ricorsiva

void Rprintstringa_invertita (char *s)void Rprintstringa_invertita (char *s){{

if (*s != '\0')if (*s != '\0'){{


}}}}

bb ll uu ee \0\0

7200 s

7200

L’invocazione della chiamataricorsiva farà stampare in ordineinverso il resto della stringa a partiredal secondo carattere(s+1) è la locazione di memoriadove è memorizzato il secondocarattere della stringaeul

Basterà quindi stampare ilcarattere puntato da s

eulb


Esercizio 3-stringheEsercizio 3-stringhe/*calcola la lunghezza di una stringa *//*calcola la lunghezza di una stringa */int String_length(char *);int String_length(char *);

main()main(){{char str1[1024];char str1[1024];printf(“inserisci una stringa \n”);printf(“inserisci una stringa \n”);scanf(“%s”,str1);scanf(“%s”,str1);printf(“la lunghezza della stringa e’ %d \n”, String_length(str1));printf(“la lunghezza della stringa e’ %d \n”, String_length(str1));………………………………………………}}

/*calcola la lunghezza della stringa*//*calcola la lunghezza della stringa*/

int String_length(char *s1)int String_length(char *s1){{ int count=0:int count=0:

while (*s1 != ‘\0’)while (*s1 != ‘\0’) { {

count++;count++; s1++;s1++; }}

return count;return count;}}

Si scriva una funzione iterativa

che, data una stringa ne calcoli il numero di caratteri (escluso

il carattere di fine stringa)


Esercizio 3-stringhe ®Esercizio 3-stringhe ®/*calcola il numero di caratteri in una stringa*//*calcola il numero di caratteri in una stringa*/int Rsizestringa (char *, int);int Rsizestringa (char *, int);

main()main(){{char str1[1024];char str1[1024];printf(“inserisci stringa \n”);printf(“inserisci stringa \n”);scanf(“%s”,str1);scanf(“%s”,str1);printf(“il numero di caratteri della stringa e’ %d \n”,printf(“il numero di caratteri della stringa e’ %d \n”,Rsizestringa(str1,0) );Rsizestringa(str1,0) );………………………………………………}}

/*calcola il numero di caratteri in una stringa*//*calcola il numero di caratteri in una stringa*//*Pre: s stringa, i>=0, chiamato con i==0 *//*Pre: s stringa, i>=0, chiamato con i==0 *//*Post: restituisce il numero di caratteri della /*Post: restituisce il numero di caratteri della stringa (escluso il carattere di fine stringa */stringa (escluso il carattere di fine stringa */int Rsizestringa(char s[ ], int i)int Rsizestringa(char s[ ], int i){{

if(s[i]=='\0')if(s[i]=='\0')return 0;return 0;

elseelsereturn (1+Rsizestringa(s,i+1));return (1+Rsizestringa(s,i+1));

}}



input calcoli il numerodi caratteri della

stringa (escluso ilcarattere di fine stringa)

OPPURE:int Rsizestringa (char *s){ if (*s == '\0') return 0; else return (1+Rsizestringa(s+1));}


Manipolazione di reali in CManipolazione di reali in C

I numeri reali sono rappresentati in binario I numeri reali sono rappresentati in binario nel computernel computer

1/10=0.1 è rappresentato nella forma 1/10=0.1 è rappresentato nella forma frazionaria binaria comefrazionaria binaria come

0.00011001100110011001100110011001100.0001100110011001100110011001100110011001100110011...011001100110011...

La rappresentazione dei reali è binaria. Alcuni numeri che ciSembrerebbero perfettamente rappresentabili hanno dei problemidi rappresentazione in binario.


Manipolazione di reali in CManipolazione di reali in C

Ragionando in base 10 è facile comprendere un Ragionando in base 10 è facile comprendere un problema: problema:

Consideriamo la frazione 1/3Consideriamo la frazione 1/3

Corrisponde ad un numero periodicoCorrisponde ad un numero periodico– 0.333….0.333….I numeri reali in una macchina sono memorizzati con I numeri reali in una macchina sono memorizzati con

un numero limitato di byte un numero limitato di byte si perde in precisione si perde in precisione nella rappresentazionenella rappresentazione

Il problema non riguarda solo i numero periodici!Il problema non riguarda solo i numero periodici!


Errore nella rappresentazione dei Errore nella rappresentazione dei realireali

Abbiamo un numero limitato di byte (es. 8) Abbiamo un numero limitato di byte (es. 8) per rappresentare un double.per rappresentare un double.

Tra quanti numeri è possibile distinguere Tra quanti numeri è possibile distinguere usando 8*8=64 bit?usando 8*8=64 bit?


Errore nella rappresentazione dei Errore nella rappresentazione dei realireali

Abbiamo un numero limitato di byte (es. 8) Abbiamo un numero limitato di byte (es. 8) per rappresentare un double.per rappresentare un double.

Tra quanti numeri è possibile distinguere Tra quanti numeri è possibile distinguere usando 8*8=64 bit?usando 8*8=64 bit?

226464

L’intervallo dei reali rappresentati è quindi diviso in 226464 sottointervalliniNon possiamo avere una rappresentazione dell’intervallo continuodei numeri reali

Se immaginate che il numero reale che si trova nel mezzo dell’intervallo sia rappresentato con la sequenzadi bit che è associata all’intervallo, e che tutti gli altrivalori che cadono nell’intervallo siano approssimaticon tale sequenza di bit l’errore massimo è q/2 conq ampiezza dei sottointervallini.

c’è un errore di rappresentazione maggiore il numero di bit minore l’errore di rappresentazioneChe comunque non può essere totalmente annullato

È un errore di rappresentazione che ci portiamo dietro e che può ancheAccumularsi facendo operazioni sui reali


EsempioEsempio

Nel caso di 0.1Nel caso di 0.1

La stampa del valore decimale La stampa del valore decimale dell’approssimazione binaria del numero dell’approssimazione binaria del numero fornisce il seguente risultatofornisce il seguente risultato

0.100000000000000010.10000000000000001

Non è un bug! Come abbiamo visto dipende dalla rappresentazionedei numeri reali


EsempioEsempio

Fare operazioni sui reali può portare a Fare operazioni sui reali può portare a sorpresesorprese

sum = 0.0sum = 0.0

for (i=0;i<10;i++)for (i=0;i<10;i++)

sum += 0.1;sum += 0.1;

Il valore di sum all’uscita dal ciclo è:Il valore di sum all’uscita dal ciclo è:

0.999999999999999890.99999999999999989


In sintesiIn sintesiLa rappresentazione dei reali porta ad approssimazioni, La rappresentazione dei reali porta ad approssimazioni, che possono accumularsi o bilanciarsi facendo operazioni che possono accumularsi o bilanciarsi facendo operazioni sui realisui reali– Non è un bug, è q.sa di intrinseco nella rappresentazione di un Non è un bug, è q.sa di intrinseco nella rappresentazione di un

intervallo continuo in una macchinaintervallo continuo in una macchina

Cosa si può fare:Cosa si può fare:– tenerne conto nello scrivere un programma (nessuna soluzione tenerne conto nello scrivere un programma (nessuna soluzione

prefatta, criteri generali-vedi qui di seguito- e buon senso portano prefatta, criteri generali-vedi qui di seguito- e buon senso portano alla soluzione)alla soluzione)

– Ad esempio anziché testare se A=B nel caso in cui A e B siano Ad esempio anziché testare se A=B nel caso in cui A e B siano diversi, testare se A e B sono pressochè uguali |A-B|<= epsilon diversi, testare se A e B sono pressochè uguali |A-B|<= epsilon (cercando così di filtrare problemi di rappresentazione che si (cercando così di filtrare problemi di rappresentazione che si ripercuotono tipicamente sulle cifre meno significative).ripercuotono tipicamente sulle cifre meno significative).

– Esistono librerie ‘a precisione infinita’ (o meglio a precisione Esistono librerie ‘a precisione infinita’ (o meglio a precisione arbitraria)arbitraria)libreria BigDigitslibreria BigDigits

Non sono a precisione infinita ma cercano di allocare dinamicamente Non sono a precisione infinita ma cercano di allocare dinamicamente maggiore o minore memoria per memorizzare i numeri reali in modo da maggiore o minore memoria per memorizzare i numeri reali in modo da aumentare l’accuratezza con cui sono rappresentatiaumentare l’accuratezza con cui sono rappresentati

Memorizzano in strutture dati a dimensione variabile i numeri realiMemorizzano in strutture dati a dimensione variabile i numeri reali Rallentano l’esecuzioneRallentano l’esecuzione

Documents

Prof.ssa Chiara Petrioli -- corso di programmazione 1, a.a. 2006/2007 Corso di Programmazione 1 a.a.2007/2008 Prof.ssa Chiara Petrioli Corso di Laurea