Pilas, colas, hash tables, listas y demás estructuras de dat
Publicado por David (1 intervención) el 07/05/2013 17:56:06
Hola,
Tengo que hacer una práctica para la universidad implementando estas estructuras de datos.
El enunciado es este:
Una exitosa pastelería, controlada robóticamente, ofrece n tipos distintos de tartas distinguidas por un identificador. El establecimiento dispone de una máquina que produce tartas con los n tipos de molde de manera secuencial (tipo1, tipo2, ..., tipo n, tipo 1, tipo 2, etc...) cada 2 unidades de tiempo (u.t.) por tarta, dejándolas unas encima de otras, cuando está en funcionamiento. La máquina se activa siempre y cuando sea necesario mientras se esté atendiendo un pedido.
El local también dispone de n-1 mostradores, en los que el robot puede colocar tartas de muestra de la misma manera de cómo salen de la máquina, es decir, unas encima de otras. Tanto en la máquina
como en cada uno de los mostradores se pueden acumular de esta manera n-1 tartas diferentes.
La pastelería tiene capacidad para alojar a un máximo de 2n+1 clientes y debido a su éxito no para de recibir clientes que van haciendo sus pedidos. Cada cliente tiene asociado un identificador, entero no negativo, que le diferencia del resto.
No todos los clientes son iguales, y cada uno de ellos puede esperar un tiempo determinado dentro del local para recoger su pedido que empieza a descender desde el momento que se les atiende, de manera que el robot sirve en primer lugar a aquellos clientes más impacientes, y a igual tiempo de paciencia, atiende antes a los que entraron antes a la pastelería. Cuando el pedido de un cliente es satisfecho, o bien su paciencia se ha agotado, el cliente correspondiente sale del local y entra otro nuevo.
El precio de cada tarta es de k euros pero los clientes satisfechos dan una
propina adicional dependiendo de su tiempo de paciencia restante en el
momento de recibir su pedido, calculada mediante la siguiente fórmula: Propina = tiempo de paciencia restante (tr)/ no tipos de tartas = tr/n.
El robot lleva un informe de ventas de manera que cada vez que se satisface un pedido, escribe el identificador del cliente correspondiente, el tipo de tarta que se vendió y el dinero obtenido por dicha venta, y una vez finalizada su jornada laboral apunta, en último lugar, los ingresos totales obtenidos durante el día.
Cada actualización del informe supondremos que la hace automáticamente en tiempo cero.
Bueno, vamos por partes:
1: Para los objetos tarta entiendo que tengo que utilizar el TAD pila porque lo que hace es ir apilando las tartas una encima de otra y por lo tanto la tarta accesible será siempre la última en fabricarse (LIFO).
Tanto la máquina como los mostradores serán pilas con capacidad estática n.
2. Para los objetos cliente utilizaré un ABB (Arbol Binario de Búsqueda).
El motivo es porque los clientes menos pacientes serán colocados a la izquierda y los más pacientes a la derecha. Creo que es la forma más rápida de localizar y atender a los clientes menos pacientes y de esta manera las propinas serán mayores.(sé que lo más honesto sería una cola(FIFO) pero hay que mirar por el dinero...)
3. Como las pilas son lentas de recorrer(iterador) y solo puedo acceder al último elemento insertado, he pensado en hacer una tabla hash de tamaño n (como los tipos de tarta) asignando una clave a cada tipo de tarta. La tabla hash se irá rellenando con el último elemento de cada pila.
Habrán colisiones cada vez que se recoja el mismo tipo de tarta y esto lo solucionaré con una lista enlazada a cada clave.
Esta última parte es la que más me cuesta porque no se hacer el enlace.
Alguien me puede ayudar?
Muchas gracias de antemano
Tengo que hacer una práctica para la universidad implementando estas estructuras de datos.
El enunciado es este:
Una exitosa pastelería, controlada robóticamente, ofrece n tipos distintos de tartas distinguidas por un identificador. El establecimiento dispone de una máquina que produce tartas con los n tipos de molde de manera secuencial (tipo1, tipo2, ..., tipo n, tipo 1, tipo 2, etc...) cada 2 unidades de tiempo (u.t.) por tarta, dejándolas unas encima de otras, cuando está en funcionamiento. La máquina se activa siempre y cuando sea necesario mientras se esté atendiendo un pedido.
El local también dispone de n-1 mostradores, en los que el robot puede colocar tartas de muestra de la misma manera de cómo salen de la máquina, es decir, unas encima de otras. Tanto en la máquina
como en cada uno de los mostradores se pueden acumular de esta manera n-1 tartas diferentes.
La pastelería tiene capacidad para alojar a un máximo de 2n+1 clientes y debido a su éxito no para de recibir clientes que van haciendo sus pedidos. Cada cliente tiene asociado un identificador, entero no negativo, que le diferencia del resto.
No todos los clientes son iguales, y cada uno de ellos puede esperar un tiempo determinado dentro del local para recoger su pedido que empieza a descender desde el momento que se les atiende, de manera que el robot sirve en primer lugar a aquellos clientes más impacientes, y a igual tiempo de paciencia, atiende antes a los que entraron antes a la pastelería. Cuando el pedido de un cliente es satisfecho, o bien su paciencia se ha agotado, el cliente correspondiente sale del local y entra otro nuevo.
El precio de cada tarta es de k euros pero los clientes satisfechos dan una
propina adicional dependiendo de su tiempo de paciencia restante en el
momento de recibir su pedido, calculada mediante la siguiente fórmula: Propina = tiempo de paciencia restante (tr)/ no tipos de tartas = tr/n.
El robot lleva un informe de ventas de manera que cada vez que se satisface un pedido, escribe el identificador del cliente correspondiente, el tipo de tarta que se vendió y el dinero obtenido por dicha venta, y una vez finalizada su jornada laboral apunta, en último lugar, los ingresos totales obtenidos durante el día.
Cada actualización del informe supondremos que la hace automáticamente en tiempo cero.
Bueno, vamos por partes:
1: Para los objetos tarta entiendo que tengo que utilizar el TAD pila porque lo que hace es ir apilando las tartas una encima de otra y por lo tanto la tarta accesible será siempre la última en fabricarse (LIFO).
Tanto la máquina como los mostradores serán pilas con capacidad estática n.
2. Para los objetos cliente utilizaré un ABB (Arbol Binario de Búsqueda).
El motivo es porque los clientes menos pacientes serán colocados a la izquierda y los más pacientes a la derecha. Creo que es la forma más rápida de localizar y atender a los clientes menos pacientes y de esta manera las propinas serán mayores.(sé que lo más honesto sería una cola(FIFO) pero hay que mirar por el dinero...)
3. Como las pilas son lentas de recorrer(iterador) y solo puedo acceder al último elemento insertado, he pensado en hacer una tabla hash de tamaño n (como los tipos de tarta) asignando una clave a cada tipo de tarta. La tabla hash se irá rellenando con el último elemento de cada pila.
Habrán colisiones cada vez que se recoja el mismo tipo de tarta y esto lo solucionaré con una lista enlazada a cada clave.
Esta última parte es la que más me cuesta porque no se hacer el enlace.
Alguien me puede ayudar?
Muchas gracias de antemano
Valora esta pregunta
0