Prova scritta del 22 gennaio 2018 di Fondamenti di Informatica I (prof. Montessoro) + Fondamenti di Informatica II (prof. Di Gaspero)
Per studenti di Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti 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 (15 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.
Un secondo file contiene l’elenco di oggetti da dipingere (sfere o cubi), con le relative misure (raggio o lato), espresse in centimetri, e con il colore da utilizzare per ciascuno. Si veda l’esempio a fianco. Si assuma che tutti i colori riportati in tale file siano sicuramente presenti nella tabella di cui sopra.
Indipendentemente dal colore utilizzato, per dipingere una superficie di 1 metro quadrato sono necessari 0.15 litri di vernice.
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 degli oggetti 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 quanto riportato di seguito.
Esercizio 3 (11 punti)
Un intervallo di numeri interi a..b consiste in tutti i numeri interi 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 sotto-intervalli a..b ∪ c..d con un nuovo intervallo e..f è data dai risultati dell’unione di e..f con uno dei singoli sotto-intervalli 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ù sotto-intervalli.
Vogliamo definire un tipo di dato astratto intervallo_interi che rappresenti, in modo compatto, un singolo intervallo o un’unione di sotto-intervalli in modo da consentire un’implementazione efficiente delle operazioni descritte in seguito.
Le operazioni possibili sugli intervalli sono le seguenti:
• intervallo_interi crea_intervallo_interi(int a, int b): crea un nuovo intervallo a..b
• intervallo_interi unione(intervallo_interi i1, intervallo_interi i2): restituisce un nuovo intervallo rappresentato dall’unione di i1 e i2
• bool appartiene(int k, intervallo_interi i): verifica se k ∈ i
• elimina_intervallo_interi(intervallo_interi* i): elimina l’intervallo (o l’unione di sotto- intervalli) rappresentato da i
0.00271507 litri di blu 0.00359858 litri di rosso 0.0427848 litri di giallo 0.00157231 litri di bianco 0.000221616 litri di nero
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
sfera 3.6 BLU_S cubo 15.3 YEL7 sfera 2 YEL7 cubo 5.273 C0Q2
1. Si definisca un possibile descrittore per il tipo di dato intervallo (in altre parole l’opportuna typedef struct {…}
intervallo_interi;) 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 sotto-intervalli di cui è costituito l’intervallo.
Esercizio 2 (4 punti)
Scrivere una funzione in linguaggio C che, dato un vettore di numeri reali verifica se tale vettore rappresenta correttamente un heap-tree implicito. La funzione deve restituire true qualora il vettore sia una rappresentazione corretta, e false in caso contrario. Si discuta, informalmente, la complessità temporale dell’implementazione espressa in funzione del numero n di elementi del vettore.
