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 (14 punti)
Una rete di distributori automatici comunica periodicamente alla sede del gestore, tramite un collegamento internet, il numero di esemplari ancora disponibili di ciascun prodotto onde pianificare il necessario approvvigionamento. I dati vengono tutti raccolti in un file di testo il cui formato può essere dedotto dal seguente esempio:
RIZZI_02 4: KITKAT 3, OREO 7, OROSAIWA 9, CHIPSCHILI 12.
MANTICA_01 3: OROSAIWA 19, CHIPSTER 0, OREO 5.
KOLBE_01 5: CHIPSCHILI 10, OROSAIWA 9, OREO 0, CHIPSTER 1, KITKAT 4.
Si osservi che:
• i nomi in codice dei distributori e i nomi dei prodotti sono sempre scritti con una sola parola;
• il codice del distributore è seguito dal numero dei prodotti in vendita in quel distributore e poi dal carattere due punti;
• ogni nome di prodotto è seguito dal numero di esemplari ancora disponibili e poi dal carattere virgola o punto.
Un secondo file contiene l’elenco dei prodotti venduti dal gestore e, per ciascuno, il numero di esemplari di cui ogni distributore che abbia in vendita tale prodotto deve essere rifornito (cioè il numero totale di esemplari che devono trovarsi nel distributore quando è appena stato riempito).
Un esempio di tale file è riportato nel riquadro a lato.
Scopo dell’esercizio è calcolare per ogni prodotto il numero di esemplari che devono essere caricati
sul furgone che, facendo il giro di tutti i distributori elencati nel primo file, li rifornisce in base ai dati presenti nel secondo file.
Per esempio, facendo riferimento agli esempi sopra riportati, il furgone dovrà caricare 33 esemplari di KITKAT: 17 per il distributore RIZZI_02 e 16 per il distributore KOLBE_01.
Non è noto il massimo numero di distributori. Il massimo numero di prodotti, invece, è 500. Si assuma che tutti i prodotti dei distributori siano presenti nell’elenco del secondo file.
Si scriva un programma in linguaggio C che riceva sulla riga di comando i nomi di due file come sopra descritto (il primo il file che riporta lo stato attuale dei distributori, il secondo il numero di esemplari richiesto) e stampi sul monitor l’elenco dei prodotti (in un ordine qualsiasi) con il numero totale di esemplari da caricare sul furgone e, per ciascuno, il numero presente nel secondo file come istruzione per l’addetto al rifornimento.
Relativamente agli esempi sopra riportati, il programma dovrà stampare:
KITKAT 33 (riempire il distributore fino a 20) OREO 33 (riempire il distributore fino a 15) OROSAIWA 38 (riempire il distributore fino a 25) CHIPSCHILI 8 (riempire il distributore fino a 15) CHIPSTER 63 (riempire il distributore fino a 32)
KITKAT 20 OREO 15 OROSAIWA 25 CHIPSCHILI 15 CHIPSTER 32
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXPRODOTTI 500 struct prodotto
{
char nome[32];
int q_distr_pieno;
int q_carico_per_distribuzione;
};
int leggi_prodotti (FILE *fp, struct prodotto prodotti[], int nmax);
void calcola_carico_per_distribuzione (FILE *fpdistributori, struct prodotto prodotti[], int n_prodotti);
int cerca_prodotto (struct prodotto prodotti[], int n_prodotti, char nome[]);
void stampa_carico_per_distribuzione (struct prodotto prodotti[], int n_prodotti);
int main (int argc, char *argv[]) {
FILE *fpdistributori, *fpprodotti;
struct prodotto prodotti[MAXPRODOTTI];
int n_prodotti;
if (argc != 3) {
printf ("argomenti: <file distributori> <file prodotti>\n");
exit (EXIT_FAILURE);
}
/* apri i file */
if ((fpdistributori = fopen (argv[1], "r")) == NULL) {
printf ("errore di apertura del file %s\n", argv[1]);
exit (EXIT_FAILURE);
}
if ((fpprodotti = fopen (argv[2], "r")) == NULL) {
printf ("errore di apertura del file %s\n", argv[2]);
exit (EXIT_FAILURE);
}
/* leggi il file prodotti */
n_prodotti = leggi_prodotti (fpprodotti, prodotti, MAXPRODOTTI);
/* calcola il carico per la distribuzione */
calcola_carico_per_distribuzione (fpdistributori, prodotti, n_prodotti);
/* stampa il carico per la distribuzione */
stampa_carico_per_distribuzione (prodotti, n_prodotti);
fclose (fpprodotti);
fclose (fpdistributori);
return EXIT_SUCCESS;
}
int leggi_prodotti (FILE *fpprodotti, struct prodotto prodotti[], int nmax) {
int i;
i = 0;
while (i < MAXPRODOTTI &&
(fscanf (fpprodotti, "%s %d", prodotti[i].nome, &prodotti[i].q_distr_pieno) != EOF)) {
prodotti[i].q_carico_per_distribuzione = 0;
i++;
}
return i;
}
void calcola_carico_per_distribuzione (FILE *fpdistributori, struct prodotto prodotti[], int n_prodotti) {
int indice, i, num_prod, q;
char nome_prodotto[32];
while (fscanf (fpdistributori, "%*s %d%*c", &num_prod) != EOF) {
for (i = 0; i < num_prod; i++) {
fscanf (fpdistributori, "%s %d%*c", nome_prodotto, &q);
indice = cerca_prodotto (prodotti, n_prodotti, nome_prodotto);
if (indice == -1) {
printf ("prodotto %s non presente in elenco\n", nome_prodotto);
exit (EXIT_FAILURE);
}
prodotti[indice].q_carico_per_distribuzione += prodotti[indice].q_distr_pieno - q;
} } return;
}
int cerca_prodotto (struct prodotto prodotti[], int n_prodotti, char nome[]) {
int i;
i = 0;
while (i < n_prodotti) {
if (strcmp (nome, prodotti[i].nome) == 0) return i;
i++;
}
return -1;
}
void stampa_carico_per_distribuzione (struct prodotto prodotti[], int n_prodotti) {
int i;
for (i = 0; i < n_prodotti; i++)
printf ("%s %d (riempire il distributore fino a %d)\n", prodotti[i].nome, prodotti[i].q_carico_per_distribuzione, prodotti[i].q_distr_pieno);
return;
}
Esercizio 2 (8 punti)
Si consideri un nuovo tipo di dato astratto lista_multipla che consiste di un vettore (creato dinamicamente, ma di dimensione fissa) di liste di valori di tipo int. Il peso di ciascuna delle liste che costituiscono una lista multipla è dato dalla somma dei suoi valori. Si veda l’esempio a fianco di una lista multipla che consiste di 4 liste e in cui il peso della prima lista è 4, quello della seconda 4, della terza 0 e della quarta 6.
Le operazioni possibili sulle liste multiple sono le seguenti:
• lista_multipla crea_lista_multipla(int m): crea un vettore di m liste inizialmente vuote e imposta eventuali altre informazioni nel descrittore;
• inserisci_lista_multipla(lista_multipla *lm, int d): inserisce il dato d nella lista, facente parte della lista multipla lm, avente peso minore;
• rimuovi_lista_multipla(lista_multipla *lm, int d): rimuove tutte le occorrenze del dato d dalle liste facenti parte della lista multipla lm;
• elimina_lista_multipla(lista_multipla *lm): elimina la lista multipla deallocando tutti i dati allocati dinamicamente.
1. Si definisca un possibile descrittore per il tipo di dato lista multipla (in altre parole la struct _lista_multipla).
2. Si implementino in linguaggio C le operazioni di manipolazione delle liste multiple descritte in precedenza. Qualora fosse necessario si assuma l’esistenza di funzioni di manipolazione delle liste adattate allo specifico tipo di
informazione memorizzata nelle singole liste (ad es. aggiungi_in_testa(lista* l, int dato), nodo_lista*
trova_dato(nodo_lista *t, int dato)). In tal caso, si scrivano le dichiarazioni delle funzioni utilizzate.
3. Si discuta, informalmente, la complessità temporale dell’implementazione delle operazioni di manipolazione espressa in funzione di n, numero totale di elementi memorizzati in tutte le liste, e di m, numero totale di liste.
#include <stdlib.h>
typedef struct _nodo_lista { int dato;
struct _nodo_lista* succ;
} nodo_lista;
typedef struct {
// una possibilità è mantenere due array, uno con il peso e l'altro con i puntatori ai nodi, oppure si potrebbe racchiudere tutto in un singolo record
nodo_lista** liste;
int* peso;
int m;
} lista_multipla;
// complessità O(m): dovuto al ciclo for lista_multipla crea_lista_multipla(int m) { lista_multipla lm;
int i;
lm.liste = (nodo_lista**)malloc(m * sizeof(nodo_lista));
lm.peso = (int*)malloc(m * sizeof(int));
assert(lm.liste != NULL && lm.peso != NULL);
for (i = 0; i < m; i++) { lm.liste[i] = NULL;
lm.peso[i] = 0;
}
lm.m = m;
return lm;
}
// complessità O(m + n): ciclo for seguito poi dalla scansione della lista di peso minore (che però, nel caso peggiore potrebbe avere lunghezza n)
void inserisci_lista_multipla(lista_multipla* lm, int d) { int i, i_min = 0;
nodo_lista* n;
for (i = 1; i < lm->m; i++)
if (lm->peso[i] < lm->peso[i_min]) i_min = i;
n = (nodo_lista*)malloc(sizeof(nodo_lista));
assert(n != NULL);
n->dato = d;
n->succ = lm->liste[i_min];
lm->liste[i_min] = n;
lm->peso[i] += d;
}
// complessità O(m + n): ciclo for al cui interno vi è la deallocazione degli elementi della lista con valore d (complessivamente n)
void rimuovi_lista_multipla(lista_multipla* lm, int d) { int i;
nodo_lista *c, *p, *n;
for (i = 0; i < lm->m; i++) { p = NULL;
c = lm->liste[i];
while (c != NULL) { n = c->succ;
if (c->dato == d) { if (p == NULL)
lm->liste[i] = c->succ;
else
p->succ = c->succ;
free(c);
lm->peso[i] -= d;
} c = n;
} } }
// complessità O(m + n): analogamente al precedente, ciclo for al cui interno vi è la deallocazione di tutti gli elementi della lista (complessivamente n)
void elimina_lista_multipla(lista_multipla* lm) { int i;
nodo_lista *c, *p;
for (i = 0; i < lm->m; i++) { c = lm->liste[i];
while (c != NULL) { p = c->succ;
free(c);
c = p;
} }
free(lm->liste);
free(lm->peso);
}
Esercizio 3 (8 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);
Nei montaggi video, l’effetto di transizione tra due immagini detto “tendina orizzontale” (“wipe”, in inglese) consiste in una linea verticale che si sposta dall'estremità sinistra a quella destra dello schermo rivelando la nuova immagine.
Si scriva un programma che generi il fotogramma centrale di tale transizione, in cui le due immagini compaiono per metà.
Il programma deve ricevere sulla riga di comando, nell’ordine, i seguenti parametri:
• nome del file contenente la prima immagine
• nome del file contenente la seconda immagine (di dimensioni identiche alla prima)
• nome del file di uscita
Si assuma che le due immagini di ingresso abbiano le stesse dimensioni.
La figura riporta un esempio.
Prima immagine Seconda immagine Immagine di uscita
/* NOTA: QUESTA IMPLEMENTAZIONE È PIÙ GENERALE DI QUANTO RICHIESTO DAL COMPITO.
PER ULTERIORI DETTAGLI SI VEDA IL TESTO DEL COMPITO DI “ARCHITETTURA DEI CALCOLATORI”
NELLA STESSA DATA */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "bmp.h"
#define OUT_FILE_BASE_NAME "wipe_"
#define OUT_FILE_EXT ".bmp"
void wipe_mix (BITMAP img1, BITMAP img2, BITMAP imgout, double p);
int main (int argc, char *argv[]) {
FILE *fp1, *fp2, *fpout;
char filename[64];
int n, i;
BITMAP img1, img2, imgout;
if (argc != 4)
{ printf ("ARGOMENTI: <file in1> <file in2> <N>\n");
exit (EXIT_FAILURE);
}
if ((fp1 = fopen (argv[1], "rb")) == NULL) {
printf ("Error opening input file 1\n");
exit (EXIT_FAILURE);
}
if ((fp2 = fopen (argv[2], "rb")) == NULL) {
printf ("Error opening input file 2\n");
exit (EXIT_FAILURE);
}
n = atoi (argv[3]);
img1 = ReadBitmap (fp1);
fclose (fp1);
img2 = ReadBitmap (fp2);
fclose (fp2);
if (img1.height != img2.height || img1.width != img2.width) {
printf ("Images have different sizes\n");
exit (EXIT_FAILURE);
}
imgout = CreateEmptyBitmap (img1.height, img1.width);
for (i = 0; i <= n; i++) {
sprintf (filename, "%s%d%s", OUT_FILE_BASE_NAME, i, OUT_FILE_EXT);
if ((fpout = fopen (filename, "wb")) == NULL) {
printf ("Error opening output file %s\n", filename);
exit (EXIT_FAILURE);
}
wipe_mix (img1, img2, imgout, i / (double) n);
WriteBitmap (imgout, fpout);
fclose (fpout);
}
ReleaseBitmapData (&img1);
ReleaseBitmapData (&img2);
ReleaseBitmapData (&imgout);
return EXIT_SUCCESS;
}
void wipe_mix (BITMAP img1, BITMAP img2, BITMAP imgout, double p) {
int r, c, threshold;
threshold = p * imgout.width;
for (r = 0; r < imgout.height; r++) {
for (c = 0; c < imgout.width; c++) {
if (c < threshold)
PIXEL (imgout, r, c) = PIXEL (img1, r, c);
else
PIXEL (imgout, r, c) = PIXEL (img2, r, c);
} }
return;
}
