Scritto Settembre 2008

Di seguito la soluzione commentata dell’esame scritto di Settembre 2008.

Esercizio 1.

Ci viene chiesto di implementare un sistema per gestire i Gran Premi di Formula 1.

Identifichiamo subito la classe Circuito, che ha un nome (stringa), una nazione (stringa), una lunghezza (float) e un numero di giri (intero). L’interfaccia di tale classe sarà la seguente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Circuito
{
public:
    Circuito();
 
    string getNome() const { return nome; }
    void setNome(string value) { nome = value; }
 
    string getNazione() const;
    void setNazione(string value);
 
    float getLunghezza() const;
    void setLunghezza(float value);
 
    int getGiri() const;
    void setGiri(int value);
 
private:
    string nome;
    string nazione;
    float lunghezza;
    int giri;
};

Alle linee 6 e 7 è stata fornita anche l’implementazione di un metodo get e di un metodo set, quindi abbiamo già soddisfatto uno dei requisiti della traccia (senza usare troppa penna).

Un Gran Premio è identificato da una data e si svolge in un circuito. Per ogni Gran Premio siamo interessati ai tempi dei giri delle diverse fasi: prove libere, prove ufficiali, warmup e gara. Di ogni giro ci interessa il numero progressivo (ad esempio se è il decimo giro di gara), la vettura che l’ha effettuato e il tempo che la vettura ha impiegato per completarlo. A sua volta, di una vettura ci interessa il numero, la squadra a cui appartiene e il pilota che la guida. Vediamo come spezzare tutte queste informazioni.

Iniziamo dalla vettura, che può essere modellata tramite la seguente classe.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Vettura
{
public:
    Vettura();
 
    int getNumero() const;
    void setNumero(int value);
 
    string getSquadra() const;
    void setSquadra(string value);
 
    string getPilota() const;
    void setPilota(string value);
 
private:
    int numero;
    string squadra;
    string pilota;
};

Poiché per squadra e pilota non c’è la necessità di memorizzare informazioni strutturate né di eseguire particolari operazioni, se non al più un confronto di uguaglianza, una stringa sarà più che sufficiente.

A questo punto possiamo raggruppare le informazioni relative a un singolo giro in una classe. Il numero progressivo sarà rappresentato dal campo numero di tipo intero, mentre la vettura da un’istanza della classe Vettura. Per il tempo, visto che in aula ne abbiamo poco, scegliamo la soluzione più semplice e utilizziamo un intero che rappresenti i millisecondi (magari mettiamo un commento, per non lasciare dubbi a chi leggerà il nostro codice).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Giro
{
public:
    Giro();
 
    int getNumero() const;
    void setNumero(int value);
 
    // tempo espresso in millisecondi
    int getTempo() const;
    void setTempo(int value);
 
    Vettura getVettura() const;
    void setVettura(Vettura value);
 
private:
    int numero;
    int tempo;
    Vettura vettura;
};

Per il Gran Premio ci interessavano data, circuito e giri: conviene definire una nuova classe. Visto che non dovremo fare operazioni sulla data, e tenendo sempre d’occhio l’orologio, utilizziamo una stringa per rappresentarla. Per il circuito abbiamo definito una classe e per i giri utilizzeremo quattro liste di Giro.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class GranPremio
{
public:
    GranPremio();
 
    Data getData() const;
    void setData(Data value);
 
    Circuito getCircuito() const;
    void setCircuito(const Circuito & value);
 
    list<Giro> & getGiriProveLibere();
    list<Giro> & getGiriProveUfficiali();
    list<Giro> & getGiriWarmUp();
    list<Giro> & getGiriGara();
 
    const list<Giro> & getGiriProveLibere() const;
    const list<Giro> & getGiriProveUfficiali() const;
    const list<Giro> & getGiriWarmUp() const;
    const list<Giro> & getGiriGara() const;
 
    // Determina il tempo finale del pilota (la somma di tutti i suoi giri)
    int calcolaTempoFinale(string pilota) const;
 
    // Determina il pilota che ha effettuato il miglior giro in gara
    string pilotaGiroRecord() const;
 
private:
    Data data;
    Circuito circuito;
    list<Giro> giriProveLibere;
    list<Giro> giriProveUfficiali;
    list<Giro> giriWarmUp;
    list<Giro> giriGara;
};

Non si badi ai metodi definiti alle linee 22-26, la loro utilità sarà spiegata nel seguito.

Non ci resta che definire una classe che rappresenti l’intero sistema (durante la correzione la presenza/assenza di questa classe fa spesso la differenza). Chiameremo questa classe FIA, dalla sigla della Federazione Italiana Automobilismo (ma anche Sistema andrebbe bene). In questa classe manterremo la lista dei Gran Premi disputati e, per nostra comodità, la lista dei piloti iscritti alla federazione (per i piloti abbiamo usato una semplice stringa, quindi avremo una lista di stringhe). Inoltre, definiamo i metodi che la seconda parte dell’esercizio ci chiede di implementare.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class FIA
{
public:
    FIA();
 
    list<string> & getPiloti();
    list<GranPremio> & getGranPremi();
 
    const list<string> & getPiloti() const;
    const list<GranPremio> & getGranPremi() const;
 
    // esercizio b.1: Dato un gran premio determinare il pilota vincitore
    string determinaVincitore(const GranPremio & gp) const;
 
    // esercizio b.2: Determinare il nome del pilota che detiene il giro record 
    //                in gara per un dato gran premio
    string determinaPilotaGiroRecord(const GranPremio & gp) const;
 
private:
    list<string> piloti;
    list<GranPremio> granPremi;
};

L’esercizio b.1 ci chiede di implementare un metodo che dato un Gran Premio determini il pilota vincitore. Questo metodo è determinaVincitore(), che riceve proprio una istanza di GranPremio e restituisce una stringa, ovvero il pilota vincitore. L’implementazione sarà la seguente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

string 
FIA::determinaVincitore(
        const GranPremio & gp) const
{
    // inizializza il vincitore al primo pilota
    list<string>::const_iterator it = piloti.begin();
    string vincitore = *it;
 
    // calcola il tempo finale del vincitore (corrente)
    int tempoVincitore = gp.calcolaTempoFinale(*it);
    it++;
 
    // per ogni pilota
    for(; it != piloti.end(); it++)
    {
        // calcola il suo tempo finale
        int tempo = gp.calcolaTempoFinale(*it);
 
        // se il tempo è inferiore a quello del vincitore (corrente)
        if(tempo < tempoVincitore)
        {
            // abbiamo un nuovo vincitore
            vincitore = *it;
            tempoVincitore = tempo;
        }
    }
 
    return vincitore;
}

Iteriamo sui piloti iscritti alla federazione e inizializziamo il vincitore al primo di questi, calcolando il suo tempo totale di gara tramite il metodo calcolaTempoFinale(string) di Gran Premio (che DOBBIAMO ancora implementare). Per ogni altro pilota andiamo quindi a verificare se il tuo tempo totale di gara è minore di quello del vincitore; in questo caso aggiorniamo la variabile vincitore. Occorre precisare che inizializzare la variabile tempoVincitore a 0 sarebbe un errore, poiché stiamo cercando il minimo fra numeri positivi (e quindi lo 0 è sicuramente minore di tutti questi valori). Potrebbe andare bene inizializzare la variabile a MAX_INT.

L’implementazione del metodo ausiliario è la seguente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int
GranPremio::calcolaTempoFinale(
        string pilota) const
{
    // inizializza il tempo a ZERO
    int tempo = 0;
 
    // per ogni giro del GP
    for(list<Giro>::const_iterator it = giriGara.begin(); 
        it != giriGara.end(); it++)
        // se il giro è del pilota
        if(it->getVettura().getPilota() == pilota)
            // aggiungi il tempo del giro al tempo totale del pilota
            tempo += it->getTempo();
 
    return tempo;
}

Niente di strabiliante. Inizializziamo il tempo totale a 0 (visto che dobbiamo fare una somma). Quindi iteriamo su tutti i giri di gara e sommiamo i tempi del pilota dato in input.

Per l’esercizio b.2 dobbiamo implementare un metodo che dato un Gran Premio determini il pilota che detiene il giro record in gara. Definiamo allora il metodo determinaPilotaGiroRecord() che riceve in input un Gran Premio e restituisce una stringa rappresentante il pilota che ha eseguito nel minor tempo un giro di gara.

1
2
3
4
5
6
7
8

string 
FIA::determinaPilotaGiroRecord(
        const GranPremio & gp) const
{
    // visto che bisogna accedere a molte strutture di GranPremio,
    // meglio implementare il metodo in quella classe
    return gp.pilotaGiroRecord();
}

Come specificato nel commento, deleghiamo il lavoro sporco alla classe GranPremio.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

string
GranPremio::pilotaGiroRecord() const
{
    // inizializza il giro record al primo giro del GP
    list<Giro>::const_iterator it = giriGara.begin();
    list<Giro>::const_iterator record = it;
    it++;
 
    // per ogni giro del GP
    for(; it != giriGara.end(); it++)
        // se il tempo è inferiore
        if(it->getTempo() < record->getTempo())
            // abbiamo un nuovo record
            record = it;
 
    // restituisci il pilota che ha effettuato il miglior giro
    return record->getVettura().getPilota();
}

Dobbiamo ancora una volta eseguire una ricerca di minimo. Inizializziamo il giro record al primo giro di gara e quindi iteriamo. Se troviamo un giro con tempo inferiore aggiorniamo il minimo. Alla fine restituiamo il pilota che detiene il giro record.

Tutti i requisiti della traccia sono stati soddisfatti. Possiamo quindi passare al secondo esercizio.

Esercizio 2.

Il secondo esercizio chiede di implementare, tramite l’ereditarietà, una coda di interi dal prodotto limitato, ovvero una coda di interi nella quale il prodotto degli elementi è sempre inferiore a un intero dato.

Senza sforzarci troppo con la fantasia, chiameremo la nostra classe CodaIntProdottoLimitato. Ora dobbiamo scegliere da quale classe ereditare e in che modo. Possiamo estendere vector<int> o supporre che esista una classe CodaInt (magari anche implementarla). Nel primo caso dovremmo ereditare in modo privato e define i metodi utili per una coda, ovvero un metodo per l’inserimento e uno per l’estrazione. Se optiamo per la seconda scelta, invece, ereditiamo in modo pubblico perché i metodi della nuova classe saranno quelli di una coda.

La classe che estende vector<int> è la seguente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class CodaIntProdottoLimitato : private vector<int>
{
public:
    CodaIntProdottoLimitato(int aMaxProd) : vector<int>() { maxProd = aMaxProd };
 
    void inserisci(int x);
    int preleva();
 
private:
    int maxProd;
 
    // calcola il prodotto degli interi presenti nella coda
    int calcolaProdotto() const;
};
 
void
CodaIntProdottoLimitato::inserisci(
        int x)
{
    if(calcolaProdotto() * x < maxProd)
        vector<int>::insert(vector<int>::end(), x);
}
 
int
CodaIntProdottoLimitato::preleva()
{
    assert(size() > 0);
 
    int x = at(0);
    vector<int>::erase(vector<int>::begin());
    return x;
}
 
int
CodaIntProdottoLimitato::calcolaProdotto() const
{
    int prod = 1;
    for(int i = 0; i < size(); i++)
        prod *= at(i);
    return prod;
}

Si noti che nella funzione che calcola il prodotto degli elementi nella coda la variabile viene inizializzata a 1 e non a 0. Questo perché l’elemento neutro rispetto al prodotto è 1.

Se invece optiamo per la seconda scelta avremo una classe CodaInt, come per esempio la seguente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class CodaInt : private vector<int>
{    
public:
    CodaInt() : vector<int>() {}
 
    void inserisci(int x) { vector<int>::insert(vector<int>::end(), x); }
    int preleva();
 
    int size() const { return vector<int>::size(); }
 
 
 
protected:
    int at(int index) const { return vector<int>::at(index); }
};
 
int
CodaInt::preleva()
{
    assert(size() > 0);
 
    int x = at(0);
    vector<int>::erase(vector<int>::begin());
    return x;
}

La classe CodaInt definisce il metodo at(int), necessario per calcolare il prodotto degli elementi nella coda. Senza questo metodo la classe CodaInt non sarebbe una buona classe base per CodaIntProdottoLimitato. Infatti, non è sufficiente memorizzare il prodotto attuale e aggiornarlo a ogni inserimento/rimozione perché il prodotto è un’operazione invertibile solo in assenza dello 0 (che però è un intero, e quindi potrebbe trovarsi nella coda).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class CodaIntProdottoLimitato : public CodaInt
{
public:
    CodaIntProdottoLimitato(int maxProd) : CodaInt(), maxProd(max) {}
 
    // in una coda dal prodotto limitato il prodotto degli interi
    // non deve eccedere maxProd, quindi bisogna ridefinire il
    // metodo per l'inserimento (per quello di rimozione va bene
    // l'implementazione della classe CodaInt).
    void inserisci(int x);
 
private:
    int maxProd;
 
    // calcola il prodotto degli interi presenti nella coda
    int calcolaProdotto() const;
};
 
void
CodaIntProdottoLimitato::inserisci(
        int x)
{
    if(calcolaProdotto() * x < maxProd)
        CodaInt::inserisci(x);
}
 
int
CodaIntProdottoLimitato::calcolaProdotto() const
{
    int prod = 1;
    for(int i = 0; i < size(); i++)
        prod *= at(i);
    return prod;
}