Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- fisica:informatica:201415:esercitazioni:esercitazione7 [22/01/2015 alle 09:22 (10 anni fa)] – creata Susanna Pelagatti
+++ fisica:informatica:201415:esercitazioni:esercitazione7 [13/04/2015 alle 12:42 (10 anni fa)] (versione attuale) – [Esercizio 8: Algoritmi di ordinamento su Array] Susanna Pelagatti
@@ Linea 1: / Linea 1: @@
-====== Esercitazione: Array ======
+====== Esercitazione: Array e puntatori ======
-===== Esercizio 1: Media =====
+===== Esercizio 1: Funzione swap =====
-Scrivere un programma C che legge da standard input 5 valori reali, li memorizza in un array e calcola la somma e la media dei valori letti.
+Scrivere una funzione di prototipo
+<code>
+void swap (int *a, int*b);
+</code>
+che ha l'effetto di scambiare i valori di due variabili, ad esempio:
+<code>
+int a=5;
+int b=63;
+swap(&a,&b);
+printf("a = %d, b = %d \n", a, b);
+....
+</code>
+deve stampare
+<code>
+a = 63, b = 5
+</code>
+Sarebbe stato possibile ottenere lo stesso effetto utilizzando una funzione di prototipo
+<code>
+void swap (int a, int b);
+</code>
+? Perche' ?
-Prima di terminare, il programma stampa la media ed i valori letti dall'ultimo al primo.
+===== Esercizio 2: Somma e prodotto di matrici =====
+Scrivere un programma C costituito da un ''main()'' che legge da standard input due matrici quadrate, le somma, calcola il prodotto e stampa i risultati sullo standard output.
+===== Esercizio 3: Ricerca in un array =====
+Scrivere una funzione di prototipo
+<code c>
+int cerca (int * vec, int lung, int x);
+</code>
+che cerca se l'elemento ''x'' e' presente nell'array ''vec'' di lung elementi e restituisce 1 se lo trova e 0 se non lo trova.
+Verificare la correttezza della funzione utilizzando un opportuno ''main()''.
+===== Esercizio 4: Generazione di numero casuali in C =====
+In alcuni casi e' importante riuscire a generare casualmente dei valori all'intero di programmi C per modellare situazioni reali o per testare opportunamente i programmi scritti.
+In realta' il computer non riesce a generare eventi realmente "a caso" in quanto tutti i programma si basano su una determinata sequenza di azioni. Tuttavia e' possibile avere un comportamento vicino alla casualita' con le //sequenze pseudocasuali//, che vengono generate con un procedimento deterministico ma mantengono proprieta' statistiche simili a quelle di una vera sequenza casuale.
+Inoltre le sequenze pseudocasuali possono, su richiesta, rigenerare la stessa sequenza di numeri. Questo e' molto utile ad esempio in fase di testing del codice.
+La generazione di numeri pseudocasuali e' molto complessa. Tutti i linguaggi di programmazione ad alto livello mettono a disposizione delle opportune funzioni per generare una sequenza. In C, per generare una sequenza pseudocasuale si utilizzano due funzioni di stdlib.h: la funzione
+<code c>
+void srand(unsigned int seed);
+</code>
+che serve a fissare il seme (//seed//) ovvero il valore iniziale della sequenza. E la funzione
+<code c>
+int rand(void);
+</code>
+che genera un intero nell'intervallo ''[0,RAND_MAX]'' ogni volta che viene chiamata.
+La ''srand()'' deve essere chiamata una sola volta per fissare il seme, successivamente la sequenza puo' essere generata con chiamate successive alla ''rand()''.
+Partendo dallo stesso valore iniziale si ottiene sempre la stessa sequenza quindi fornendo lo stessp seme a ''srand()'' possiamo riprodurre piu' volte la stessa sequenza casuale quando occorre (per testing o altro).
+Utilizzare le funzioni ''srand()'' e ''rand()'' per scrivere una funzione di prototipo
+<code>
+void init (int * vec, int lung);
+</code>
+che inizializza il vettore vec di lunghezza lung con dei valori pseudocasuali nell'intervallo [0,50] (//suggerimento//: leggere attentamente il manuale di ''srand'' e ''rand'' e utilizzare l'operatore resto ''%'')
+===== Esercizio 5: MSS, Maximum Segment Sum =====
+Dato un array di interi positivi e negativi, il segmento di somma massima e' la porzione contigua dell'array in cui la somma deigli elementi ha valore piu' alto.
+Ad esempio l'array
+<code c>
+[2,-4,2,-1,6-3]
+</code>
+ha come SSM il segmento [2,-1,6] di valore 7. Si chiede di definire due funzioni  per la stampa e per il calcolo di SSM, con i seguenti prototipi :
+<code c>
+/** stampa l'array s di lunghezza n */
+void print_array(int s[], int n);
+/** calcola SSM sull'array s di lunghezza lung
+ \param s array
+ \param n lunghezza
+ \param s_init puntatore alla variabile che conterra' la posizione di inizio dell'SSM
+ \param s_lung puntatore alla variabile che conterra' la lunghezza del segmento di somma massima
+ \retval k la somma degli elementi dell' SSM
+ */
+int ssm (int s[], int n, int * s_init, int * s_lung);
+</code>
+===== Esercizio 6: Invasion Percolation =====
+//Invasion percolation// e' una semplice forma frattale basata su un modello di diffusione di fluidi. In due dimensioni, l'invasion percolation si simula come segue.
+**(Passo 1)** Si genera una griglia quadrata ''sXs'' di numeri casuali nell'intervallo ''[1,r]'' . Ad esempio, una griglia 5x5 di numeri nel range [1,100] puo' essere:
+<code>
+	17	72	45	38
+	38	39	92	38
+	29	12	29	77
+	26	90	35	11
+	84	18	56	52
+</code>
+**(Passo 2)** poi si marca il centro della griglia come //pieno//, ad esempio '*' indica la cella piena:
+<code>
+	17	72	45	38
+	38	39	92	38
+	29	*	29	77
+	26	90	35	11
+	84	18	56	52
+</code>
+**(Passo 3)** Si effettua un ciclo in cui ad ogni passo:
+   - si esaminano i 4 vicini di tutte le celle gia' piene (gia' marcate con '*'),
+   - si sceglie la cella con il valore minore,
+   - si marca tale cella come 'piena'.
+Ad esempio, i quattro vicini della cella (2,2) nella griglia sono:
+ <code>
+
+	*	29
+
+ </code>
+L'evoluzione della forma frattale e' : (+ indica la cella selezionata ad ogni nuovo passo)
+<code>
+	17	72	45	38
+	38	39	92	38
+	+	*	29	77
+	26	90	35	11
+	84	18	56	52
+</code>
+<code>
+	17	72	45	38
+	38	39	92	38
+	*	*	29	77
+	+	90	35	11
+	84	18	56	52
+</code>
+<code>
+	17	72	45	38
+	38	39	92	38
+	*	*	+	77
+	*	90	35	11
+	84	18	56	52
+</code>
+Si richiede di implementare un programma C invocabile da shell con
+<code>
+./percolation
+</code>
+che legge dall ostandard input i valori di ''s'' ed ''r'' simula invasion percolation su una griglia sXs con valori nel range [1..r].
+Ogni iterazione viene visualizzata sullo schermo. La computazione si ferma quando il 50% delle celle e' stata marcata.
+Per l'inizializzazione con numeri casuali usare le funzioni ''srand()/rand()'' (vedi esercizio precedente).
+Per ottenere valori fra 1 ed r basta usare la funzione modulo (%), infatti l'espressione
+<code>
+rand()%r + 1
+</code>
+genera ogni volta che viene valutata un numero fra 1 ed r.
+Per inizializzare il generatore dei numeri casuali con valori diversi (e ottenere quindi sequenze diverse ad ogni run) usare
+<code>
+srand(time(NULL))
+</code>
+la ''time()'' restituisce il numero di secondi passati dal 1 gennaio 1970 (includere ''time.h'').
+Per pulire lo schermo fra una stampa e l'altra si puo' usare
+<code>
+system("clear");
+</code>
+per attendere un istante fra le varie visualizzazioni (che altrimenti non sono visibili) si puo' usare
+<code>
+sleep(1);
+</code>
+che aspetta un secondo, prima di riprendere la computazione (in ''unistd.h'').
+===== Esercizio 7: Stampa del triangolo di Tartaglia =====
+Il triangolo di Tartaglia è una disposizione geometrica dei coefficienti binomiali, ad esempio:
+<code>
+
+2 1
+3 3 1
+4 6 4 1
+5 10 10 5 1
+   .......
+</code>
+Scrivere un programma C che legge un intero ''n'' da standard input e stampa il triangolo di Tartaglia sullo standard output fino all riga ''n''-esima.
+===== Esercizio 8: Algoritmi di ordinamento su Array =====
+Facendo riferimento agli algoritmi di ordinamento visti a lezione, implementare un algoritmo di ordinamento non ricorsivo (bubblesort o selection sort) e l'algoritmo merge-sort su array di double.
+Valutare i tempi di esecuzione su array di lunghezza crescente generati casualmente nell'intervallo [0,1] utilizzando le funzioni ''rand(), srand()'' e il comenado di shell ''time''. Ci sono delle variazioni ?
+===== Esercizio 9: Algoritmi di ordinamento su Array: costo ... =====
+Cercare una formula (approssimata) che fornisca il numero di istruzioni eseguite dai tre algoritmi di ordinamento (selection sort, bubblesort e mergesort) in funzione di //n//, lunghezza dell'array da ordinare.