Prova scritta del 19 luglio 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 (13 punti)
Nel gioco della morra cinese ad ogni giocata due giocatori scelgono e dichiarano con un gesto della mano uno tra gli oggetti
“carta”, “forbici” e “ sasso”. Il sasso vince sulla forbice, la forbice sulla carta e la carta sul sasso.
In una gara internazionale sono state registrate le giocate di due giocatori in un file che contiene, per ogni riga, l’oggetto scelto dal giocatore 1 e quello scelto dal giocatore 2. Il problema è che, a causa delle numerose nazionalità presenti, la registrazione è avvenuta in modo un po’ confuso e i nomi degli oggetti sono stati scritti in lingue diverse, come nell’esempio a destra.
Il vettore char* dizionario[50][3] contiene la forma
delle tre parole in tutte le lingue utilizzate (che sono al massimo 50, il numero di lingue effettivamente presenti è contenuto nella variabile int n_lingue), nell’ordine “carta”,
“forbici” e “sasso”. Si veda l’esempio a sinistra. Si osservi che le parole non contengono mai spazi.
Si scriva una funzione in linguaggio C che riceva come argomenti il nome di un file contenente le giocate come sopra descritto, il vettore char* dizionario[50][3]e la variabile intera int n_lingue e stampi il punteggio dei due giocatori e il vincitore (oppure l’indicazione che la partita è terminata alla pari).
Nell’esempio precedente il programma dovrà stampare:
punteggio giocatore 1: 2 punteggio giocatore 2: 1 vince il giocatore 1
NOTA: è obbligatorio scrivere e utilizzare una funzione che riceva come ingresso due codici numerici che rappresentano gli oggetti dichiarati in una giocata (0 = carta, 1 = forbice, 2 = sasso) e restituisce 1 se vince il primo giocatore e 2 se vince il secondo.
Esercizio 2 (5 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);
scissors carta stone ciseaux forbici pierre carta paper paper papier carta forbici sasso
paper scissors stone papier ciseaux pierre
La figura a fianco rappresenta l’iperbole di equazione x = 1/y nel primo quadrante.
L’immagine è grande 1000 x 1000 pixel e ogni unità del grafico è rappresentata da 100 pixel (quindi, l’intera immagine rappresenta uno spazio di 10 x 10 unità nelle coordinate del grafico dell’equazione).
Come è noto, a causa della rappresentazione discreta dei punti dell’immagine soltanto alcuni soddisfano esattamente l’equazione dell’iperbole. Pertanto, per poter evidenziare meglio l’andamento della curva, sono stati colorati in nero tutti i punti
appartenenti al luogo geometrico che soddisfa l’equazione a meno di un errore di 0,03 unità. Lo sfondo è un grigio di luminosità pari a 3/4 della luminosità massima (bianco).
Si scriva una funzione in linguaggio C che riceva come argomento una struttura dati di tipo BITMAP, già allocata e rappresentante un’immagine di 1000 x 1000 pixel, e vi scriva l’immagine sopra descritta.
Esercizio 3 (12 punti)
Un modo per rappresentare gli insiemi di valori interi (nel senso matematico di ”collezioni” di valori prive di duplicazioni) è attraverso un vettore dinamico che contiene i valori rappresentati nell’insieme. In particolare, qualora il vettore venga
mantenuto ordinato, le operazioni di verifica dell’appartenenza di un elemento ad un insieme possono essere realizzate in modo efficiente.
Vogliamo definire l’implementazione del tipo di dato astratto insieme che gestisca questa struttura dati attraverso la sua rappresentazione per mezzo di vettori dinamici ordinati.
Le operazioni possibili sugli insiemi sono le seguenti:
• insieme crea_insieme(): crea un nuovo insieme vuoto.
• struct info_rango rango(insieme i, int x): restituisce due informazioni organizzate nella seguente struct:
struct info_rango { int rango;
bool presente;
}
Il campo rango conterrà il rango del valore x nell’insieme i, ovvero il numero di elementi minori di x (alternativamente, la posizione di x nella sequenza ordinata), mentre il campo presente avrà valore true qualora l’elemento x sia presente nell’insieme e false in caso contrario.
* insieme aggiungi(insieme* i, int a): restituisce il descrittore del nuovo insieme ottenuto aggiungendo il valore a (allocando, se necessario, opportunamente la memoria); se tale valore è già presente nell’insieme la funzione non farà alcuna modifica
* void elimina_insieme(insieme* i): elimina l’insieme i liberando la memoria eventualmente allocata dinamicamente.
1. Si definisca un possibile descrittore per il tipo di dato insieme (in altre parole la typedef struct {}
insieme) e per le eventuali ulteriori strutture di dati utilizzate per la rappresentazione.
2. Si implementino in linguaggio C le operazioni di manipolazione degli insiemi 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. In particolare, si richiede che l’implementazione della funzione rango() abbia complessità O(log n), con n numero di valori contenuti nell’insieme.
Nota: il rango di un determinato valore x è calcolabile sia nel caso esso sia presente nell’insieme che in caso contrario. Ad esempio, per l’insieme { 1, 5, 8, 14, 18 }, il valore 4 ha rango 2 (ovvero apparirebbe in seconda posizione nella sequenza ordinata), mentre il valore 14 ha rango 4.
Suggerimento: la funzione rango() può essere utilizzata per implementare la funzione aggiungi() in modo più efficiente.
