Introducción a la programación
Banco de alimentos P2 – 19-11-15 (modificado)
El Banco de Alimentos de Cáceres está preparando una campaña de recogida de alimentos. Como quieren dar una respuesta rápida a
las necesidades de muchas personas en nuestra ciudad, te han pedido ayuda para que implementes algunos módulos que gestionen las
donaciones que llegan al almacén central.
Los voluntarios recogen alimentos en tiendas, oficinas, escuelas, centros de la universidad, etc. Cuando llenan un pequeño
contenedor, lo llevan al almacén. Vamos a ayudarles a gestionar las existencias de ese almacén.
Para cada contenedor vamos a guardar el identificador del donante (un entero), lo que pesa en kilos (un número real) y si contiene o
no alimentos perecederos que se puedan estropear (un bool).
La capacidad de almacenamiento está limitada a 2000 contenedores.
La especificación de las operaciones del TAD Banco que debes implementar es la siguiente:
TAD
Banco es iniciar, insertar, totalKilos , mayorPeso, vaciarPerecederos
Operaciones
iniciar salida Banco
efecto Inicia la estructura
insertar (B: Banco, id: entero, k: real, perec: bool)
modifica Banco
efecto Inserta la información de un nuevo contenedor. Si la estructura está llena,
no lo insertará.
totalKilos (B: Banco, id: entero) salida real
efecto Devuelve el total de kilos donados por el donante id.
mayorPeso (B: Banco) salida entero, real
efecto Devuelve el identificador del donante y el peso del contenedor más
pesado. (Podemos suponer que habrá como mínimo un contenedor en la estructura.)
vaciarPerecederos (B: Banco) modifica Banco
efecto Elimina de la estructura toda la información de los contenedores con
productos perecederos.
1. Escribe la cabecera de las funciones que necesites del TAD Contenedor y una breve descripción de lo que hacen.
2. Escribir la definición de tipos necesaria para almacenar la información de la estructura. (1 punto)
3. Implementar de forma eficiente todas las operaciones del TAD. (7.5 puntos)
Calificación de cada operación: iniciar (0.5), insertar (1), totalKilos (1.5) , mayorPeso (2), vaciarPerecederos (2.5)
4. Indicar cuál es el tamaño del problema y la complejidad de cada operación. (1.5 puntos) (La complejidad calculada solo se
considerará si la operación está bien implementada.)
Una posible solución
// Cabeceras de las funciones del TAD Contenedor que se necesitan
// Crea un nuevo contenedor a partir de los datos correspondientes
void nuevo (int donante, float peso, bool perecedero, Contenedor &c);
// devuelven el valor de cada uno de los datos que se almacenan
int obtenerDonante (Contenedor c);
float obtenerPeso (Contenedor c);
bool obtenerSiPerecedero (Contenedor c);
// TAD BANCO DE ALIMENTOS
const int MAX = 2000;
typedef Contenedor tvector[MAX];
struct Banco {
tvector vector;
int ocupadas;
};
// tamaño del problema: tamaño del vector
// iniciar O(1)
void iniciar (Banco &b) {
[Link] = 0;
}
1
Introducción a la programación
// insertar O(1)
void insertar (Banco &b, int id, float k, bool perec) {
Contenedor uno;
if ([Link] < MAX) {
nuevo(id, k, perec, uno);
[Link][[Link]] = uno;
[Link] = [Link] + 1;
}
}
// totalKilos O(n)
float totalKilos (Banco b, int id) {
float total;
int i;
total = 0;
for (i=0; i<[Link];i++) {
if (obtenerDonante([Link][i])==id) {
total = total + obtenerPeso([Link][i]);
}
}
return total;
}
// mayorPeso O(n)
int mayorPeso (Banco b, float &peso) {
int pmayor; //posición del mayor hasta ahora
int i;
pmayor = 0;
for (i=1;i<[Link]; i++) {
if (obtenerPeso([Link][i]) > obtenerPeso([Link][pmayor])) {
pmayor = i;
}
}
peso = obtenerPeso([Link][pmayor]);
return obtenerDonante([Link][pmayor]);
}
// vaciarPerecederos O(n)
void vaciarPerecederos (Banco &b) {
int cuantos;
int i;
cuantos = 0;
for(i=0; i < [Link]; i++) {
if (obtenerSiPerecedero([Link][i]) == true)
cuantos = cuantos+ 1;
else
[Link][i-cuantos] = [Link][i];
}
[Link] = [Link] - cuantos;
}