Prova scritta del 22 gennaio 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)
Un’azienda deve dipingere degli oggetti di forme geometriche regolari (sfere e cubi) con diversi colori. I colori sono generati mescolando in proporzioni diverse le vernici di cinque colori primari: blu, rosso, giallo, bianco e nero. La tabella che indica come devono essere
combinati i colori primari per ottenere un dato colore è riportata in un file il cui formato può essere dedotto dall’esempio a fianco. Come si può facilmente intuire, la prima è una riga di intestazione e le altre riportano le percentuali da utilizzare per ciascun colore primario.
Valgono le seguenti assunzioni:
• i codici dei colori sono sempre composti da una sola parola;
• le percentuali sono sempre dei numeri interi;
• i colori primari sono sempre gli stessi e sono sempre scritti nel medesimo ordine (blu, rosso, giallo, bianco e nero);
• il massimo numero di colori nella tabella è pari a 100;
• indipendentemente dal colore utilizzato, per dipingere una superficie di 1 metro quadrato sono necessari 0.15 litri di vernice.
Un secondo file contiene un elenco di superfici (espresse in metri quadrati) con associato il colore da utilizzare per ciascuna. Si veda l’esempio a fianco. Si assuma che tutti i colori riportati in tale file siano sicuramente presenti nella tabella di cui sopra.
Si scriva un programma in linguaggio C che riceva sulla riga di comando il nome di un file contenente la tabella dei colori e il nome di un file contenente l’elenco delle superfici come sopra descritto.
Il programma deve stampare la quantità totale, in litri, dei colori primari necessari a verniciare tutti gli oggetti presenti nel secondo file.
Relativamente agli esempi sopra riportati, il programma dovrà stampare:
0.700923 litri di blu 0.340797 litri di rosso 2.54435 litri di giallo 0.237285 litri di bianco 0.1026 litri di nero
Esercizio 2 (4 punti)
Si consideri una libreria in linguaggio C per manipolare file audio così definita:
typedef unsigned char byte;
typedef unsigned short int word;
typedef unsigned long int dword;
#define SAMPLE(wave, channel, offset) \ wave.wavedata.sample \ [2 * (offset) + (channel)]
#define FMTPCM 1
#define SAMPLINGRATE 44100
#define CHANNELS 2
#define BITSPERSAMPLE 16
#define LEFT 0
#define RIGHT 1
#define RIFF_ID "RIFF"
#define WAV_ID "WAVE"
#define FMT_ID "fmt "
#define DATA_ID "data"
typedef struct tagRIFFHEADER {
char riffid[4];
dword FileSize;
char waveid[4];
} RIFFHEADER;
typedef struct tagFMTHEADER {
char fmtid[4];
dword fmtsize;
word format;
word channels;
dword SampleRate;
dword BytesPerSecond;
word BlockAlign;
word BitsPerSample;
} FMTHEADER;
typedef struct tagWAVEDATA {
char dataid[4];
dword DataSize;
signed short int *sample;
} WAVEDATA;
typedef struct tagWAVE {
RIFFHEADER riffheader;
FMTHEADER fmtheader;
unsigned long int numofstereosamples;
WAVEDATA wavedata;
} WAVE;
void WriteWave (WAVE wave, FILE *fp);
WAVE ReadWave (FILE *fp);
WAVE CreateEmptyCDaudioWave (unsigned long int numofstereosamples);
void ReleaseWaveData (WAVE *wave);
3.6 BLU_S 15.3 YEL7 2 YEL7 5.273 C0Q2 colore % blu % rosso % giallo % bianco % nero C0Q2 34 26 10 30 0 BLU_S 80 1 0 0 19 YEL7 0 5 95 0 0
Per amplificare un suono senza incorrere nell’overflow è necessario conoscere in anticipo il massimo valore assunto dai campioni nella WAVE da amplificare.
Si scriva in linguaggio C la funzione short int max_campione (WAVE w) che riceve come argomento una WAVE (già letta da file e caricata in memoria) e restituisca il massimo valore presente tra i campioni di entrambi i canali.
Esercizio 3 (13 punti)
Un intervallo di numeri reali [a, b] consiste in tutti i numeri reali compresi fra a e b, estremi inclusi. Un’unione di intervalli [a, b] e [c, d] (con a ≤ c) dà come risultato un singolo intervallo [min{a, c}, min{b, d}], se i due intervalli non sono disgiunti, altrimenti l’insieme risultato può essere descritto come [a, b] ∪ [c, d] se i due intervalli sono disgiunti. Analogamente, l’operazione di unione applicata ad un insieme di sottointervalli [a, b] ∪ [c, d] con un nuovo intervallo [e, f] è data dai risultati dell’unione di [e, f] con uno dei singoli sottointervalli costituenti l’unione (qualora non sia da esso disgiunto) oppure è descritto da [a, b] ∪ [c, d] ∪ [e, f], e così via per insiemi di più sottointervalli.
Vogliamo definire un tipo di dato astratto intervallo che rappresenti, in modo compatto, un singolo intervallo o un’unione di sottointervalli in modo da consentire un’implementazione efficiente delle operazioni descritte in seguito.
Le operazioni possibili sugli intervalli sono le seguenti:
• intervallo crea_intervallo(float a, float b): crea un nuovo intervallo [a, b]
• intervallo unione(intervallo i1, intervallo i2): restituisce un nuovo intervallo rappresentato dall’unione di i1 e i2
• bool appartiene(float x, intervallo i): verifica se x ∈ i
• elimina_intervallo(intervallo* i): elimina l’intervallo rappresentato da i
1. Si definisca un possibile descrittore per il tipo di dato intervallo (in altre parole l’opportuna typedef struct {…}
intervallo;) e si definiscano le ulteriori strutture di dati utilizzate per la rappresentazione.
2. Si implementino in linguaggio C le operazioni di manipolazione degli intervalli 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 sottointervalli di cui è costituito l’intervallo.
