CI-1201 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
I Semestre 2011

$[\/]$

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] Una ventaja de los iteradores Java es que basta una sola variable para recorrer un contenedor.

2.a) [22 pts] Escriba el archivo de encabezado para el iterador itrAcum.h que sirve para recorrer una lista visitando el primer elemento una vez, el segundo dos, hasta retornar el n-ésimo n veces. Por ejemplo, si L==(a,b,c) el iterador retornará a los elementos en el orden (a b b c c c). Incluya la especificación de su iterador junto con los datos de prueba BUnit.h. En su respuesta usted debe usar el siguiente Rep para el iterador:

TYPE
  Rep_Acum = RECORD
    c : Lpos_T;   { list<>::iterator actual    }
    i : UNSIGNED; { Número del elemento actual }
                  { 0 <= i <= L.size()         }
    countL,       { L.size()                   }
    k : UNSIGNED; { Veces que se ha retornado  }
                  { el i-ésimo elemento        }
    L : ^List_P;  { Puntero a la lista que se recorre }
  END;

2.b) [11 pts] Implemente el iterador.

3) [33 pts] La matriz chisquirrisquitirrisquititica no incluye una clase vector que le permita al programador cliente de la clase manipular una fila completa. Diseñe 2 clases amigas, "Matriz" y "Fila", de manera que el programador cliente pueda obtener y manipular una fila completa de la matriz.

 m_ptr[]
  /[*]--->[*][*][*][*][*][*][*]
 | [*]--->[*][*][*][*][*][*][*]
 | [*]--->[*][*][*][*][*][*][*]  Matriz[NxM]:
N| [*]--->[*][*][*][*][*][*][*]  - N filas
 | [*]--->[*][*][*][*][*][*][*]  - M Columnas
 | [*]--->[*][*][*][*][*][*][*]
  \[*]--->[*][*][*][*][*][*][*]
           |----------------->
                    M

3.a) [6 pts] Declare el Rep de las clases "Matriz" y "Fila" de manera que cada "Fila" contenga un vector y "Matriz" contenga un vector de punteros a cada una de las filas. Suponga que la matriz es densa. Respecte los siguientes requerimientos en el Rep:

El tamaño de la matriz es NxM.
Los tamaños "N" y "M" pueden cambiar en tiempo de ejecución.
"m_ptr[]" es un vector de "N" punteros.
"m_ptr[i]" es un vector de "M" valores.
La matriz queda implementada como un vector de punteros en que cada uno de esos punteros apunta al vector que contiene todos los valores de una fila.
El acceso "Matriz[i][j]" siempre toma 2 brincos, pues es necesario usar el vector indirecto de "N" punteros.

3.b) [7 pts] Especifique e implemente una operación que le permita al programador cliente obtener una fila completa de la matriz. No copie la fila.

3.c) [7 pts] Especifique e implemente una operación que le permita al programador usuario accesar uno de los valores de la matriz.

3.d) [7 pts] Especifique e implemente una operación que le permita al programador usuario intercambiar 2 filas de la matriz.

3.e) [6 pts] Especifique e implemente una operación que le permita al programador usuario intercambiar 2 columnas de la matriz.

Soluciones

$[/\]$