Estructuras de Datos 2 - Taller Parcial Final

PRIMERA PARTE (60%):

A continuación se plantean 6 ejercicios tomados del sitio de UVA Online Judge.  Debe resolver al menos tres de ellos y subirlos al sitio http://www.uvaonlinejudge.org


1.      673 – Paréntesis Balanceados

Usted recibe una cadena que consta de paréntesis () y []. Una cadena de este tipo se dice que es correcta:

1.  si es la cadena vacía
2.  si A y B son correctas, AB es correcta,
3.  si A es correcta, (A) y [A] es correcta.

Escriba un programa que reciba una secuencia de cadenas de este tipo y comprobar su corrección. El programa puede suponer que la duración máxima de la cadena es de 128.

Entrada
Un archivo que contiene un entero positivo n y n secuencias de cadenas de paréntesis () y [], cada cadena en una línea

Salida
Una secuencia de Sí o No en el archivo de salida.

Ejemplo de entrada
3
([])
(([()])))
([()[]()])()

Ejemplo de salida

No


2.     540 – Cola de Equipo

Las Colas y las colas de prioridad son estructuras de datos conocidas normalmente por ingenieros y desarrolladores de software.  La cola de equipo, sin embargo, no es tan conocido, aunque se produce a menudo en la vida cotidiana.

En una cola de equipo de cada elemento pertenece a un equipo. Si un elemento entra en la cola, se busca primero en la cabeza de la cola de la cabeza para comprobar si algunos de sus compañeros de equipo (elementos del mismo equipo) ya están en la cola. Si es así, entra en la cola justo detrás de ellos. Si no, entra en la cola en la cola y se convierte en el nuevo último (mala suerte).

Para desencolar un elemento (Dequeue) se hace igual que en las colas normales: los elementos son retirados de la cola en el orden en que aparecen en la cola de equipo.

Su tarea es escribir un programa que simula una cola de equipo.

Entrada
El archivo de entrada va a contener uno o más casos de prueba. Cada caso de prueba comienza con una linea que tiene el número de equipos t ( 1 <= t <= 1000); luego vienen en lineas separadas los detalles de cada uno de los equipos, que comienzan con la cantidad de miembros del equipo y la descripción de cada uno de ellos, que es un número entero en el rango de 0 a 999999.  Un equipo puede tener hasta 1.000 elementos.

A continuación viene una lista de comandos.  Existen tres diferentes tipos de comandos:
ENQUEUE x           - introducir elemento x en la cola de equipo
DEQUEUE              - procesa el primer elemento y quitarlo de la cola
STOP      - final de caso de prueba

La entrada se termina por un valor de 0 para t

Salida
Para cada caso de prueba, la primera impresión una línea que diga Escenario `` "# k, donde k es el número del caso de prueba. A continuación, para cada comando de quitar de la cola, imprimir el elemento que es quitado de la cola en una sola línea. Imprimir una línea en blanco después cada caso de prueba, incluso después de la última.

Ejemplo de entrada
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

Ejemplo de salida

Escenario # 1
101
102
103
201
202
203


Escenario # 2
259001
259002
259003
259004
259005
260001



3.     112 – Suma de Árboles

Introducción
LISP fue uno de lor primeros lenguajes de programación de alto nivel y, junto con FORTRAN, es uno de los más viejos lenguajes que aun se utilizan. Las Listas, que son las estructuras de datos fundamentales en LISP, pueden ser fácilmente adapatadas para representar otras estructuras de datos importantes como los árboles.

Este problema trata sobre determinar si árboles binarios representados como expresiones en LISP poseern cierta propiedad.

El problema
Dado un árbol binario de enteros, usted debe escribir un programa que determina si existe un ruta de la raiz a alguna hoja en la que la suma de los nodos sea igual a un entero dado.  Por ejemplo, en el siguiente árbol hay exactamente cuatro caminos de la raiz a las hojas.  La suma de dichos caminos son 27, 22, 26 y 18.




Los árboles binarios se representarán en el archivo de entrada como expresiones en LISP que tienen la siguiente forma:

ábol vacío             ::=  ()
árbol                      ::= árbol vacío  (entero árbol árbol)

El árbol mostrado anteriormente se representa por la expresión
(5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )

Note que con esta formulación todas las hojas de un árbol son de la forma (entero () () )

Entrada
La entrada consiste de una secuencia de casos de prueba en la forma de entero/árbol.  Cada caso consiste de un entero seguido por uno o más espacios, seguido por un árbol binario formateado como la expresión descrita anteriormente.  Todas las espresiones serán válidas, pero éstas pueden ocupar más de una linea y pueden contener espacios  Puede haber más de un caso de prueba en el archivo de entrada y la entrada termina con el fin de archivo.

Salida
Debería haber una línea de salida para cada caso de prueba del archivo de entrada.  Para cada caso se debe generar un “yes” si hay una ruta de la raíz a alguna hora que sume el valor del entero, y “no” si no la hay.

Ejemplo de entrada
22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
10           (3
                                (2
(4 () () )
                                               (8 () () )
)
                (1
(6 () () )
(4 () () )
                )
                )
5 ()

Salida del Ejemplo
yes
no
yes
no


4.     10042 - Números De Smith

Mientras leía su guía de teléfonos en 1982, Albert Wilansky, un matemático de la universidad de Lehigh, notó que el número de teléfono de su cuñado H. Smith tenía la siguiente característica peculiar: La suma de los dígitos de ese número era igual a la suma de los dígitos de los factores primos de ese
número. El número de teléfono de Smith era 493-7775. Este número se puede escribir como el producto de sus factores primos de la siguiente manera: 4937775 = 3 x 5 x 5 x 65837.

La suma de todos los dígitos del número de teléfono es 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42, y la suma de los dígitos de los factores primos es igualmente 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42. Wilansky fue así que sorprendido por su descubrimiento que nombró a este tipo de números; con el nombre de su
cuñado, Números de Smith. Una lista pequeña de números de Smith es 4, 22, 27, 58, 85, 94, 121, 166, 202, 265.

Pues esta observación es también verdad para cada número primo, Wilansky decidió más adelante que el número primo no es igual que el número de Smith y él los excluyo de la definición.

Problema.
Wilansky publicó un artículo acerca de los números de Smith en “Two Year College Mathematics Journal”. Fue capaz de presentar una colección de diversos números de Smith: Sin embargo, Wilansky no podía dar un número de Smith que sea más grande que el número de teléfono de su cuñado. Esta es su tarea, encontrar los números de Smith que son más grandes que 4937775.


Entrada
El número que se introduce en la primera línea de entrada es el número de casos de prueba. Cada caso de prueba consiste de una línea que contiene un solo número entero positivo más pequeño que 109.

Salida.
Para cada valor de n, se tiene que calcular el número de Smith más pequeño, que sea mayor a n (o que esté por encima de n) e imprimir cada número en una sola línea. Asumir que existe tal número.

Ejemplo de entrada
1
4937774

Salida
4937775


5.     10295 - Cálculo de salario

Cada empleado en un trabajo burocrático tiene una descripción de su trabajo en un pequeño párrafo, que describe las responsabilidades del mismo.  La descripción del trabajo está combinado con aspectos tales como experiencia para definir su salario.

El sistema libera al personal de recursos humanos de tener que juzgar en forma inteligente como valorar a un empleado. El proceso consiste en juzgar al empleado en base de una serie de frases buscando las palabras que implican responsabilidad.

Debe implementar un sistema simplificado de cálculo de salarios. Dado un diccionario de palabras y un número de descripciones de trabajos debe calcular el salario de cada persona.

La primera entrada contiene dos números enteros positivos m <= 1000 que corresponden al número de palabras en el diccionario y un número n <= 100 que indica el número de descripciones de trabajo.  Cada palabra del diccionario contiene una palabra y un valor que es un Número real entre 0 y 1.000.000.  Seguidamente vienen las descripciones de los puestos de trabajos que consisten en una o varias líneas de texto que terminan en un punto.

Para cada descripción del texto debe imprimir el salario calculado que es la suma de los puntos asignados en las palabras de la descripción que figuran en el diccionario.

Entrada
administer          100000
spending             200000
manage               50000
responsibility    25000
expertise            100
skill                        50
money                 75000
The incumbent will administer the spending of kindergarden milk money and exercise responsibility for making change he or she will share responsibility for the task of managing the money with the assistant whose skill and expertise shall ensure the successful spending exercise.

This individual must have the skill to perform a heart transplant and expertise in rocket science.

Salida
700150
150


6.     499 - Hallar la frecuencia

El problema consiste en hallar las letras que ocurren con mayor frecuencia en una línea de texto.  La salida contiene la lista de letras que incurrieron con la máxima frecuencia seguido de la frecuencia.  La lista de letras debe estar en minúsculas y en forma ordenada.

Ejemplo de entrada
When riding your bicycle backwards down a one-way street, if the
wheel falls of a canoe, how many ball bearings does it take to fill
up a water buffalo?
Hello Howard.

Ejemplo de salida
e 6
al 7
a 3
Hlo 2




SEGUNDA PARTE (40%):

La composición estadística de los estudiantes de una universidad se ha determinado de la siguiente forma, de acuerdo con varios criterios:
Edades

Facultades

Sexo

Jornada
18-24
50%

Ingeniería
60%

Hombres
55%

Nocturna
60%
25-30
30%

Administración
30%

Mujeres
45%

Diurna
40%
31-40
20%

Humanidades
10%







1.      Generar una estructura de datos que pueda contener los siguientes datos:
·         Nombre
·         Apellidos
·         Edad
·         Facultad
·         Jornada
·         Sexo

2.      Utilizando las funciones de generación de números aleatorios, y basándose en la composición estadística presentada anteriormente, generar un banco de datos de prueba con 400 personas. (40%)

3.      Generar por cada facultad, la lista alfabética ordenada de sus estudiantes. (30%)

4.      Con base en la información generada, desplegar las tablas estadísticas que validen el modelo, para edades, facultades, sexo y jornada. (30%)


--- Fin de documento ---

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...