Elabore un programa en C++ que facilite repartir elementos cuantificables entre grupos. Existen muchos escenarios en los que este programa resulta útil. Algunos ejemplos:
-
Repartir estudiantes en grupos que competirán tirando de la soga (gana el equipo que tira de la soga con más fuerza arrastrando a su oponente). Muchas veces los equipos se integran conforme llegan los participantes, pero en competencias serias, idealmente deberían estar integrados por personas con pesos similares. En este caso, los competidores son los elementos cuantificables por su peso.
-
Repartir productos (golosinas, juguetes, ropa, …) entre infantes, procurando que cada infante reciba un paquete de valor (precio) igual. En este caso, los productos se cuantifican por su precio.
-
Distribuir cajas por su volumen en grupos que serán almacenados en bodegas o transportados en contenedores. En este caso, las cajas se cuantifican por su volumen (en metros cúbicos).
El siguiente ejemplo de ejecución reparte competidores para tirar de la soga (indicado por la palabra soga en la primera línea de la entrada) entre tres grupos (indicado por el 3 en la primera línea). En las subsecuentes líneas de la entrada estándar vendrán las personas competidoras que han de repartirse, cada una con su nombre y su peso en kilogramos.
Ejemplo de entrada 1:
soga 3
Luis 82.5
Marta 85.3
Carlos 65.0
Ana 90.0
Jorge 75.5
Elena 48.0
Pedro 88.0
Sonia 62.0
Ejemplo de salida 1:
Orden de llegada:
G1: 260.5
Luis: 82.5
Ana: 90
Pedro: 88
G2: 222.8
Marta: 85.3
Jorge: 75.5
Sonia: 62
G3: 113
Carlos: 65
Elena: 48
Orden descendente:
G1: 234.5
Ana: 90
Luis: 82.5
Sonia: 62
G2: 211.5
Pedro: 88
Jorge: 75.5
Elena: 48
G3: 150.3
Marta: 85.3
Carlos: 65
Balanceo de carga:
G1: 158
Luis: 82.5
Jorge: 75.5
G2: 221.3
Marta: 85.3
Elena: 48
Pedro: 88
G3: 217
Carlos: 65
Ana: 90
Sonia: 62
Hay varios algoritmos para repartir elementos entre grupos. Su programa debe implementar tres de ellos. El primero es repartir por orden de llegada. En el ejemplo anterior, Luis es asignado al primer grupo. La siguiente persona en llegar, Marta, es asignada al segundo grupo. La tercera persona (Carlos) al tercer grupo. Dado que se solicitaron tres grupos, la cuarta persona (Ana) es asignada al primer grupo, la quinta (Jorge) al segundo grupo, y así sucesivamente siguiendo este patrón cíclico hasta que se acaben los elementos. Tras repartir los elementos, su programa debe imprimir en la salida estándar el nombre del algoritmo, seguido de cada grupo, y los elementos que en ellos quedaron. Para cada grupo, indique la suma de sus elementos cuantificados.
El segundo algoritmo es repartir en orden descendente los elementos cuantificables entre los grupos. Primero se ordenan descendentemente los elementos cuantificables. En el ejemplo de entrada anterior, el orden sería: Ana (90), Pedro (88), Marta (85.3), Luis (82.5), Jorge (75.5), Carlos (65), Sonia (62), y Elena (48). Luego se reparten entre los grupos circularmente, de la misma forma que el algoritmo de repartir por orden de llegada. En el ejemplo, Ana se asigna al grupo 1, Pedro al grupo 2, Marta al 3; Luis al grupo 1, Jorge al 2, y así sucesivamente. Tras repartir los elementos, su programa imprime en la salida estándar el nombre del algoritmo, seguido de cada grupo resultante, la suma de sus elementos cuantificables, y la lista de elementos en cada grupo. Nótese que en el ejemplo anterior, este algoritmo creó grupos más equilibrados en peso para tirar de la soga, que los grupos que hizo el algoritmo de orden de llegada.
El tercer algoritmo es repartir con balanceo de carga. Los elementos cuantificados se reparten en orden de llegada, pero el elemento es asignado al grupo que tenga la suma menor. Si hay varios grupos con la misma suma, se asigna al grupo con índice menor. En el ejemplo anterior, cuando Luis llega, los tres grupos están vacíos, con suma de pesos 0.0 cada uno, representado por [0, 0, 0], por tanto se asigna al grupo 1 por tener el índice menor. Cuando Marta llega, los grupos 2 y 3 tienen la suma menor: [82.5, 0, 0], por lo que se asigna al grupo 2. Cuando Carlos llega, es asignado al grupo 3 por tener la suma menor: [82.5, 85.3, 0]. Cuando Ana llega, de los tres grupos [82.5, 85.3, 65], el tercero tiene la suma menor y Ana se les une. Cuando Jorge llega, los grupos suman [82.5, 85.3, 155], y se une al grupo 1 por tener la suma mínima de pesos; y así sucesivamente. Después de repartir los elementos cuantificables, se imprimen los grupos en la salida estándar de forma similar a los anteriores. Nótese en la salida estándar que este algoritmo produjo el mejor balanceo de pesos.
Para que su solución sea reutilizable y fácil de extender a muchos contextos, siga estos lineamientos:
-
[15%] Elabore un diagrama de clases UML de su solución. Use nombres significativos, clases abstractas y concretas, atributos sin violación de encapsulamiento. Distinga los métodos normales de los abstractos. Relacione las clases.
-
[20%] Provea un programa principal y una clase controladora. La clase controladora debe ser fácil de adaptar para repartir colecciones de cualquier tipo de objetos cuantificables, usando cualquier tipo de algoritmo repartidor. Para ilustrar su uso, permita que al leer en la entrada estándar la palabra
sogao la palabracajas, cree objetos cuantificables para el juego de tirar de la soga o repartir cajas por volumen, respectivamente. La clase controladora debe administrar la colección de elementos cuantificables haciendo buen uso de la memoria, sin provocar accesos inválidos ni fugas de memoria. Provea métodos para distribuir los elementos cuantificables en la cantidad de grupos indicados en la entrada estándar. Sus métodos usarán programación genérica, polimórfica, o ambas, de acuerdo a su solución del punto 5. La tabla de abajo muestra un ejemplo de ejecución que reparte cajas en 2 grupos. Nota: Su solución del punto 5 debe impedir que la clase controladora (u otra clase) "explote" si se agrega en el futuro una cantidad enorme de tipos de elementos cuantificables, o si se agrega una cantidad enorme de algoritmos de reparto, o ambas. -
[15%] Clase base abstracta para representar los elementos cuantificables, con un método para obtener una representación numérica (real) del elemento, algo como
getValor(). Provea sobrecargas de los operadores de flujo>>y<<, además de otros métodos auxiliares polimórficos para lectura e impresión. Sobrecargue eloperator<()para comparar elementos cuantificables por sus cantidades. Agregue una función comparadora que use este operador para comparar punteros a objetos cuantificables. -
[10%] Provea dos clases concretas de elementos cuantificables. La primera, para el juego de tirar de la cuerda, donde los participantes conocen su nombre y peso, y se miden por su peso. La segunda, para representar cajas cuantificables por volumen en metros cúbicos. Cada caja tiene un número natural identificador y su volumen.
-
[20%] Provea una solución escalable y generalizable para representar algoritmos repartidores de objetos cuantificables, con el uso ya sea de: polimorfismo, programación genérica o ambos. Su solución debe ser capaz de recibir un arreglo dinámico de elementos cuantificables y la cantidad de grupos que se quieren crear con ellos. Su solución los reparte entre grupos. Provea también una clase para representar grupos de elementos cuantificables, capaz de calcular la suma de sus elementos e imprimirse con el
operator<<. -
[20%] Implementa tres algoritmos repartidores: repartidor por orden de llegada, repartidor en orden descendente, y repartidor con balanceo de carga.
Ejemplo de entrada 2:
cajas 2
345 50
101 0.5
777 70
222 4.5
Ejemplo de salida 2:
Orden de llegada:
G1: 120
Caja 345: 50
Caja 777: 70
G2: 5
Caja 101: 0.5
Caja 222: 4.5
Orden descendente:
G1: 74.5
Caja 777: 70
Caja 222: 4.5
G2: 50.5
Caja 345: 50
Caja 101: 0.5
Balanceo de carga:
G1: 54.5
Caja 345: 50
Caja 222: 4.5
G2: 70.5
Caja 101: 0.5
Caja 777: 70