Introducción a la programación
Méritos 2-07-2018
La UEx va a sacar unas becas de colaboración el próximo curso y necesita una aplicación para gestionar los méritos de las personas
que se presenten y así poder calcular fácilmente quién obtiene las becas en función del baremos de puntos fijado para cada mérito.
Ayúdanos implementando algunas operaciones del TAD. Queremos almacenar la información de los méritos de las personas que se
presenten, agrupados por categoría.
Primero se ha definido un TAD Mérito que gestiona la información de un dato de una persona: el identificador de la persona (un
entero), la categoría del mérito (cursillo, nota, beca, premio, etc.; una cadena) y los puntos que le corresponden a ese mérito (un real).
Las cabeceras de las operaciones del TAD Mérito son las siguientes:
// Crea un mérito con el identificador, la categoría y los puntos dados
void nuevo (int id, string categoria, float puntos, Merito &m);
// Incrementa los puntos con el valor p dado en el mérito m
void incrementar (Merito &m, float p)
// devuelve el identificador del mérito m
int obtenerIdentificador (Merito m );
// devuelve la categoría del mérito m
string obtenerCategoria (Merito m );
// devuelve los puntos del mérito m
float obtenerPuntos (Merito m );
Sabemos que, como mucho, habrá información sobre 3000 méritos. (Una persona puede tener méritos en distintas categorías.)
El TAD Gestión con las operaciones que queremos implementar es el siguiente:
TAD Gestion es Iniciar, Insertar, TotalPuntos, Mayor, Eliminar
Operaciones
Iniciar salida Gestion
efecto Inicia la estructura.
Insertar (G: Gestion, Id: entero, C: string, P: real)
modifica Gestion
efecto Añade un nuevo mérito de la persona con identificador Id, de la categoría
C con P puntos. Si ya existía un mérito de esa persona en esa categoría, incrementa
los puntos; si no, inserta ese mérito en la estructura. Podemos suponer que la
estructura no estará llena.(Es posible que una persona tenga méritos en varias
categorías.)
TotalPuntos (G: Gestion, Id: entero) salida real
efecto Devuelve el total de puntos de la persona Id en todas las categorías.
Mayor (G: Gestion ) salida entero, string
efecto Devuelve el identificador de la persona y la categoría del mérito con la
puntuación más alta. Podemos suponer que habrá, como mínimo, un mérito en la
estructura. Si hay varios con la misma cantidad, devuelve los datos de uno
cualquiera.
Eliminar (G: Gestion, C: string) modifica Gestion
efecto Elimina la información de todos los méritos de la categoría C.
Podemos suponer que el TAD Mérito ya está implementado y que todas las operaciones tienen coste O(1).
Una posible solución
const int MAX = 3000;
typedef Merito TVector[MAX];
struct Gestion {
TVector vector;
int ocupadas;
};
// Tamaño del problema: tamaño del vector
// Complejidad: O(1)
void iniciar ( Gestion &g ) {
[Link] = 0;
}
Introducción a la programación
// Complejidad: O(n)
void insertar ( Gestion &g, int id, string categoria, float puntos ) {
int i;
bool enc;
Merito m;
enc = false;
i=0;
while (i < [Link] && !enc) {
if ( obtenerIdentificador ( [Link][i] ) == id &&
obtenerCategoria ( [Link][i] ) == categoria ) {
incrementar ( [Link][i], puntos );
enc = true;
}
else
i = i+1;
}
if ( !enc ) {
nuevo (id, categoria, puntos, m);
[Link][[Link]] = m;
[Link]++;
}
}
// Complejidad: O(n)
float totalPuntos ( Gestion g, int id ) {
int i;
float total;
total = 0;
for ( i = 0; i < [Link]; i++ )
if ( obtenerIdentificador ( [Link][i] ) == id )
total = total + obtenerPuntos ( [Link][i] );
return total;
}
// Complejidad: O(n)
void mayor ( Gestion g, int &id, string &categoria ) {
int i;
float puntosMayor;
int posMayor;
puntosMayor = obtenerPuntos ( [Link][0] );
posMayor = 0;
for ( i = 1; i < [Link]; i++ ) {
if ( obtenerPuntos ( [Link][i] ) > puntosMayor ) {
puntosMayor = obtenerPuntos ( [Link][i] );
posMayor = i;
}
}
id = obtenerIdentificador ( [Link][posMayor] );
categoria = obtenerCategoria ( [Link][posMayor] );
}
Introducción a la programación
// Complejidad: O(n)
void eliminar ( Gestion &g, string categoria ) {
int cuantos;
int i;
cuantos = 0;
for ( i = 0; i < [Link]; i++ ) {
if ( obtenerCategoria ( [Link][ i ] ) == categoria ) {
cuantos = cuantos + 1;
}
else {
[Link] [ i - cuantos ] = [Link] [ i ];
}
}
[Link] = [Link] - cuantos;
}