Corso di Fondamenti di Programmazione a.a.2009/2010 Prof.ssa Chiara Petrioli Corso di Laurea in Informatica Università degli Studi “La Sapienza” (lezioni 6 e 7) funzioni e vettori Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Come vengono gestiti progetti complessi Approccio top-down: data la descrizione del progetto si devono individuare dei task che devono essere eseguiti (ed in che ordine) per portare a compimento il progetto Ciascun task avrà bisogno di informazioni iniziali (input) consisterà nell’eseguire a sua volta delle azioni per produrre il risultato voluto (output o valore di ritorno del task) Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Come vengono gestiti progetti complessi Esempio: a Bob, manager di Telecom viene dato il compito di fare un progetto di reti che consenta a tutte le 400 filiali della ditta NastroRosa di essere interconnesse in una rete aziendale. Il compito di Bob è quello di presentare un progetto al cliente (ditta NastroRosa) che soddisfi le specifiche del cliente stesso. ? Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Come vengono gestiti progetti complessi Esempio: Bob riceve in input, dialogando con il cliente, delle informazioni Quanto deve costare il progetto Le caratteristiche delle varie sedi (numero di computer da interconnettere,quantità di dati che devono essere scambiate, quindi capacità che devono avere i link..) etc... Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Come vengono gestiti progetti complessi Esempio: Sulla base di queste informazioni Bob identifica una serie di passi che devono essere effettuati per svolgere il progetto Prepara un documento che descrivere la caratteristiche tecniche del progetto Chiede quindi a Alan, che è un Technical Manager, dato il documento con le caratteristiche tecniche del progetto, di produrre la soluzione tecnica dettagliata per il progetto Ricevuto da Alan tale soluzione chiederà, in base alla soluzione, al suo collaboratore Kevin di stimare i costi dettagliati del progetto, applicando gli sconti quando possibile. Se i requisiti tecnici ed economici del cliente sono soddisfatti presenterà la soluzione finale al cliente, altrimenti rivedrà il documento di caratteristiche tecniche del progetto (ad esempio cercando di abbassare i costi) e ripeterà l’iterazione Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Come vengono gestiti progetti complessi Esempio: Sulla base di queste informazioni Bob identifica una serie di passi che devono essere effettuati per svolgere il progetto TASK1 TASK2 Prepara un documento che descrivere la caratteristiche tecniche del progetto Chiede quindi a Alan, che è un Technical Manager, dato il documento con le caratteristiche tecniche del progetto, di produrre la soluzione tecnica dettagliata per il progetto Ricevuto da Alan tale soluzione chiederà, in base alla soluzione, al suo collaboratore Kevin di stimare i costi dettagliati del progetto, applicando gli sconti quando possibile. Se i requisiti tecnici ed economici del clientecomplesso. sono soddisfatti Ciascuno di questi task è un compito Ciascuno di questi task un compito complesso. presenterà la soluzione finale al ècliente, altrimenti rivedrà il Quello che Bob fa è Per portarlo a compimento dovrà essere a sua volta strutturato documento caratteristiche del progetto (ad esempio Chiarire il di compito che devetecniche essere effettuato (e quindi il tipo in azioni più elementari. Bob non conosce (e non gli output atteso dall’esecuzione del task) cercando di di abbassare i costi) e ripeterà l’iterazione interessa) come verrà svolto in dettaglio tale compito; gli Prof.ssa Chiara Petrioli necessarie -- Fondamenti di per Fornire le informazioni (input) svolgere il task programmazione, a.a.fornito 2009/2010l’output richiesto. interessa che gli venga Come vengono gestiti progetti complessi Esempio: Kevin per stimare i costi dettagliati del progetto Inserisce i dati sulle specifiche del progetto nel sistema aziendale Approccio modulare Invoca un tool che calcolo dei costi Ognicalcola task unil modulo in passi elevate chiede sconti Per alcune vociLa discomposizione costo eccessivamente elementari del task è del tutto particolari trasparente a chi invoca il – contatta John, che si occupa di approvare sconti maggiori dello modulo (chiede che il task venga standard con richieste in tal senso. John seguirà le procedure aziendali portato a completamento) per decidere se tali sconti possono essere accettati e fornirà i valori rivisti dei costi come output. Ad esempio: se cambia la Approccio top-down procedura interna per Gestione gerarchica Bob per successivi raffinamenti stimare i prezzi o per il problema viene scomposto concedere sconti questo in passi elementari sarà del tutto trasparente a Kevin e a Bob Alan Kevin Sarà ulteriormente strutturato Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, tool a.a. 2009/2010 John Progettazione del SW Partiamo dalle specifiche del problema da risolvere Determiniamo l’algoritmo – Si procede in modo top-down per raffinamenti successivi – Vengono individuati task che devono essere eseguiti Successivamente raffinati in sotto-task Ciascun task prende in input degli argomenti, ha un determinato compito da svolgere, fornisce un valore di ritorno Concetto di funzione Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Funzione Il programmatore può organizzare il codice in funzioni Ciascuna funzione svolge un task specifico (ad esempio calcolare ab) – il task deve essere chiaramente indicato nel nome della funzione (ad esempio potenza) – la funzione prenderà in input una serie di parametri (ad esempio a e b) – eseguirà il codice necessario per portare a compimento il task (as esempio calcolare ab) – restituirà un valore di ritorno a chi ha invocato la funzione (ab) tipo_del_valore_di_ritorno nome_funzione (tipo parametro1, …, tipo parametron) void se la funzione non restituisce nulla Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Funzione Le funzioni sono invocate tramite una chiamata a funzione nome_funzione (argomento1, …,argomenton) L’invocazione della funzione fa sì che la funzione esegua il suo compito (con i valori dei parametri specificati nella invocazione della funzione) e restituisca al chiamante il valore di ritorno. Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Vantaggio dell’uso delle funzioni Una organizzazione in funzioni rende più facile strutturare un programma complesso Lo stesso task può essere invocato più volte (magari con diversi valori dei parametri) durante l’esecuzione del programma Usando le funzioni dovremo scrivere il codice della funzione una volta sola, e semplicemente invocare la funzione tutte le volte che serve Riuso del codice Molte operazioni/task sono di interesse generale (ad esempio l’elevazione a potenza). Esistono quindi librerie standard che realizzano tali funzioni. In tal caso basta includere tali librerie (contenenti il codice della funzione) ed invocarla appropriatamente nel programma non occorre sempre reinventare la ruota Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Vantaggio dell’uso delle funzioni Modularità Se vogliamo modificare il modo in cui un task viene eseguito basta cambiare il codice della funzione relativa. La modifica è trasparente al resto del programma. Facilità di debugging Strutturare il programma in funzioni, ciascuna con un compito chiaro, semplifica il debugging e permette di isolare le funzioni in cui si verificano errori. Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Funzioni di libreria Un esempio: la libreria matematica #include <math.h> Funzione Descrizione Esempio sqrt(x) radice quadrata di x sqrt(900.0) restituisce 30.0 sqrt(900.0)30.0 exp(x) ex exp(1.0) 2.71 log(x) logaritmo di x in base e log(2.71)1 log10(x) logaritmo di x in base 10 log10(100.0)2 fabs(x) valore assoluto di x fabs(-5.0)5.0 ceil(x) parte intera superiore ceil (9.2)10 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Funzioni di libreria Un esempio: la libreria matematica #include <math.h> Funzione Descrizione Esempio floor(x) parte intera inferiore floor(9.2)9.0 pow(x,y) xy pow(2,7) 128 fmod(x,y) resto della divisione di x per y (con x e y reali) fmod(13.657,2.333) 1.992 sin(x) seno di x sin(0.0)0.0 cos(x) coseno di x cos(0.0)1.0 tan(x) tangente di x (x in radianti) tan(0.0)0.0 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Uso di funzioni #include <stdio.h> int quadrato (int); prototipo della funzione int main() la funzione riceve un valore intero e restituisce un valore intero { int x; /*stampa i quadrati dei primi 10 interi*/ for (x=1; x<=10; x++) { All’inizio del corpo della printf (“%d ”, quadrato(x)); funzione possono essere } Invocazionedefinite variabili locali printf(“\n”); (viene loro allocata memoria della funzione return 0; all’entrata nella funzione. Tale } memoria viene rilasciata quando parametro formale int quadrato (int y) { return y*y; } si restituisce il controllo al definizione di funzione chiamante). I parametri possono essere viste come variabili locali return restituisce il alla funzione in cui viene copiato corpo della all’entrata nella funzione il controllo al chiamante funzione Prof.ssa Chiara Petrioli -- Fondamenti di valore con cui la funzione fornendo un valore di programmazione, a.a. 2009/2010 viene invocata. ritorno Vediamo cosa succede in memoria parametro attuale dal main invochiamo printf (“%d ”, quadrato(x)); La variabile x vale 1 Si invoca la funzione quadrato Viene associata una locazione di memoria al parametro y della funzione. In questa locazione viene copiato il valore del parametro attuale (si parla di passaggio per valore dei parametri) Memoria 4357 1 … Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 y Vediamo cosa succede in memoria Viene quindi eseguito il corpo della funzione Si calcola y2 e si restituisce questo valore al chiamante Memoria restituisce 1 al chiamante (il main) 4357 int quadrato (int y) { return y*y; } 1 … Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 y La memoria allocata per il parametro y viene rilasciata Vediamo cosa succede in memoria Il valore 1 viene stampato printf (“%d ”, quadrato(x)); restituisce 1 Memoria restituisce 1 al chiamante (il main) 4357 int quadrato (int y) { return y*y; } ATTENZIONE:importante che restituisca un intero altrimenti errore 1 … Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 y Vediamo cosa succede in memoria parametro attuale dal main invochiamo printf (“%d ”, quadrato(x)); La variabile x vale 2 Si invoca la funzione quadrato Viene associata una locazione di memoria al parametro y della funzione. In questa locazione viene copiato il valore del parametro attuale (si parla di passaggio per valore dei parametri) Memoria 5200 2 … Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 y Vediamo cosa succede in memoria Viene quindi eseguito il corpo della funzione Si calcola y2 e si restituisce questo valore al chiamante Memoria restituisce 4 al chiamante (il main) 5200 int quadrato (int y) { return y*y; } 2 … Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 y La memoria allocata per il parametro y viene rilasciata Vediamo cosa succede in memoria Il valore 4 viene stampato printf (“%d ”, quadrato(x)); restituisce 4 Memoria restituisce 4 al chiamante (il main) 5200 int quadrato (int y) { return y*y; } ATTENZIONE:importante che restituisca un intero altrimenti errore 2 … Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 y Un esempio #include <stdio.h> int maximum (int, int, int); int main() { int number 1, number2, number 3; printf (“inserisci tre valori interi \n”); scanf(“%d%d%d”, &number1,&number2,&number3); printf(“il massimo è: %d \n”, maximum (number1,number2,number3)); return 0; } int maximum (int x, int y, int z) { int max=x; if (y>max) max=y; if (z >max) max=z; return max; } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Prototipo di una funzione Cosa succedei se un valore un parametrodei attuale con cui è Specifica tipi ed ildinumero parametri, invocata una funzione è di tipo diverso da quanto specificato ? l’ordine in cui tali parametri devono essere (ad esempio int maximum(int,int,int); double sqrt(double); forniti, il tipo del valore di ritorno cosa succede se si invoca su una variabile intera?) dice che la funzione maximum prende tre argomenti interi coercizione degli argomenti si forza al tipo opportuno e restituisce un valore di tipo intero Aiuta il compilatore ad (‘promosso’) individuare errori Il valore intero viene ‘convertito’ valore reale ildella valore a sqrt Se nel unacorrispettivo chiamata a funzione non riflettediilpassarne prototipo Una invocazione di prima funzione che non rispetta funzione (es. meno o piu’ argomenti, restituisce un tipo diverso, quanto indicato dal prototipo di funzione causa …) si ha un errore sintattico in fase di compilazione un errore sintattico in fase di compilazione a volte potete vedere il nome dei parametri-non solo il tipoindicato nel prototipo non serve, è una informazione ignorata dal compilatore tipo_valore_di_ritorno nome_funzione (tipo parametro1,…,tipo parametron); Se void significa che la funzione non restituisce valore Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Headers Ciascuna libreria standard ha un header che contiene i prototipi di tutte le funzioni della libreria l’ header contiene i prototipi delle funzioni, le definizioni di costanti e tipi di dato usati da tali funzioni #include <xxx.h> include questi header (proprocessore) Esempi di librerie standard stdio.h ctype.h string.h math.h libreria standard di I/O funzioni sui caratteri funzioni di manipolazione di stringhe funzioni matematiche Il codice delle funzioni di libreria viene quindi incluso nell’eseguibile dal linker Il programmatore può creare delle sue librerie in modo da riusare il codice di funzioni che ha scritto Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Chiamata per valore e per riferimento Nei linguaggi di programmazione esistono due modi di invocare una funzione Chiamata per valore – quando gli argomenti sono passati per valore si fa una copia del valore dei parametri attuali con cui la funzione viene invocata – Tale copia viene memorizzata nelle locazioni di memoria assegnate ai parametri formali in seguito alla chiamata della funzione – Modifiche effettuate sui valori memorizzati in tali locazioni non hanno impatto sulle variabili della funzione invocante Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Esempio #include <stdio.h> int quadrato (int); int main() { int x; /*stampa i quadrati dei primi 10 interi*/ for (x=1; x<=10; x++) { printf (“%d ”, quadrato(x)); } Una copia del valore di x (che vale 1) printf(“\n”); viene memorizzata nella locazione return 0; di memoria associata al parametro y } int quadrato (int y) { y=y*y; return y; } Viene modificato il valore di y NON subisce alcuna modifica il valore di x All’uscita dalla funzione la memoria allocata a y viene rilasciata.Non rimane Prof.ssatraccia Chiara Petrioli -- Fondamenti di delle modifiche fatte. Rimane solo il programmazione, a.a. 2009/2010 valore di ritorno restituito al chiamante Chiamata per valore e per riferimento Nei linguaggi di programmazione esistono due modi di invocare una funzione Chiamata per riferimento – consente di modificare il valore della variabile con cui viene invocata la funzione printf (“%d ”, quadrato(x)); Il C consente solo la chiamata di funzioni per valore Se fosse una chiamata per riferimento Si lavorerebbe direttamente su x Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Esercizio Si scriva un programma che calcoli il minimo di tre interi #include <stdio.h> int minimo (int,int,int); int main() { int x1,x2,x3; printf (“inserisci tre interi \n”); scanf (“%d %d %d”, &x1,&x2,&x3); printf(“il minimo dei tre valori e’ %d \n”, minimo(x1,x2,x3)); return 0; } int minimo (int y1, int y2, int y3) { int temp=y1; if (y2 < temp) Inserisci tre interi temp=y2; 4 if (y3 < temp) 6 temp=y3; 3 return temp; Prof.ssa Chiara Petrioli -- Fondamenti di tre valori è 3 Il minimo dei programmazione, a.a. 2009/2010 } Vediamo cosa succede in memoria Dal main invochiamo: printf(“il minimo dei tre valori e’ %d \n”, minimo(x1,x2,x3)); La variabile x1 vale 4, la variabile x2 vale 6, la variabile x3 vale 3 Si invoca la funzione minimo Viene associata una locazione di memoria a ciascuno dei parametri y1, y2, y3 della funzione. In queste locazioni vengono copiati i valori dei parametri attuali. Viene anche allocata una locazione di memoria per la variabile locale temp; Memoria temp … 4 y1 6 y2 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 3 y3 Vediamo cosa succede in memoria Viene quindi eseguito il corpo della funzione. La variabile temp contiene il minimo dei tre valori y1, y2, y3, ovvero il valore 3 Viene eseguito return temp che ritorna il controllo al main, con valore di ritorno pari a 3 restituisce 3 al chiamante (il main) Memoria int minimo (int y1, int y2, int y3) temp 3 { int temp=y1; y1 La memoria allocata if (y2 < temp) 4 per i parametri y1,y2, y3 temp=y2; e per temp viene if (y3 < temp) y2 rilasciata … 6 temp=y3; return temp; Prof.ssa Chiara Petrioli -- Fondamenti di } y3 programmazione,3 a.a. 2009/2010 Vediamo cosa succede in memoria Il valore 3 viene stampato printf(“il minimo dei tre valori e’ %d \n”, minimo(x1,x2,x3)); restituisce 3 int minimo (int y1, int y2, int y3) { int temp=y1; if (y2 < temp) temp=y2; if (y3 < temp) temp=y3; return temp; } Memoria 3 … restituisce 3 al chiamante (il main) y temp 4 y1 6 y2 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 3 y3 Esercizio Un intero è primo se è divisibile solo per 1 e se stesso Si scriva una funzione che determini se un numero è primo Si usi questa funzione in un programma che determini e stampi tutti i numeri primi tra 1 e 10.000 OSSERVAZIONE: sufficiente testare se l’intero x è divisibile o meno per i numeri da 1 a sqrt(x). Perché? Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Soluzione #include <stdio.h> #include <math.h> int primo (int); int main() { int i; /*stampa i numeri primi tra 1 e 10.000*/ for (i=1; i<=10000; i++) { if (primo (i)!=0) printf (“%d \n”, i); } return 0; } int primo (int y) { int x; for (x=2; x<=sqrt(y); x++) { if (y % x == 0) return 0; } Prof.ssa Chiara Petrioli -- Fondamenti di return 1; programmazione, a.a. 2009/2010 } Esercizio Un numero intero si dice perfetto se i suoi fattori (incluso 1 ma non il numero stesso) sommano al numero. Ad esempio 6 è un numero perfetto. I suoi fattori sono 1, 2 e 3: 1+2+3=6. Si scriva una funzione perfect che, dato un numero intero, determini se tale numero è perfetto. Si usi questa funzione per determinare e stampare tutti i numeri perfetti tra 1 e 1000. Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 #include <stdio.h> #include <math.h> Soluzione // Restituisce 1 se l’input e’un numero perfetto int perfect (int); int main() { int i; /*stampa i numeri perfetti tra 1 e 1.000*/ for (i=1; i<=1000; i++) { if (perfect (i)==1) printf (“%d \n”, i); } return 0; } int perfect (int n) { int tmp = n; int tot = 0; int d; for (d = 1; d < n; d++ ) if ( n % d == 0 ) tot += d; if ( tot == n ) return 1; else return 0; } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Gioco dei dadi Il giocatore tira due dadi. Si calcola la somma x dei valori della facce superiori dei due dadi. Se tale somma è 7 o 11 il giocatore vince. Se è 2, 3 o 12 il giocatore perde. Altrimenti x è il punto del giocatore che deve continuare a giocare fino a quando non si ottiene un valore uguale al proprio punto. Se i dadi danno 7 il giocatore perde. Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Emulazione del lancio dei dadi Non ha argomenti Produce in output il risultato di un tiro di dadi int rollDice ( ) { int d1,d2; d1=1+(rand() % 6); d2=1+(rand() % 6); returnNumero (d1+d2); pseudocasuale tra 0 e 5 } (scaling) Funzione della stdlib.h che produce un numero pseudocasuale tra 0 e RAND_MAX, con RAND_MAX almeno 32767 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Soluzione tipo enumerato: insieme di costanti intere #include <stdio.h> #include <stdlib.h> funzione rand, srand rappresentate da identificatori CONTINUA ha associato il valore 0 #include <time.h> VINTO il valore 1 enum STATO { CONTINUA, VINTO, PERSO}; PERSO il valore 2 int rollDice (); int main() { int somma, mio_punto; enum STATO stato_del_gioco; /*stato_del_gioco è una variabile che può assumere valore CONTINUA, VINTO o PERSO*/ srand (time (NULL)); Ritorna Inizializza il tempo il seme somma=rollDice(); corrente del generatore in secondi switch(somma) da pseudocasuale un istante dato …….. (funzione della } libreria time.h) Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 switch(somma) { case 7: case 11: stato_del_gioco=VINTO; break; Soluzione case 2: case 3: case 12: stato_del_gioco=PERSO; break; default: stato_del_gioco=CONTINUA; mio_punto=somma; break; } while (stato_del_gioco == CONTINUA) { somma=rollDice(); if (somma ==mio_punto) stato_del_gioco=VINTO; else if (somma == 7) stato_del_gioco=PERSO; } if (stato_del_gioco == VINTO) printf(“VINTO \n”); } Se il gioco non si decide al primo tiro di dadi… Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Vettori Un vettore è una struttura dati contiene n elementi dello stesso tipo memorizzati in celle successive di memoria e’ possibile accedere in tempo costante ad un elemento specificando il suo indice – se vett è il nome del vettore di interi – vett[0] è il valore del primo elemento del vettore – vett[i] è il valore dell’ i+1 –esimo elemento del vettore L’indice dell’elemento dell’array può anche essere specificato indice del davettore una espressione Ad esempio, se a=5 e b=6 c[a+b] +=2; fa sì che si aggiunga due all’elemento con indice 11 (il 12esimo elemento del vettore c) Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Definizione di un array Specifica il nome del vettore, il tipo dei suoi elementi ed il numero dei suoi elementi int c[12]; alloca memoria (12 celle consecutive) per un vettore di nome c costituito da 12 interi. memoria 5 -1 8 10 c[0] c[1] c[11] Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 c[1] è uguale a -1 c[11] uguale a 10 x=c[11]/2; assegna a x il valore 5 Esempio Definizione di un array Inizializzazione di un array Uso di un array Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Esempio #include <stdio.h> int main() { int a[10]; /* definisce un array di 10 interi, di nome a*/ int i,x; for (i=0; i<10; i++) { printf (“inserisci valore \n”); scanf(“%d”,&x); 5 -1 8 3 4 6 2 -3 6 10 a[i]=x; } a[9] for (i=0; i<10; a[0] i++) a[1] { 5 printf (“%d01%d \n”, i, a[i]); -1 } 28 …Prof.ssa Chiara Petrioli -- Fondamenti di } programmazione, a.a. 2009/2010 9 10 Esempio #include <stdio.h> int main() Definizione e inizializzazione { int a[10]= {5,-1,8,3,4,6,2,-3,6,10}; int i; Se non sono specificati tutti gli elementi quelli restanti sono for (i=0; i<10; i++) messi a 0 { printf (“%d %d \n”, i, a[i]); } } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Esercizio Si scriva un programma che prenda da input gli elementi di un array di interi, calcoli e stampi la somma degli elementi dell’array. Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Soluzione #include <stdio.h> #define DIM_ARRAY 10 int main() { int a[DIM_ARRAY]; int i, somma; somma = 0; for (i=0; i< DIM_ARRAY; i++) { printf (“inserisci elemento array \n”); scanf (“%d”, &a[i]); } for (i=0; i< DIM_ARRAY; i++) { somma +=a[i]; } printf (“somma degli elementi dell’array: %d\n”, somma); } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Esercizio Si scriva un programma che calcoli l’istogramma dei voti degli studenti in un appello di esame Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Soluzione #include <stdio.h> #define INTERVALLO_VOTI 30 #define NUM_VALORI 100 int main() { int i,j,n; int frequenza [INTERVALLO_VOTI]= {0}; int voti[NUM_VALORI]; Definizione delle variabili printf (“inserisci numero di voti delle persone che hanno sostenuto l’appello (al massimo 100)\n”); scanf (“%d”, &n); /*in n la dimensione effettiva dell’array voti, deve essere <= NUM_VALORI*/ for (i=0; i<n; i++) { printf (“inserisci elemento array \n”); scanf (“%d”, &voti[i]); ++frequenza[voti[i]]; } Inizializzazione del vettore printf (“Istogramma \d”); for (i=0; i<INTERVALLO_VOTI; i++) { printf (“%d ”, i+1); for (j=0; i<frequenza[j]; j++) printf(“ * ”); Prof.ssa Chiara Petrioli -- Fondamenti di printf(“\n”); programmazione, a.a. 2009/2010 } Soluzione #include <stdio.h> #define INTERVALLO_VOTI 30 #define NUM_VALORI 100 int main() { int i,j,n; int frequenza [INTERVALLO_VOTI]= {0}; int voti[NUM_VALORI]; Definizione delle variabili Inserisci il numero di voti delle persone che hanno sostenuto l’appello (al (“inserisci massimo 100) di voti delle persone che hanno sostenuto l’appello (al massimo 100)\n”); printf numero scanf 10 (“%d”, &n); /*in n la dimensione effettiva dell’array voti, deve essere <= NUM_VALORI*/ 28 for (i=0; i<n; i++) { 18 25 printf (“inserisci elemento array \n”); Inizializzazione del vettore scanf (“%d”, &voti[i]); 22 ++frequenza[voti[i]]; 18 VOTI INSERITI } 30 (“Istogramma \d”); printf for21 (i=0; i<INTERVALLO_VOTI; i++) { 22 printf (“%d ”, i+1); 25 for (j=0; i<frequenza[j]; j++) printf(“ * ”); 25 … printf(“\n”); } } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Soluzione #include <stdio.h> #define INTERVALLO_VOTI 30 #define NUM_VALORI 100 int main() Istogramma { int 1 i,j,n; int frequenza [INTERVALLO_VOTI]= {0}; 2 int voti[NUM_VALORI]; Definizione delle variabili … printf 18 * *(“inserisci numero di voti delle persone che hanno sostenuto l’appello (al massimo 100)\n”); scanf 19 (“%d”, &n); /*in n la dimensione effettiva dell’array voti, deve essere <= NUM_VALORI*/ 20 (i=0; i<n; i++) for {21 * 22 * *printf (“inserisci elemento array \n”); del vettore Specifica ilInizializzazione numero scanf (“%d”, &voti[i]); 23 ++frequenza[voti[i]]; di studenti che hanno 24 } conseguito un determinato printf \d”); 25 * *(“Istogramma * voto for 26 (i=0; i<INTERVALLO_VOTI; i++) { 27 printf (“%d ”, i+1); 28 * for (j=0; i<frequenza[j]; j++) printf(“ * ”); 29 printf(“\n”); 30 * } } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Stringhe Una stringa è una sequenza di caratteri che termina con ‘\0’. Il numero celle Una stringa può quindi essere vista comediun ALTERNATIVA PER da allocare al vettore L’INIZIALIZZAZIONE vettore di caratteri che termina con undecisa carattere viene in base char string1[ ]= predefinito di fine stringa. alla dimensione della {‘a’,’l’,’u’,’n’,’n’,’i’,’\0’} stringa con cui si inizializza il vettore Inizializzazione char string1[30] = “alunni”; a l u n n Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 i \0 Stringhe Il vettore deve essere sufficientemente lungo da contenere la stringa inserita Legge caratteri da Definizione char string2 [20]; e inizializzazione: scanf(“%s”, string2); input fino al primo spazio e li inserisce in string2 aggiungendo uno \0 Stampa di una stringa printf (“%s \n”, string2); a l Stampa ciò che è contenuto in string2 fino a \0 (escluso) u n n i \0 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Come si passa un vettore ad una funzione int v[50]; nome del vettore int somma_vett(int vett[ ],int n) { int i; int somma=0; for (i=0; i<n; i++) somma +=vett[i]; return somma; Restituisce la } Numero di elementi validi che si vogliono considerare somma degli elementi di un vettore Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Chiamata alla funzione x=somma_vett(v,num); Come si passa un vettore ad una funzione I vettori di fatto vengono passati per riferimento vett &vett[0] Il nome del vettore è di fatto l’indirizzosono della prima equivalenti locazione di memoria allocata al vettore Nel parametro attuale si copia tale indirizzo. Nella funzione si lavora quindi sulle celle allocate al vettore nella funzione chiamante. Modifiche fatte ai valori degli elementi del vettore permangono all’uscita dalla funzione Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Un esempio… Si scriva una funzione che data una stringa sostituisca tutte le cifre che compaiono nella stringa con il carattere ‘*’. char str2[DIM_STRINGA]; inizializzazione stringa nella funzione chiamante All’inizio del file prototipo di questa funzione I singoli elementi del vettore vengono La funzione non invece passati per restituisce valori valore void modifica_stringa(int str[ ]); { int i=0; while (str [i] != ‘\0’) { if (str[ i] >= ‘0’ && str[i] <= ‘9’) str indica la str[ i] = ‘*’; I vettori sono passati locazione di i=i+1; per riferimento memoria del Importante sempre Copiare interi vettori primo elemento mettere il controllo } (che potrebbe significare del vettore sul carattere } Molti dati) ad ogni chiamata Verifica se str[i]diIècaratteri fine stringa sono a funzione può essere una cifra rappresentatiProf.ssa Petrioli -- Fondamenti di con Chiara molto inefficiente programmazione, a.a. 2009/2010 interi – codice ASCII Cosa succede in memoria… Chiamata a funzione modifica_stringa(str2); str2 è l’indirizzo di memoria in cui si memorizza str2[0] 1415 1415 a l 1 a \0 str2 è stata definita ed Inzializzata nella funzione chiamante (che in questo caso è il main()) str2 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Cosa succede in memoria… Si entra nella funzione Viene allocata memoria per la variabile locale intera i Viene copiato l’indirizzo di memoria in cui è memorizzato il primo elemento del vettore 1415 a l 1 a \0 str2 è stata definita ed Inizializzata nella funzione chiamante (che in questo caso è il main()) str2 i 2500 Allocata memoria all’entrata nella funzione Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Cosa succede in memoria… Si comincia ad eseguire il corpo della void modifica_stringa(int str[ ]); funzione { str[0] è il primo elemento del vettore str2; vale ‘a’ È quindi da ‘\0’Quindi str[0] nondiverso è una cifra. Si incrementa il valore di i e si ritorna all’inizio del Ciclo. 1415 a l 1 a \0} int i=0; while (str [i] != ‘\0’) { if (str[ i] >= ‘0’ && str[i] <= ‘9’) str[ i] = ‘*’; i=i+1; str2 è stata definita ed Inzializzata nella funzione } chiamante (che in questo caso è il main()) str2 1 0 2500 i str Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Cosa succede in memoria… Si comincia ad eseguire il corpo della void modifica_stringa(int str[ ]); funzione { str[1] è il secondo elemento del vettore str2; vale ‘l’ È quindi da ‘\0’Quindi str[1] nondiverso è una cifra. Si incrementa il valore di i e si ritorna all’inizio del Ciclo. 1415 a l 1 a \0} int i=0; while (str [i] != ‘\0’) { if (str[ i] >= ‘0’ && str[i] <= ‘9’) str[ i] = ‘*’; i=i+1; str2 è stata definita ed Inzializzata nella funzione } chiamante (che in questo caso è il main()) str2 21 2500 i str Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Cosa succede in memoria… Si comincia ad eseguire il corpo della void modifica_stringa(int str[ ]); funzione { str[2] è il terzo elemento del vettore str2; vale ‘1’ È quindi diverso da ‘\0’ str[2] è una cifra. str[2]=‘*’ Si incrementa il valore di i e si ritorna all’inizio del Ciclo. 1415 a l *1 a \0} int i=0; while (str [i] != ‘\0’) { if (str[ i] >= ‘0’ && str[i] <= ‘9’) str[ i] = ‘*’; i=i+1; str2 è stata definita ed Inzializzata nella funzione } chiamante (che in questo caso è il main()) str2 32 2500 i str Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Cosa succede in memoria… Si comincia ad eseguire il corpo della void modifica_stringa(int str[ ]); funzione { str[3] è il quarto elemento del vettore str2; vale ‘a’ È quindi diverso da ‘\0’ str[3] non è una cifra. Si incrementa il valore di i e si ritorna all’inizio del Ciclo. 1415 a l *1 a \0} int i=0; while (str [i] != ‘\0’) { if (str[ i] >= ‘0’ && str[i] <= ‘9’) str[ i] = ‘*’; i=i+1; str2 è stata definita ed Inzializzata nella funzione } chiamante (che in questo caso è il main()) str2 4 3 2500 i str Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Cosa succede in memoria… Si comincia ad eseguire il corpo della void modifica_stringa(int str[ ]); funzione { str[4] è il quinto elemento del vettore str2; vale ‘\0’ Condizione di treminazione del ciclo si esce dal ciclo e dalla funzione 1415 a l *1 a \0 } int i=0; while (str [i] != ‘\0’) { if (str[ i] >= ‘0’ && str[i] <= ‘9’) str[ i] = ‘*’; i=i+1; str2 è stata definita ed Inzializzata nella funzione } Rimangono le modifiche chiamante (che in questo Effettuate su str2 caso è il main()) str2 4 3 2500 i str La memoria allocata per la variabili locali alla funzione e per i parametri viene rilasciata Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Un altro esempio #include <stdio.h> #define SIZE 5 void modifyArray (int b[], int size); void modifyElement (int e); int main() { int a[SIZE]={0,1,2,3,4}; int i; printf(“effetti del passaggio ‘per riferimento’ degli array \n. Valori del vettore originale \n\n”); for (i=0;i<SIZE;i++) { printf(“%d ”, a[i]); } modifyArray(a,SIZE); printf(“\n Nuovi valori degli elementi dell’array: \n\n”); for (i=0;i<SIZE;i++) { printf(“%d ”, a[i]); } printf(“\n\n effetto del passaggio di un elemento del vettore ‘per valore’. il valore di a[3] è: %d”, a[3]); modifyElement(a[3]); printf(“il valore di a[3] ora è: %d”,a[3]); return 0; } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Un altro esempio void modifyArray (int b[ ], int size) { int j; for (j=0;j<size; j++){ b[j]*=2; } return; } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Un altro esempio void modifyElement (int e) { e*=2; printf(“valore elemento modificato: %d”,e); return; } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Un altro esempio #include <stdio.h> #define SIZE 5 void modifyArray (int b[], int size); void modifyElement (int e); int main() { Valori del vettore originale… int a[SIZE]={0,1,2,3,4}; 01234 int i; Nuovidegli valori… printf(“effetti del passaggio ‘per riferimento’ array \n. 02468 Valori del vettore originale \n\n”); for (i=0;i<SIZE;i++) { passaggio degli elementi del vettore per valore. Effetto del printf(“%d”, a[i]); Il valore di a[3] è: 6 } Valore elemento modificato: 12 modifyArray(a,SIZE); Il valore di a[3] ora è: 6 printf(“\n Nuovi valori degli elementi dell’array: \n\n”); Siamo all’interno for (i=0;i<SIZE;i++) { della funzione printf(“%d”, a[i]); modifyElement } printf(“\n\n effetto del passaggio di un elemento del vettore ‘per valore’. il valore di a[3] è: %d”, a[3]); modifyElement(a[3]); printf(“il valore di a[3] ora è: %d”,a[3]); return 0; Prof.ssa Chiara Petrioli -- Fondamenti di } programmazione, a.a. 2009/2010 Qualificatore const Consente di imporre che un array non possa essere modificato dalla funzione che lavora su di esso Un esempio… Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Esempio di utilizzo del qualificatore const #include <stdio.h> void tryToModifyArray(const int b[ ]); int main() { int a[ ]={10,20,30}; tryToModifyArray(a); printf(“%d%d%d\n”,a[0],a[1],a[2]); Se si prova a modificare return 0; Compiling… il contenuto di un elemento } dell’array Error: l-value specifies const object avviene un errore void tryToModifyArray(const int b[ ])di compilazione in fase { b[0]/=2; b[1]/=2; Prof.ssa Chiara Petrioli -- Fondamenti di b[2]/=2; programmazione, a.a. 2009/2010 Alcune operazioni su vettori Ricerca di un elemento (in vettori non ordinati e ordinati) Ordinamento di un vettore Calcolo della media, mediana degli elementi di un vettore Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento di vettori Dato un vettore di n interi vett riorganizzare i valori memorizzati nei suoi elementi in modo che se i <j, vetti[i]<= vetti[j] …ovvero in modo tale che gli elementi del vettore siano ordinati in modo crescente. Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Pseudocodice Inizializza il vettore di interi con i valori dati; inizializza una variabile contatore i a 0. Esegui n-1 iterazioni (n num. elementi del vettore). Per ogni iterazione: Considera la posizione j del vettore (j=1,…,n-1) – Se l’elemento in posizione j è maggiore dell’elemento in posizione j+1 scambia i due elementi Vedremo che ogni iterazione è in grado di assicurare che almeno un ulteriore elemento sarà inserito nell’ordine corretto, progressivamente aumentando il numero di elementi ordinati e portando in n-1 iterazioni al pieno ordinamento del vettore Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Un esempio Prima iterazione Il vettore NON è ordinato alla fine della prima iterazione i 3 i 4 1 i 41 i 8 5 i 6 85 86 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Idea: Dopo la prima iterazione il valore più grande si trova in fondo al vettore. Perché? Se il valore più grande era in posizione j, allora il confronto tra j e j+1 lo sposta in posizione j+1. Il confronto tra il valore della posizione j+1 e della posizione j+2 lo sposta in posizione j+2, e così via finisce nella prima iterazione in fondo al vettore Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Un esempio Seconda iterazione i 31 i 31 i 4 i 5 Il vettore NON è ordinato alla fine della seconda iterazione MA il secondo elemento più grande È in penultima posizione. L’elemento più grande in ultima posizione. Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 6 8 Ordinamento dei vettori BubbleSort Perché? Se il secondo valore più grande era in posizione j, allora il confronto tra j e j+1 lo sposta in posizione j+1 (l’unico valore più Grande è in fondo al vettore). Il confronto tra il valore della posizione j+1 e della posizione j+2 lo sposta in posizione j+2, e così via. Non può essere messo nell’ultima posizione dove c’è un valore più grande di lui finisce nella penultima posizione del vettore Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Un esempio Terza iterazione i 1 i 3 i 4 5 IN QUESTO caso il vettore è ordinato alla fine della seconda iterazione Il terzo elemento più grande È in terzultima posizione. Si procede comunque con Prof.ssa Chiara Petrioli -- Fondamenti di altre due iterazioni in cui non programmazione, a.a. 2009/2010 si cambia nulla nel vettore. 6 8 Codice del BubbleSort #include <stdio.h> #define SIZE 10 int main() { int a[SIZE]={2,6,4,8,10,12,89,68,45,37}; int i,j,hold; printf(“Ordinamento originale del vettore \n”); for (i=0; i<SIZE;i++) { printf(“%d ”, a[i]); } for (i=0;i<SIZE-1;i++) { for (j=0;j<SIZE-1;j++) { if (a[j])>a[j+1]) { hold=a[j]; a[j]=a[j+1]; a[j+1]=hold; } } } Prof.ssa Chiara Petrioli -- Fondamenti di a.a. 2009/2010 printf (“\n vettore ordinato \n”); /*stampa, come sopra delprogrammazione, vettore*/ …… } Dimostrazione formale di correttezza (per induzione) Vogliamo dimostrare che il BubbleSort Termina sempre Produce un vettore ordinato Terminazione banale. Numero di iterazioni eseguite dal for annidato finite. SOLO una cattiva implementazione può portare a esecuzioni infinite , NON l’ALGORITMO Vogliamo quindi dimostrare che dopo k iterazioni le ultime k posizioni del vettore contengono i k elementi più grandi, ordinati in ordine crescente SE VERO Dopo le n iterazioni eseguite dall’algoritmo il vettore contiene gli n elementi ordinati in ordine crescente Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Dimostrazione formale di correttezza (per induzione) Passo base Affermazione vera per k=1 Dimostrato 5 slide fa Passo induttivo Se vero per ogni k<=h, k<n, dimostriamo che sia vero per k <=h+1 Claim: Dopo h+1 iterazioni le ultime h+1 posizioni del vettore contengono gli h+1 elementi più grandi, ordinati in ordine crescente Per ipotesi induttiva quando si comincia ad eseguire la h+1 iterazione le ultime h posizioni contengono gli h elementi più grandi ordinati in ordine crescente. Tali elementi non verranno spostati. L’applicazione delle regole dell’algoritmo non consente che elementi piu’ piccoli possano essere spostati in posizioni di indice maggiore in cui sono memorizzati elementi più grandi. Nella h+1 esima iterazione l’ordinamento relativo degli h elementi più grandi (già ordinati in ordine crescente) non subisce modifiche. Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Dimostrazione formale di correttezza (per induzione) Passo induttivo – Quello che succede è che l’h+1 esimo elemento più grande viene spostato in posizione n-1-h Le posizioni n-1, n-h contengono gli h elementi più grandi Se l’h+1 esimo elemento più grande si trova in posizione j, j <= n-1-h, e tutte le posizioni j,…,n-1-h conterranno elementi più piccoli quindi avverranno switch tra la posizione j e j+1, j+2 e j+3, etc. fino a portare l’h+1 esimo elemento più grande in posizione n-1-h. Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Codice del BubbleSort #include <stdio.h> #define SIZE 10 int main() { int a[SIZE]={2,6,4,8,10,12,89,68,45,37}; int i,j,hold; printf(“Ordinamento originale del vettore \n”); for (i=0; i<SIZE;i++) { Se gli elementi dalla posizione printf(“%d ”, a[i]); 1 alla n-1 contengono gli n-1 elementi } piu’ grandi e sono ordinati in ordine for (i=0;i<SIZE-1;i++) crescente ALLORA tutti gli elementi { for (j=0;j<SIZE-1;j++) del vettore sono ordinati { if (a[j])>a[j+1]) Si lavora su j e j+1. Questa { condizione impone che si considerino hold=a[j]; solo elementi validi del vettore (non si a[j]=a[j+1]; a[j+1]=hold; eccede mai la sua dimensione) } } Si potrebbe ottimizzare considerando ogni volta solo i primi n-i elementi del vettore } printf (“\n vettore ordinato \n”); /*stampa, come che sopraseguono del vettore*/ (quelli sono già ordinati)… …… } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Caso peggiore Vediamo quale è il caso in cui ordinare il vettore comporta l’esecuzione di un numero maggiore di istruzioni un tempo di calcolo maggiore (complessità dell’algoritmo BubbleSort) Il caso in cui gli elementi sono ordinati in ordine decrescente..vediamo cosa succede in questo caso Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Un esempio Prima iterazione Il vettore NON è ordinato alla fine della prima iterazione i 6 5 i 65 4 i 64 3 i 2 63 i 62 1 61 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Un esempio Seconda iterazione 5 4 i i i i Il vettore NON è ordinato alla fine della seconda iterazione 54 3 53 2 52 1 51 6 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Un esempio Terza iterazione i 4 3 i 43 2 i 42 1 41 Il vettore NON è ordinato alla fine della terza iterazione 5 6 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Un esempio Quarta iterazione i 3 2 i 32 1 31 4 Il vettore NON è ordinato alla fine della quarta iterazione 5 6 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort Un esempio Quinta iterazione i 21 1 2 3 4 Il vettore NON è ordinato alla fine della quinta iterazione 5 6 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ordinamento dei vettori BubbleSort 1 n-1 iterazioni per ordinare i nodi In ciascuna iterazione vengono esaminati gli elementi del vettore e se un elemento e il successivo non sono in ordine crescente viene effettuato uno scambio c*n*n istruzioni nel caso peggiore Algoritmo di complessità O(n2) Data una funzione g(n) appartengono all’insieme O(g(n)) quelle funzioni f(n) tali che esistano due costanti intere positiveProf.ssa c e n0 tali che Chiara Petrioli -- Fondamenti di 0<=f(n)<=c*g(n) per tutti gli n>=n0 a.a. 2009/2010 programmazione, 2 3 4 5 6 Ricerca di un elemento in un vettore Abbiamo già visto il caso in cui il vettore non è ordinato – può essere necessario scandire l’intero vettore per sapere se l’elemento è presente o meno nel vettore Complessità O(n) – si può ricercare più efficacemente un elemento nel vettore se tale vettore è ordinato? Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Ricerca di un elemento in un vettore ordinato (ricerca binaria) A ogni passo elimina la metà degli elementi dell’array dall’insiemeKey di =elementi da 4 scandagliare Si confronta la chiave con l’lemento intermedio dell’array 1 3 5 6 8 9 10 12 – se la chiave è più grande bisognerà esaminare solo la metà destra dell’array – se la chiave è più piccola bisognerà esaminare solo la metà sinistra dell’array – se la chiave è uguale all’elemento cercato allora La chiave NON è presente nel vettore ! abbiamo trovato l’elemento! Si procede fino a quando o si è trovato l’elemento oppure non ci sono più elementi Prof.ssa Chiara Petrioli -- Fondamenti di da scandagliare programmazione, a.a. 2009/2010 Ricerca binaria int ricerca_binaria (const int b[ ], int key, int low, int high) { /*pre: low e high indici tra 0 e n-1; vettore ordinato post: dato un vettore ordinato di interi ed un intero int middle; key verifica se key è contenuto nel vettore */ int found = 0; while ((low <= high) && (found==0)) { middle = (low+ high)/2; if (key == b[middle]) found=1; else if (key < b[middle]) high=middle-1; else low=middle +1; } return found; Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 } Complessità della ricerca binaria Se il numero di elementi del vettore è n Prima iterazione: Se il vettore è di – n posizioni da scandagliare Seconda iterazione – <=n/2 posizioni da scandagliare Terza iterazione – <= n/4 posizioni da scandagliare 1048576 elementi -se il vettore non è ordinato possiamo dover eseguire c* 1048576 istruzioni per trovare l’elemento -se il vettore è ordinato si riducono a c1*20 istruzioni In log (n) iterazioni l’algoritmo termina complessità O(log n) Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Correttezza dell’algoritmo di ricerca binaria Vediamo un secondo approccio di dimostrazione – Dimostrazione per assurdo Scriviamo la tesi che vogliamo dimostrare Es. l’algoritmo di ricerca binaria, applicato ad un vettore ordinato, con low =0, high= dimensione del vettore -1, termina sempre restituendo un valore che è 0 se la chiave non è presente nel vettore e 1 se la chiave è presente nel vettore. Supponiamo per assurdo che esista un caso in cui la tesi non è verificata Es. in cui l’algoritmo restituisce un valore non corretto. Facciamo vedere che questo porta ad una contraddizione con le ipotesi di lavoro Es. non è possibile che l’algoritmo restituisca un valore non corretto A MENO che il vettore non sia ordinato (che è una ipotesi invece del nostro claim) Prof.ssa Chiara Petrioli -- Fondamenti di Per vettori ordinati è veroprogrammazione, che l’algoritmo restituisce valore corretto (CVD) a.a. 2009/2010 Lemma L’algoritmo di ricerca binaria termina sempre restituendo un valore booleano Numero limitato di iterazioni del ciclo Ogni volta che si entra nel ciclo while ((low <= high) && (found==0)) while ((low <= high) && (found==0)) { { middle = (low+ high)/2; middle = (low+ high)/2; if (key == b[middle]) if (key == b[middle]) found=1; Quando si esce dal ciclo si esegue else if (keyfound=1; < b[middle]) else if (key < b[middle]) found; high=middle-1; oppure l’intervalloreturn da high=middle-1; il controllo al chiamanteelse e scandagliare vieneRitornando ridotto else low=middle +1; (nel qual caso in alRestituendo massimo un valore booleano low=middle +1; (1 per VERO, 0 per FALSO) } log(n) iterazioni avremo che } high<low non avendo più Prof.ssa Chiara Petrioli -- Fondamenti di elementi da scandagliare e programmazione, a.a. 2009/2010 o found viene messo a 1 (in questo caso found non può essere successivamente rimesso a 0 si esce dal ciclo) Correttezza della ricerca binaria Dato un vettore ordinato, low==0, high==n-1 (con dimensione del vettore) e dato un intero key ricerca_binaria verifica se key è presente o meno nel vettore – restituisce 0 se key non è presente – 1 altrimenti Terminazione già dimostrata Inoltre osserviamo che l’algoritmo opera sempre su indici validi del vettore. Si parte con low=0, high=n-1 (indici validi).high viene solo diminuito, Prof.ssa Chiara -- Fondamenti di low solo aumentato. Non appena lowPetrioli > high la funzione termina. programmazione, a.a. 2009/2010 Correttezza della ricerca binaria Dato un vettore ordinato, low==0, high==n-1 (con dimensione del vettore) e dato un intero key ricerca_binaria verifica se key è presente o meno nel vettore – restituisce 0 se key non è presente – 1 altrimenti Supponiamo PER ASSURDO che esista un vettore ordinato vett, ed una chiave k, tale che ricerca_binaria produca un risultato non corretto – caso A) k compare in vett ma l’algoritmo di ricerca binaria restituisce 0 (FALSO) – Caso B) k non compare in vett ma l’algoritmo di ricerca binaria restituisce 1 (VERO) Prof.ssa Chiara Petrioli -- Fondamenti di Vedremo che entrambi questi due casi NON possono verificarsi. Infatti il programmazione, a.a. 2009/2010 loro verificarsi porta a delle CONTRADDIZIONI. Correttezza della ricerca binaria Supponiamo per assurdo che – Caso B) k non compare in vett ma l’algoritmo di ricerca binaria restituisce 1 (VERO) Osserviamo che l’algoritmo restituisce il valore della variabile found. found viene messo a 1 soltanto se si esegue if (k == vett[middle]) found=1; k compare tra gli elementi del vettore CONTRADDIZIONE Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Correttezza della ricerca binaria Supponiamo per assurdo che caso A) k compare in vett ma l’algoritmo di ricerca binaria restituisce 0 (FALSO). Se found viene messa a 1 (VERO) non può essere rimessa a 0 (FALSO) se i è l’indice in cui compare il valore k tale posizione non è mai esaminata altrimenti avremmo eseguito if (k == vett[middle]) found=1; e restituito 1 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Correttezza della ricerca binaria Questo significa che usciamo dal ciclo (low > high) senza mai aver esaminato l’elemento in posizione i Originariamente tutti gli elementi del vettore erano da esaminare L’osservazione precedente significa che ad una determinata iterazione abbiamo tolto dall’insieme degli elementi da scandagliare l’elemento in posizione i…sia h tale iterazione Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Correttezza della ricerca binaria Nell’h-esima iterazione possono succedere tre cose (in base al codice dell’algoritmo) Può essere che k == vett[middle] CONTRADDIZIONE found=1; Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Correttezza della ricerca binaria Nell’h-esima iterazione possono succedere tre cose (in base al codice dell’algoritmo) Può essere che k < vett[middle] high =middle-1; Per l’ipotesi che durante questa iterazione l’elemento in posizione i venga escluso da quelli da scandagliare i > middle. Ma allora k<vett[middle] è in posizione precedente ad un elemento con valore k Il vettore non è ordinato in ordine crescente Prof.ssa Chiara Petrioli -- Fondamenti di CONTRADDIZIONE programmazione, a.a. 2009/2010 Correttezza della ricerca binaria Nell’h-esima iterazione possono succedere tre cose (in base al codice dell’algoritmo) Può essere che k > vett[middle] low =middle+1; Per l’ipotesi che durante questa iterazione l’elemento in posizione i venga escluso da quelli L’ipotesi che il claim non sia vero porta a contraddizioni con le da scandagliare i < middle. Ma allora Ipotesi di lavoro Il claim è corretto k>vett[middle] è in posizione successiva ad un elemento con valore k Il vettore non è ordinato in ordine crescente Prof.ssa Chiara Petrioli -- Fondamenti di CONTRADDIZIONE programmazione, a.a. 2009/2010 Calcolo della media, mediana in un vettore Si scriva una funzione che dati 100 dati forniti da input e memorizzati in un vettore calcoli la media e la mediana di tali valori – Media: somma dei valori del vettore / numero degli elementi del vettore – Mediana: valore intermedio una volta ordinato il vettore Se il vettore ha 8 elementi con valori crescenti s1,s2,s3,…, s8 la mediana è il valore s4 Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Soluzione void median (int answer[ ], int n) { bubblesort (answer,n); printf (“il valore della mediana e’ %d \n”, answer[n/2]); } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Soluzione #include <stdio.h> #define SIZE 100 void mean (const int answer [ ], int n); void median (int answer [ ], int n); void bubblesort (int answer [ ], int n); Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Soluzione int main () { int dati [SIZE]; int i; for (i=0; i<SIZE; i++) { printf (“inserisci valore \n”); scanf(“%d”, &dati[i]); } mean (dati,SIZE); median (dati, SIZE); } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010 Soluzione void mean (const int answer[ ], int n) { int total, j; total=0; for (j=0; j<n; j++) total += answer[j]; printf (“il valore della media e’ %f \n”, (float) total/n); } Prof.ssa Chiara Petrioli -- Fondamenti di programmazione, a.a. 2009/2010