CI-1201 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
II Semestre 2012

$[\/]$

CI-1201 Programación II

Examen #2 [solución]

Duración: Ciento veinte minutos. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva todas las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] En 1878 Samuel Loyd inventó el "Juego de los Quince" que se juega en una matriz 4x4 moviendo piezas a la casilla vacía hasta que queden ordenadas. Un ejemplo del comienzo y fin del juego es el siguiente:

15	2	3	4
5	6	7	8
9	10	11	12
13	14	1

→

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15

1.a) [0 pts] Dibuje el modelo para la clase "J15" que sirve para almacenar de una forma eficiente los números del Juego de los Quince. Indique si vale la pena usar un enum para los valores { up down left right }.

1.b) [5 pts] Defina la abstracción y explique cuáles operaciones son importantes para esta clase.

1.c) [20 pts] Escriba el archivo de encabezado con la especificación en formato "Doxygen" para la clase "J15". Incluya el Rep y los datos de prueba BUnit.h para la clase.

1.d) [8 pts] Use una lista en donde almacene valores de tipo "J15" para representar los movimientos del juego. Especifique e implemente una rutina que comience en una configuración del juego y genere la lista de los movimientos que resuelven el juego. Su algoritmo no tiene que ser eficiente. Puede usar una estrategia de prueba y error para obtener la solución del juego, por lo que es válido escribir y borrar de la lista configuraciones de juego de prueba. Recuerde que en algunos casos el juego no tiene solución. No se le meta al Rep de "J15".

1.e) [0 pts] Explique si es mejor usar las rutinas str2list.h para hacer los ejemplos de prueba de los métodos del juego "J15" o si más bien es mejor usar inicializaciones de matrices (pues ambas requieren de un método para cargar los valores a partir de una matriz cuadrada).

2) [33 pts]

+--------------------------------+
| MZ..<...'.....7.......o....... |
| ..triturar.................... |
| ..g...6........)("33$.....J... |
| ..P...=...matar........?!??;;^ |
| o.z.o.i.o...o...o...o...o..... |
| ..n...j...f...b.destruir..V... |
| .....bonga..i.H.i.3.i...i...i. |
| i...i...i...i.matanga...i.'.i. |
| ......}...A...1...$....canga.. |
+--------------------------------+
           chunga.exe

Jimmy Neutron descubrió que muchos de los programas ejecutables que usan los estudiantes de la ECCI incluyen comandos satánicos que es necesario censurar. Para eso, propuso construir un módulo que recibe como entrada un programa ejecutable y produce una lista de las palabras que contiene el texto, en donde "palabra" significa "varias letras juntas, sin espacios ni caracteres raros".

Escriba un programa que permita extraer todas las hileras de un archivo. Incluya un argumento que indique cuál es el tamaño mínimo de una palabra, para evitar que letras solas aparezcan en la salida. Su programa no debe imprimir cada palabra más de una vez.

3) [33 pts] La función booleana obtieneMasa() retorna "false" cuando termina de proveer datos (los que obtiene leyéndolos de archivos o de la red). De otra forma, retorna "true" y un contenedor "Masa" lleno de valores de tipo "Token". En cada invocación, obtieneMasa() retorna un contenedor "Masa" completo.

3.a) [0 pts] Haga un diagrama que muestre cómo están organizadas las clases "Masa" y "Token".

3.b) [5 pts] Especifique la función obtieneMasa(). El contenedor "Masa" debe estar diseñado de manera que pueda ser recorrido con iteradores, de manera similar a como se recorren los contenedores de la biblioteca estándar. Recuerde incluir suficientes ejemplos BUnit.

3.c) [3 pts] Escriba la declaración de las clase "Masa". Incluya los métodos que usa en las implementaciones. Recuerde: ¡No se le meta al Rep!

Recuerde que la diferencia entre "definir" y "declarar" un objeto en C++ es que las declaraciones se ponen en los archivos de encabezados <*.h> y <*.hpp>, mientras que las definiciones están en los archivos de implementación <*.c> y <*.cpp>.

Las declaraciones corresponden a la especificación.
Las definiciones corresponden a la implementación. Para facilitarle memorizar este hecho, asocie la palabra "definición" con la directiva #define que sirve para implementar macros en C++:
#define max(a,b) ( (a)>(b) ? (a) : (b) )

3.d) [3 pts] Escriba la declaración de la clase "Token". Incluya los métodos que usa en las implementaciones. Recuerde: ¡No se le meta al Rep!

3.e) [6 pts] La clase "Token" incluye el método booleano "estaMarcado()" que retorna "true" para los tokens que están marcados. Implemente una función que recorra el contenedor "Masa" y almacene sus tokens marcados en una lista.

3.f) [11 pts] Escriba un programa que utilice "obtienMasa()" y un contenedor std::map<> para almacenar en él todos los contenedores "Masa" que corresponden a cada uno de los tokens marcados, de manera que cada token marcado sirva como llave para obtener la lista de contenedores "Masa" en los que aparece ese token (si un contenedor "Masa" contiene varios tokens marcados, ese contenedor "Masa" deberá aparecer en varias listas). Suponga que es posible copiar objetos de tipo "Masa" y de tipo "Token" usando sus respectivos métodos de copia (recuerde: pierde el 33% de los puntos si no usa std::map<>).

3.g) [5 pts] Suponga que tanto la clase "Token" como "Masa" ya tiene definido el operator<<() para grabar el valor del token en un flujo de salida. Modifique el programa que escribió en el punto anterior para que también imprima, para cada token, todas las "masas" en que aparece.

3.h) [0 pts] Use "Masa" y "Token" para escribir un programa similar al definido para spamTico.com.

Soluciones

$[/\]$