Programmazione a oggetti – Appello straordinario Aprile 2010

In questo articolo mostriamo una possibile soluzione all’appello straordinario di Aprile 2010 del corso di Programmazione a oggetti del corso di laurea in informatica dell’Università della Calabria.

Iniziamo col riportare i file forniti in sede d’esame, contenenti la descrizione del problema e delle funzioni da implementare. In particolare, il file Voto.h definisce una classe per modellare l’espressione di una preferenza di un elettore in una ipotetica elezione.

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
42
43
44
45
46
47
// File: Voto.h
 
#ifndef VOTO_H_
#define VOTO_H_
 
#include<string>
using namespace std;
 
enum Tipo { SENATO = 0, CAMERA, REGIONE };
 
/*
 
Un oggetto di tipo Voto rappresenta l'espressione di una preferenza di un elettore
su una delle tre possibili schede: SENATO, CAMERA e REGIONE.
 
Se il flag "nullo" e' true, allora il voto e' nullo.
 
Se "coalizione" e' la stringa vuota, allora il voto equivale ad una scheda bianca
(chiaramente cio' vale solo se il flag "nullo" e' false; se fosse true la scheda
sarebbe nulla indipendentemente dal campo "coalizione").
 
Questa classe e' gia' implementata e non necessita di modifiche.
Eventuali metodi accessori sono comunque ammessi.
 
*/
class Voto
{
private:
	string coalizione;
	Tipo tipo;
	bool nullo;
 
public:
	Voto(string ="", Tipo = SENATO, bool = false);
 
	string dammiCoalizione() const;
	Tipo dammiTipo() const;
	bool dimmiSeNullo() const;
 
	void impostaCoalizione(string);
	void impostaTipo(Tipo);
	void impostaNullo(bool);
 
	bool operator==(const Voto&) const;
};
 
#endif

La classe Voto è già implementata e ci limitiamo a riportarla di seguito.

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
// File: Voto.cpp
 
#include "Voto.h"
 
Voto::Voto(string c, Tipo t, bool n):coalizione(c), tipo(t), nullo(n)
{}
 
string Voto::dammiCoalizione() const
{
	return coalizione;
}
 
Tipo Voto::dammiTipo() const
{
	return tipo;
}
 
bool Voto::dimmiSeNullo() const
{
	return nullo;
}
 
void Voto::impostaCoalizione(string c)
{
	coalizione = c;
}
 
void Voto::impostaTipo(Tipo t)
{
	tipo = t;
}
 
void Voto::impostaNullo(bool t)
{
	nullo = t;
}
 
bool Voto::operator==(const Voto& o) const
{
	return coalizione == o.coalizione && tipo == o.tipo && nullo == o.nullo;
}

Nel file Urna.h troviamo invece la definzione di una classe che modella un’urna elettorale. L’esercizio consiste nell’implementare quattro metodi di questa classe.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
// File: Urna.h
 
#ifndef URNA_H
#define URNA_H
 
#include "Voto.h"
#include <cstdlib>
#include <iostream>
#include <list>
using namespace std;
 
/* 
 
Questa classe modella un'URNA contente solo schede votate.
Assumiamo che un oggetto di tipo Voto rappresenti una scheda votata,
che puo' essere anche nulla o bianca (come specificato nella documentazione
della classe Voto).
Quindi, l'urna sara' rappresentata da una lista di istanze della classe Voto
(nello specifico, la lista "voti").
 
I voti sono esattamente di 3 tipi,
come specificato nella classe Voto (senato, camera e regione).
 
Ogni elettore *deve* votare tutte e tre le schede, ma l'ordine in cui 
le tre schede votate (ovvero i tre oggetti di tipo Voto) vengono 
inserite nell'urna e' a sua discrezione.
Di conseguenza, dopo che un elettore ha votato e inserito tutte
e tre le schede nell'urna, la dimensione dell'urna sara' un multiplo di 3
(nello specifico, 3 moltiplicato il numero di elettori che hanno votato).
 
Ad esempio, dopo quattro votanti, il tipo delle schede presenti nell'urna 
potrebbe essere il seguente:
 
Urna = [CAMERA,     REGIONE,    SENATO, 
        SENATO,     CAMERA,     REGIONE, 
        SENATO,     REGIONE,    CAMERA,
        CAMERA,     SENATO,     REGIONE ]
 
Si richiede di implementare nel file Urna.cpp
tutti i metodi di questa classe ad eccezione del costruttore
(la cui implementazione e' data e non puo' essere modificata).
 
 */
class Urna // questa riga e' corretta NON MODIFICARE
{
 
private:
    // Le schede dell' URNA sono memorizzate in una lista.
    list<Voto> voti;
 
public:
 
    /*
 
    Questo metodo aggiunge una scheda all'urna solo se non viola la suddetta struttura dell'urna.
    In questo caso, il metodo ritorna true.
    Altrimenti, se la proprieta' non e' soddisfatta, restituisce false senza inserire la scheda.
 
    Ad esempio, se il tipo delle schede nell'urna e' il seguente:
 
    Urna = [SENATO,     CAMERA,     REGIONE,
            REGIONE ]
 
    il metodo restituira' true solo se la scheda e' di tipo CAMERA o SENATO.
 
    */
    bool aggiungiVoto(Voto v);
 
    /*
 
    Dato un Tipo, il metodo restituisce true se e solo se il numero di schede nulle di quel tipo
    e` maggiore o uguale al numero di schede nulle degli altri tipi (presi singolarmente).
    Ad esempio, se l'urna contenesse i seguenti voti:
 
    Urna = [("Coal1", CAMERA,  true),  ("Coal1", REGIONE, false), ("Coal2", SENATO, false), 
            ("Coal1", REGIONE, true),  ("Coal2", CAMERA,  false), ("",      SENATO, false), 
            ("Coal2", CAMERA,  true),  ("Coal1", REGIONE, false), ("Coal2", SENATO, false) ]
 
    il metodo "maggioranzaVotiNulli(CAMERA)"  restituirebbe true  (due nulle),
    il metodo "maggioranzaVotiNulli(REGIONE)" restituirebbe false (una nulla),
    il metodo "maggioranzaVotiNulli(SENATO)"  restituirebbe false (zero nulle).
 
    */
    bool maggioranzaVotiNulli(Tipo t);
 
    /*
 
    Dato un Tipo, restituire la lista di coalizione con piu' voti per quel Tipo.
    Se piu' di una coalizione risulta vincente, la lista deve essere costruita
    dando priorita' alla coalizione che per prima ha preso un voto valido.
    Ad esempio, se l'urna contenesse i seguenti voti:
 
    Urna = [("Coal1", CAMERA,  false), ("Coal1", REGIONE, false), ("Coal2", SENATO, false), 
            ("Coal1", REGIONE, true),  ("Coal2", CAMERA,  false), ("",      SENATO, true), 
            ("Coal2", CAMERA,  false), ("Coal1", REGIONE, false), ("Coal2", SENATO, false), 
            ("",      SENATO,  false), ("Coal1", REGIONE, true),  ("Coal1", CAMERA, true),
            ("Coal1", CAMERA,  false), ("Coal1", REGIONE, false), ("Coal2", SENATO, false) ]
 
    il metodo "coalizioniVincenti(CAMERA)" restituirebbe ["Coal1", "Coal2"] in quest'ordine. 
    Infatti, "Coal1" ha due voti validi (righe 1 e 5; la riga 4 ha un voto nullo).
    Allo stesso modo, "Coal2" ha due voti validi (righe 2 e 3).
    "Coal1" precede "Coal2" nella lista restituita in quanto il primo voto valido
    di "Coal1" e' sulla riga 1, mentre per "Coal2" e' sulla riga 2.
 
     */
    list<string> coalizioniVincenti(Tipo t);
 
    /*
 
    Dato un Tipo, restituire la lista di coalizione con piu' voti consecutivi per quel Tipo.
    Se piu' di una coalizione soddisfa la condizione, la lista deve essere costruita
    dando priorita' alla coalizione che per prima ha preso un voto valido.
    Ad esempio, se l'urna contenesse i seguenti voti:
 
    Urna = [("Coal1", CAMERA,  false), ("Coal1", REGIONE, false), ("Coal2", SENATO, false), 
            ("Coal1", REGIONE, true),  ("Coal2", CAMERA,  false), ("",      SENATO, true), 
            ("Coal2", CAMERA,  false), ("Coal1", REGIONE, false), ("Coal2", SENATO, false), 
            ("",      SENATO,  false), ("Coal1", REGIONE, true),  ("Coal1", CAMERA, true),
            ("Coal1", CAMERA,  false), ("Coal1", REGIONE, false), ("Coal2", SENATO, false) ]
 
    il metodo "coalizioniConSequenzePiuLunghe(CAMERA)" restituirebbe ["Coal2"]. 
    Infatti, "Coal1" compare in due sequenze di lunghezza 1: la prima in riga 1, 
    la seconda in riga 5 (da notare che il voto per "Coal1" in riga 4 e' nullo).
    "Coal2", invece, compare in una sola lista di lunghezza 2: da riga 2 a riga 3.
    Non essendoci altre coalizzioni votate alla CAMERA, "Coal2" risulta essere
    la sola coalizione con la sequenza piu' lunga di voti consecutivi alla CAMERA.
 
    */
 
    list<string> coalizioniConSequenzePiuLunghe(Tipo t);
 
    inline list<Voto>& getContent();
};
 
list<Voto>& Urna::getContent()
{
    return voti;
}
 
#endif

Urna::aggiungiVoto(Voto)

La struttura dell’urna impone che ogni tripla di voti sia composta da un voto per il Senato, uno per la Camera e uno per la Regione, in un ordine qualsiasi. Quindi, se il numero di voti nell’urna è un multiplo di 3, quello che stiamo inserendo è un voto di un nuovo elettore; in questo caso non dovremo controllare nulla. Diversamente, se il numero di voti nell’urna diviso 3 da resto 1, quella che stiamo inserendo è la seconda scheda di un elettore; in questo caso dovremo verificare che il tipo del voto inserito sia diverso da quello precedentemente inserito. L’ultimo caso possibile è che il numero di voti nell’urna diviso 3 da resto 2, ovvero l’elettore sta inserendo il suo terzo voto; dobbiamo quindi verificare che il tipo del voto inserito sia diverso dagli ultimi due voti presenti nell’urna.

Di seguito sono riportate due possibili implementazioni del metodo. La prima fa uso della classe list::const_iterator per attraversare la lista e trovare gli ultimi due voti presenti nell’urna. La seconda implementazione ottiene lo stesso risultato in modo più efficiente facendo uso della classe list::const_reverse_iterator (iteratore all’inverso, dalla fine all’inizio).

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
bool Urna::aggiungiVoto(Voto v)
{
    // Se non e' un voto di un nuovo elettore, allora controlliamo il tipo degli altri voti espressi dall'elettore
    if(voti.size() % 3 >= 1)
    {
        // Troviamo gli ultimi due voti
        Voto ultima, penultima;
        for(list<Voto>::const_iterator it = voti.begin(); it != voti.end(); it++)
        {
            penultima = ultima;
            ultima = *it;
        }
 
        // Non possiamo aggiungere un voto dello stesso tipo dell'ultimo voto presente nell'urna
        if(v.dammiTipo() == ultima.dammiTipo())
            return false;
 
        // Se questa e' la terza scheda di un elettore eseguiamo il controllo anche per il penultimo voto
        if(voti.size() % 3 == 2 && v.dammiTipo() == penultima.dammiTipo())
            return false;
    }
 
    voti.push_back(v);
    return true;
}
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
bool Urna::aggiungiVoto(Voto v)
{
    // Se non e' un voto di un nuovo elettore, allora controlliamo il tipo degli altri voti espressi dall'elettore
    if(voti.size() % 3 >= 1)
    {
        list<Voto>::const_reverse_iterator it = voti.rbegin();    
        Voto ultima = *it, penultima;
 
        // Non possiamo aggiungere un voto dello stesso tipo dell'ultimo voto presente nell'urna
        if(v.dammiTipo() == ultima.dammiTipo())
            return false;
 
        // Se questa e' la terza scheda di un elettore eseguiamo il controllo anche per il penultimo voto
        if(voti.size() % 3 == 2)
        {
            it++;
            penultima = *it;
            if(v.dammiTipo() == penultima.dammiTipo())
                return false;
        }
    }
 
    voti.push_back(v);
    return true;
}

Urna::maggioranzaVotiNulli(Tipo)

Questo metodo ritorna true se e solo se il numero di voti nulli per un dato tipo è maggiore o uguale del numero di voti nulli degli altri tipi, presi singolarmente. Una semplice implementazione consiste nel contare il numero di voti nulli di ogni tipo e quindi nel verificare la condizione. Visto che Tipo è un enumerato che associa le costanti SENATO, CAMERA e REGIONE a 0, 1 e 2, rispettivamente, possiamo usare un array di 3 elementi per contare i voti nulli di ogni tipo.

1
2
3
4
5
6
7
8
9
10
11
12
bool Urna::maggioranzaVotiNulli(Tipo t)
{
    int count[] = {0,0,0};  // equivale a: int count[3]; count[SENATO] = count[CAMERA] = count[REGIONE] = 0;
 
    // Contiamo i voti nulli per ogni tipo
    for(list<Voto>::const_iterator it = voti.begin(); it != voti.end(); it++)
        if(it->dimmiSeNullo())
            count[it->dammiTipo()]++;
 
    // Ritorniamo true se count[t] è maggiore o uguale di tutti gli altri
    return count[t] >= count[0] && count[t] >= count[1] && count[t] >= count[2];
}

Urna::coalizioniVincenti(Tipo)

Questo metodo deve restituire la lista delle coalizioni vincenti per un dato tipo. Dobbiamo quindi contare quanti voti ha preso ogni coalizione e costruire una lista delle coalizioni con più voti.

Per contare i voti ottenuti da ogni coalizione possiamo eseguire un doppio ciclo sull’urna: il primo per individuare una coalizione, il secondo per contare i voti ottenuti da quella coalizione da quel momento in poi. Per costruire la lista delle coalizioni vincenti, invece, possiamo adattare facilmente un algoritmo per la ricerca di massimo. Questa soluzione è implementata di seguito.

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
list<string> Urna::coalizioniVincenti(Tipo t)
{
    list<string> vincenti;
    int max = 0;
 
    // Iteriamo sui voti presenti nell'urna
    for(list<Voto>::const_iterator it = voti.begin(); it != voti.end(); it++)
    {
        // Se il voto e' valido e del tipo richiesto, allora contiamo i voti per questa coalizione
        if(it->dammiTipo() == t && !it->dimmiSeNullo() && it->dammiCoalizione() != "")
        {
            int count = 0;
 
            // Contiamo tutti i voti presenti nell'urna a partire da it
            for(list<Voto>::const_iterator it2 = it; it2 != voti.end(); it2++)
                // Se il voto e' valido, dello stesso tipo e coalizione di it, allora incrementa count
                if(it2->dammiTipo() == t && !it2->dimmiSeNullo() && it2->dammiCoalizione() != it->dammiCoalizione())
                    count++;
 
            // Se questa coalizione ha preso piu' voti di tutti (finora)
            if(count > max)
            {
                // Abbiamo un nuovo massimo
                max = count;
 
                // Quindi la lista dovra' contenere solo questa coalizione
                vincenti.erase(vincenti.begin(), vincenti.end());   // equivale a: vincenti = list<string>();
                vincenti.push_back(it->dammiCoalizione());
            }
            // Se invece questa coalizione ha il massimo dei voti a parimerito di altre coalizioni
            else if(count == max)
                // Aggiungiamo la coalizione alla lista
                vincenti.push_back(it->dammiCoalizione());
        }
    }
 
    return vincenti;
}

Un’implementazione più efficiente può essere la seguente, nella quale prima costruiamo un vettore di coalizioni con i rispettivi voti validi ottenuti, e in seguito eseguiamo la ricerca di massimo. Quest’implementazione è più efficiente di quella precedentemente esposta (lineare rispetto a quadratica). Tuttavia è più complessa. Ai fini dell’esercizio, scegliere l’una o l’altra soluzione è indifferente.

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
list<string> Urna::coalizioniVincenti(Tipo t)
{
	vector<string> coalizioni;
	vector<int> numPref;
 
	for(list<Voto>::const_iterator it = voti.begin(); it != voti.end(); it++)
	{
		Voto v = *it;
		if(v.dammiTipo() == t && !v.dimmiSeNullo() && v.dammiCoalizione() != "")
		{
			bool trovato = false;
			for(int i = 0; i < coalizioni.size(); i++)
				if(coalizioni[i] == v.dammiCoalizione())
				{
					numPref[i]++;
					trovato = true;
				}
 
			if(!trovato)
			{
				coalizioni.push_back(v.dammiCoalizione());
				numPref.push_back(1);
			}
 
		}
	}
 
    list<string> vincenti;
	int max = 0;
	for(int i = 0; i < coalizioni.size(); i++)
		if(numPref[i] > max)
		{
			max = numPref[i];
			vincenti.erase(vincenti.begin(), vincenti.end());
			vincenti.push_back(coalizioni[i]);
		}
		else if(numPref[i] == max)
			vincenti.push_back(coalizioni[i]);
 
	return vincenti;
}

Urna::coalizioniConSequenzePiuLunghe(Tipo)

Questo metodo è del tutto simile al precedente. L’unica differenza è che siamo interessati alle coalizioni con il maggior numero di voti consecutivi. La prima implementazione del metodo precedente richiede solo minori modifiche per eseguire questo compito (la condizione nell’if all’interno del secondo for deve essere messa in congiunzione a quella del secondo for).

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
list<string> Urna::coalizioniVincenti(Tipo t)
{
    list<string> vincenti;
    int max = 0;
 
    // Iteriamo sui voti presenti nell'urna
    for(list<Voto>::const_iterator it = voti.begin(); it != voti.end(); it++)
    {
        // Se il voto e' valido e del tipo richiesto, allora contiamo i voti per questa coalizione
        if(it->dammiTipo() == t && !it->dimmiSeNullo() && it->dammiCoalizione() != "")
        {
            int count = 0;
 
            // Contiamo tutti i voti consecutivi presenti nell'urna a partire da it
            for(list<Voto>::const_iterator it2 = it; 
                    it2 != voti.end() && it2->dammiTipo() == t && 
                    !it2->dimmiSeNullo() && it2->dammiCoalizione() != it->dammiCoalizione(); 
                    it2++)
                count++;
 
            // Se questa coalizione ha preso piu' voti di tutti (finora)
            if(count > max)
            {
                // Abbiamo un nuovo massimo
                max = count;
 
                // Quindi la lista dovra' contenere solo questa coalizione
                vincenti.erase(vincenti.begin(), vincenti.end());   // equivale a: vincenti = list<string>();
                vincenti.push_back(it->dammiCoalizione());
            }
            // Se invece questa coalizione ha il massimo dei voti a parimerito di altre coalizioni
            else if(count == max)
                // Aggiungiamo la coalizione alla lista
                vincenti.push_back(it->dammiCoalizione());
        }
    }
 
    return vincenti;
}

Il codice dovrebbe essere pronto per la compilazione. Eventuali errori possono essere segnalati lasciando un commento al post.

5 thoughts on “Programmazione a oggetti – Appello straordinario Aprile 2010”

  1. nella seconda funzione la traccia dice:Questo metodo ritorna true se e solo se il numero di voti nulli per un dato tipo è maggiore del numero di voti nulli degli altri tipi, no maggiore uguale.

    1. Ciao. Era sbagliato il commento al metodo perché maggioranza lascerebbe intendere ‘maggiore’, ma per semplificare l’esercizio in sede d’esame è stato specificato ‘maggiore o uguale’. Ho aggiornato la pagina in accordo.

  2. Salve prof, mi stavo allenando con delle tracce sul laboratorio come questa, più o meno ci sono con tutte, ma sto avendo difficoltà in una particolare funzione:
    se la traccia mi da una città di partenza ed una di arrivo, so se queste due tratte sono collegate, ma per trovare il numero minimo di collegamenti che uniscono queste due tratte cosa bisogna fare?
    questo è il mio codice che rappresenta solo la prima parte del problema:


    list davisitare;
    set visitati;

    int cont=0;
    davisitare.push_back(p);
    while(!davisitare.empty())
    {
    string c=davisitare.front();
    davisitare.pop_front();
    for(list::iterator i=collegamenti.begin();i!=collegamenti.end();i++)
    {
    if(i->getDa()==c)
    {
    cont++;
    if(visitati.insert(i->getA()).second)
    davisitare.push_back(i->getA());
    }
    }

    }
    return cont;

Leave a Reply

Your email address will not be published. Required fields are marked *