CI-1201 Examen #3


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
I Semestre 2006

$[\/]$

CI-1201 Programación II

Examen #3 [solución]

Duración: dos horas. 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 tres de las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] Suponga que al examinar la biblioteca "Numerote.h" (que está implementada en su respectivo "Numerote.cpp") usted se encuentra varias funciones para usar números enteros binarios de longitud arbitraria que están almacenados en listas de valores booleanos (por eso los parámetros de esas funciones son listas booleanas).

1.a) [8 pts] Escriba las especificaciones de las funciones declaradas en la biblioteca "Numerote.h".

1.b) [5 pts] Su clase "BoolNum" es un empaque ("wrapper") alrededor de "Numerote.h" que sirve para que los programadores C++ puedan usar numerotes implementados con base en las funciones de la biblioteca "Numerote.h". Defina el Rep de su clase "BoolNum" usando las listas booleanas de "Numerote.h".

1.c) [12 pts] Declare los métodos públicos de la clase "BoolNum" que se necesitan para usar esa clase en la función emplantillada "Gaussian_Elimination()" de la tarea programada:

template <class E> E Gaussian_Elimination( const Matrix<E> & M, Matrix<E> & X, const Matrix<E> & B)

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) )

1.d) [8 pts] e) Implemente los operadores aritméticos ("+" , "-" , "*" , "/") de "BoolNum". No hace falta que implemente las funciones de "Numerote.h".

2) [33 pts]

 L->last ───────────────────────────────────────┐
                                                │
┌────────────┐   ┌────────────┐   ┌───────────┐ │
│            v   │            v   │           v v
│ ┌────────┬───┐ │ ┌────────┬───┐ │ ┌────────┬───┐
│ │ elem_1 │ ├─┼─┘ │ elem_2 │ ├─┼─┘ │ elem_3 │ ├─┼─┐
│ └────────┴───┘   └────────┴───┘   └────────┴───┘ │
│            ^               next              ^   │
│            │                                 │   │
│          first                             last  v
└───────<───────────────<────────────────<─────────┘

clist

La clase clist es una lista circular, en que el último nodo apunta al primero. A diferencia de una lista tradicional, en que en el Rep hay un puntero al primer nodo, en una lista circular el puntero del Rep apunta al último nodo, de manera que se pueden hacer inserciones eficientemente tanto al principio como al final de la lista (el Rep contiene únicamente el puntero al último nodo de la lista).

2.a) [0 pts] Dibuje el modelo para la lista circular L=(3,2,1). Describa el algoritmo de ordenamiento en que compara a cada valor con todos los demás.

2.b) [0 pts] Escriba un bloque de código que muestre cómo intercambiar los nodos primero y segundo de una lista. Al hacer su solución debe mostrar el diagrama de la lista después de que se ejecuta cada instrucción.

2.c) [0 pts] Escriba un bloque de código que muestre cómo intercambiar los nodos segundo y tercero de una lista. Al hacer su solución debe mostrar el diagrama de la lista después de que se ejecuta cada instrucción.

2.d) [33 pts] Implemente el método clist::Orden_123() que reacomoda los nodos de la lista una lista "L" que contiene exactamente 3 valores almacenados, de manera que queden ordenados. Use únicamente las instrucciones "if()" para comparar valores, o asignaciones de punteros. No use otro tipo de sentencias. Su algoritmo debe funcionar correctamente para todas las permutaciones posibles de valores. Use un total de 14 o menos asignaciones de punteros, y un total de 3 o menos comparaciones "if()" para que los nodos de la lista "L" queden en orden ascendente (1,2,3). En su solución usted puede usar sólo un puntero como variable temporal.

2.e) [0 pts] Si usara una lista sencilla, en que el Rep tiene un puntero al primer nodo de la cadena de nodos, y en el último está el puntero nulo, ¿cómo quedaría implementado el algoritmo que debe usar para clist::Orden_123()?

3) [33 pts] Jimmy Trueno, el famoso físico loco, acaba de inventar un novedoso algoritmo de graficación que permite acelerar en más de 2 órdenes de magnitud la velocidad de los programas de juegos. Por eso, la función "Relampago()" requiere la matriz "Flippy_Matrix" que tenga las siguientes cualidades:

Siempre es una matriz rectangular de tamaño MxN, en donde N==2xM.
Como en toda matriz, es necesario accesar el valor "(i,j)".
Además, la matriz debe permitir "cambios de dirección" tanto verticales como horizontales.
Independientemente del tamaño de la matriz, el tiempo que debe tomar cualquier "cambio de dirección" debe ser siempre el mismo (tiempo constante).
Independientemente del tamaño de la matriz, el tiempo que debe tomar el acceso al valor "(i,j)" debe ser siempre el mismo (tiempo constante).
En el Rep está una bandera "m_hor" que indica si la matriz está al derecho o al revés en el sentido horizontal.
En el Rep está una bandera "m_ver" que indica si la matriz está al derecho o al revés en el sentido veritcal.

/             \                    /             \
| a b c d e f |                    | f e d c b a |
| 1 2 3 4 5 6 | ==> Horizontal ==> | 6 5 4 3 2 1 |
| A B C D E F |                    | F E D C B A |
\             /                    \             /

/             \                    /             \
| a b c d e f |                    | A B C D E F |
| 1 2 3 4 5 6 | ===> Vertical ===> | 1 2 3 4 5 6 |
| A B C D E F |                    | a b c d e f |
\             /                    \             /

Flippy_Matrix

3.a) [5 pts] Declare el Rep de "Flippy_Matrix". Use la matriz chisquirrisquititica.

3.b) [4 pts] Implemente el constructor de vector y el destructor para su matriz.

3.c) [5 pts] Especifique e implemente el operador para cambiarle las dimensiones a su matriz.

3.d) [8 pts] Especifique los 2 operadores para accesar el valor "(i,j)" de la matriz: tanto el mutador como el examinador.

3.e) [11 pts] Implemente el operador examinador para accesar el valor "(i,j)" de la matriz.

3.f) [0 pts] Especifique e implemente el método para voltear la matriz. Llámelo "Flip()".

4) [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

4.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.

4.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.

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

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

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

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

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

5.a) [6 pts] Declare el Rep de las clases "Matriz" y "Columna" de manera que cada "Columna" contenga un vector y "Matriz" contenga un vector de punteros a cada una de las columnas. 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 "M" punteros.
"m_ptr[i]" es un vector de "N" 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 columna.
El acceso "Matriz[i][j]" siempre toma 2 brincos, pues es necesario usar el vector indirecto de "M" punteros.

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

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

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

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

Soluciones

$[/\]$