DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Esercitazione: Array e puntatori ======

===== Esercizio 1: Funzione swap =====
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' ?

===== 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>
26	17	72	45	38
10	38	39	92	38
44	29	12	29	77
61	26	90	35	11
83	84	18	56	52
</code>
**(Passo 2)** poi si marca il centro della griglia come //pieno//, ad esempio '*' indica la cella piena: 
<code>
26	17	72	45	38
10	38	39	92	38
44	29	*	29	77
61	26	90	35	11
83	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>	 	 	 	 
 	 	39	 	 
 	29	*	29	 
 	 	90	 	 
 </code>	 	 	 	 
L'evoluzione della forma frattale e' : (+ indica la cella selezionata ad ogni nuovo passo)
<code> 
26	17	72	45	38
10	38	39	92	38
44	+	*	29	77
61	26	90	35	11
83	84	18	56	52
</code>
<code>
26	17	72	45	38
10	38	39	92	38
44	*	*	29	77
61	+	90	35	11
83	84	18	56	52
</code>
<code>
26	17	72	45	38
10	38	39	92	38
44	*	*	+	77
61	*	90	35	11
83	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>
          1
        1 2 1
       1 3 3 1
      1 4 6 4 1
    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.