Questa è una vecchia versione del documento!
Indice
Esercitazione 3
Dove si sviluppano semplici programmi C che utilizzano i costrutti di controllo e gli array e si comincia a parlare di tempo impiegato per risolvere un problema.
Esercizio 1: Filtrare un array
Scrivere un programma C che legge da tastiera una array di 20 valori reali, trova la media e stampa sullo standard output solo i valori maggiori della media.
Esercizio 2: Somma e prodotto di matrici
Scrivere un programma C costituito da un main()
che legge da standard input due matrici 4quadrate $10\times10$ di reali, calcola somma e prodotto e stampa i risultati sullo standard output.
Esercizio 3: Massimo Comun Divisore
(1) Scrivere un programma C che
- legge da standard input x ed y
- calcola MCD(x,y) utilizzando il metodo delle divisioni successive (pag 80 lucidi sui costrutti di controllo)
- stampa il risultato sullo standard output
(2) Scrivere un programma C che
- legge da standard input x ed y
- calcola MCD(x,y) utilizzando il metodo delle divisioni successive (pag 94 e seguenti lucidi sui costrutti di controllo)
- stampa il risultato sullo standard output
Utilizzare il comando time
per valutare il tempo impiegato per calcolare MCD(m,n)
con m=10000000,n=9457831
con i due algoritmi.
Per evitare di misurare i tempi di attesa dell'input dallo schermo assegnare direttamente i valori alle variabili all'inizio del main e compilare.
Supponendo il nome degli eseguibili sia euclide1
ed euclide2
basta utilizzare il comando di shell “time” che ha come argomento un eseguibile, ovvero
time ./euclide1
e
time ./euclide2
per ottenere il tempo impiegato effettuando operazioni dentro il sistema operativo e fuori. Confrontare i tempi ottenuti con le due implementazioni ed analizzare i risultati. Utilizzare il comando
man time
per capire come interpretare i valori stampati da time su standard output.
Esercizio 4: 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
[2,-4,2,-1,6-3]
ha come SSM il segmento [2,-1,6] di valore 7. Si chiede di realizzare in programma C che legge dallo standard input N interi, li inserisce in un array lungo N, calcola il segmento di somma massima e lo stampa sullo standard output. N deve essere definito con una opportuna MACRO.
Esercizio 5: Mandelbrot (Avanzato)
L'insieme di Mandelbrote' un insieme frattale definito come l'insieme dei numeri complessi c per i quali la successione definita da:
z(0) = 0 z(n+1) = z(n)^2 + c
e' limitata, cioe' |z( n )|< 2
per ogni n >=0
.
Infatti al variare di c
, la sequenza puo' tendere
all’infinito o rimanere confinata in un disco di raggio 2 del piano complesso centrato
nell’origine.
L’algoritmo piu' semplice per visualizzare (una approssimazione de) l’insieme di Mandelbrot ´e l’Escape Time Algorithm. In questo algoritmo, dati A
(l’area del piano complesso
da visualizzare) ed r
(una precisione fissata) si effettuano i seguenti passi:
- Si suddivide A in una griglia di punti a distanza uniforme (pixel)
- per ogni pixel (x, y)
- si calcolano r valori della sequenza con c=(x,y)
- se dopo r iterazioni
|z( r )|⇐ 2
si considera c appartenente all'insieme e si assegna a c il colore NERO
- altrimenti si assegna a c il colore j, che e' il minimo indice per cui
| z(j) |>=2
Scrivere un programma C che calcola l'insieme di Mandelbrot per il rettangolo di estremi (-2,1) (1,-1) e stampando sullo standard output i colori dei pixel suppenendo di dividere il rettangolo in 100×100 pixel.