Prova scritta del 25 giugno 2018 di Fondamenti di Programmazione e Strutture Dati e Algoritmi Per studenti di Ing. Elettronica e Ing. Gestionale immatricolati a partire dall’anno 2017-18
DURATA DELLA PROVA: 3 ORE
A pena di annullamento immediato della prova:
1) Non è possibile consultare libri o appunti (in qualunque forma) né utilizzare calcolatrici, telefoni cellulari, ecc.
2) Non è consentito comunicare (con qualunque mezzo) 3) Non è consentito uscire dall’aula
Lo studente è tenuto a scrivere, correggere, compilare ed eseguire su computer (a casa o in laboratorio) gli esercizi di programmazione prima della prova orale. Alla prova orale lo studente deve portare una memory pen USB contenente i sorgenti dei programmi corretti e le stampe dei relativi file.
Esercizio 1 (14 punti)
L’orario delle lezioni di un corso universitario è rappresentato in un file il cui formato può essere dedotto dall’esempio a lato, dove:
• i nomi dei corsi sono privi di spazi;
• il numero che segue il nome del corso rappresenta il numero di lezioni elencate nel seguito della riga;
• ogni lezione è rappresentata dall’abbreviazione del giorno e dall’intervallo orario, senza spazi (le ore sono sempre numeri interi).
Il numero massimo di corsi è 20, le lezioni si svolgono dal lunedì al venerdì, in orario compreso tra le ore 8 e le 18.
Si scriva un programma in linguaggio C che riceva sulla riga di comando il nome di un file siffatto e stampi le eventuali sovrapposizioni di lezioni.
Relativamente all’esempio sopra riportato il programma dovrà stampare:
sovrapposizione di Fisica con Fondamenti_di_programmazione (LU ore 10) sovrapposizione di Analisi_matematica con Fisica (GI ore 15)
sovrapposizione di Analisi_matematica con Fisica (GI ore 16)
Suggerimento: si rappresentino i corsi in un vettore di stringhe e l’orario settimanale mediante una matrice di interi, uno per ogni ora di ogni giorno, che corrispondono all’indice del nome del corso che viene erogato in tale ora.
Esercizio 2 (4 punti)
Si consideri la libreria in linguaggio C per manipolare file bitmap vista a lezione, così definita:
typedef unsigned char byte;
typedef unsigned short int word;
typedef unsigned long int dword;
#define BMPFILETYPE 0x4D42 typedef struct tagCOLORTRIPLE {
byte blue;
byte green;
byte red;
} COLORTRIPLE;
typedef struct tagFILEHEADER {
word ImageFileType;
dword FileSize;
word Reserved1;
word Reserved2;
dword ImageDataOffset;
} FILEHEADER;
typedef struct tagBMPHEADER {
dword HeaderSize;
dword ImageWidth;
dword ImageHeight;
word NumberOfImagePlanes;
word BitsPerPixel;
dword CompressionMethod;
dword SizeOfBitmap;
dword HorizonalResolution;
dword VerticalResolution;
dword NumberOfColorsUsed;
dword
NumberOfSignificantColors;
} BMPHEADER;
typedef struct tagBITMAP {
dword width;
dword height;
COLORTRIPLE *pixel;
FILEHEADER fileheader;
BMPHEADER bmpheader;
} BITMAP;
#define PIXEL(image, row, column) \
image.pixel [(row( * image.width + (column)]
BITMAP ReadBitmap (FILE *fp);
void WriteBitmap (BITMAP bitmap, FILE *fp);
BITMAP CreateEmptyBitmap
(dword height, dword width);
void ReleaseBitmapData (BITMAP *bitmap);
Fondamenti_di_programmazione 3 LU 8-11 ME 10-12 VE 8-12 Fisica 2 LU 10-12 GI 15-18
Analisi_matematica 2 GI 14-17 VE 13-15
Si scriva una funzione in linguaggio C che riceva come argomenti una bitmap vuota (di forma quadrata) e l’iniziale di un colore primario (R, G o B). La funzione deve creare un’immagine costituita da tutte le gradazioni del colore indicato (gli altri colori primari resteranno a zero), di valore proporzionale alla distanza del punto dal vertice in basso a sinistra (cioè di coordinate [0, 0]). Si veda l’esempio a lato (le sfumature di grigio nella stampa in bianco e nero sono in realtà sfumature di rosso, verde o blu a seconda del codice inserito).
Suggerimento: per calcolare il valore da attribuire alla componente di colore si moltiplichi il massimo valore rappresentabile (255) per la distanza dal vertice
normalizzata rispetto alla diagonale del quadrato (che rappresenta la distanza massima). Si assuma già disponibile la funzione
double norm_distance (int r, int c, int dim)che riceve le coordinate di riga e di colonna e la lunghezza in pixel del lato del quadrato.
Esercizio 3 (12 punti)
Un vettore compatto è una struttura dati sequenziale in cui le eventuali ripetizioni di valori (aventi indici) contigui del vettore sono rappresentate da una coppia (valore, numero di ripetizioni). Ad esempio, il vettore
(tradizionale) {3, 3, 1, 1, 1, 6, 1, 1, 2, 2, 2, 2, 2} può essere rappresentato attraverso questa struttura dati attraverso la sequenza {(3, 2), (1, 3), (6, 1), (1, 2), (2, 5)}.
Vogliamo definire un tipo di dato astratto vettore compatto che implementi questa struttura dati.
Le operazioni possibili sui vettori compatti sono le seguenti:
• vettore_compatto crea_vettore_compatto(): crea un nuovo vettore compatto vuoto
• vettore compatto aggiungi_in_coda(vettore_compatto* v, int a): restituisce un nuovo vettore compatto ottenuto aggiungendo il valore a in coda al vettore (allocando opportunamente la memoria in modo dinamico)
• int cerca_prima_posizione(vettore_compatto v, int x) restituisce il valore della prima posizione (indice, dunque a partire da 0) in cui apparirebbe il valore x nella rappresentazione come vettore tradizionale
• elimina_vettore_compatto(vettore_compatto* v): elimina il vettore compatto v liberando la memoria eventualmente allocata dinamicamente
A titolo d’esempio, l’esecuzione di aggiungi_in_coda(v, 2) sul vettore riportato in esempio dovrebbe modificarlo in v = {(3, 2), (1, 3), (6, 1), (1, 2), (2, 6)}, viceversa, l’esecuzione di aggiungi_in_coda(v, 5) sullo stesso vettore dovrebbe modificarlo in v = {(3, 2), (1, 3), (6, 1), (1, 2), (2, 5), (5, 1)}.
Per ciò che riguarda la funzione di ricerca, invece, l’esecuzione di cerca_prima_posizione(v, 1) sul vettore riportato in esempio dovrebbe restituire il valore 2, che è l’indice della posizione del primo 1 nella rappresentazione tradizionale mentre l’esecuzione di cerca_prima_posizione(v, 2) dovrebbe restituire 8, indice della prima occorrenza di 2 nella rappresentazione tradizionale.
1. Si definisca un possibile descrittore per il tipo di dato vettore_compatto (in altre parole la typedef struct {…} vettore_compatto) e per le eventuali ulteriori strutture di dati utilizzate per la rappresentazione.
2. Si implementino in linguaggio C le operazioni di manipolazione dei vettori compatti descritte in precedenza. Qualora fosse necessario si assuma l’esistenza delle funzioni di manipolazione delle strutture dati utilizzate nel descrittore, scelte fra quelle studiate durante il corso.
3. Si discuta, informalmente, la complessità temporale dell’implementazione delle operazioni di manipolazione espressa in funzione del numero n di sequenze di valori contigui uguali memorizzate nel vettore compatto.
