Scrivere una funzione di prototipo
void swap (int *a, int*b);
che ha l'effetto di scambiare i valori di due variabili, ad esempio:
int a=5;
int b=63;
swap(&a,&b);
printf("a = %d, b = %d \n", a, b);
....
deve stampare
a = 63, b = 5
Sarebbe stato possibile ottenere lo stesso effetto utilizzando una funzione di prototipo
void swap (int a, int b);
? Perche' ?
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.
Scrivere una funzione di prototipo
int cerca (int * vec, int lung, int x);
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().
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
void srand(unsigned int seed);
che serve a fissare il seme (seed) ovvero il valore iniziale della sequenza. E la funzione
int rand(void);
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
void init (int * vec, int lung);
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 %)
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
[2,-4,2,-1,6-3]
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 :
/** 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);
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 5×5 di numeri nel range [1,100] puo' essere:
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
(Passo 2) poi si marca il centro della griglia come pieno, ad esempio '*' indica la cella piena:
26 17 72 45 38 10 38 39 92 38 44 29 * 29 77 61 26 90 35 11 83 84 18 56 52
(Passo 3) Si effettua un ciclo in cui ad ogni passo:
Ad esempio, i quattro vicini della cella (2,2) nella griglia sono:
39 29 * 29 90
L'evoluzione della forma frattale e' : (+ indica la cella selezionata ad ogni nuovo passo)
26 17 72 45 38 10 38 39 92 38 44 + * 29 77 61 26 90 35 11 83 84 18 56 52
26 17 72 45 38 10 38 39 92 38 44 * * 29 77 61 + 90 35 11 83 84 18 56 52
26 17 72 45 38 10 38 39 92 38 44 * * + 77 61 * 90 35 11 83 84 18 56 52
Si richiede di implementare un programma C invocabile da shell con
./percolation
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
rand()%r + 1
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
srand(time(NULL))
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
system("clear");
per attendere un istante fra le varie visualizzazioni (che altrimenti non sono visibili) si puo' usare
sleep(1);
che aspetta un secondo, prima di riprendere la computazione (in unistd.h).
Il triangolo di Tartaglia è una disposizione geometrica dei coefficienti binomiali, ad esempio:
1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
.......
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.
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 ?
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.