CI-1201 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
II Semestre 2005

$[\/]$

CI-1201 Programación II

Examen Final [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. Debe escribir con un bolígrafo de tinta. Resuelva tres de las cuatro preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] En las calles de Piswack en Canadá hay un gran problema de tráfico cuya solución requiere del uso de una simulación. Para eso, usarán un modelo en que esté representado en el computador el estado de las calles, segundo por segundo.

             |  |oo|               |[]|
             |  |  |         \     |  |
             |  |  |  ========>    |  |
            \|/ |  |         /     |()|
----------------    ---------------    --------------------
 () [].[]  oo         oo   []             ()  ()  [].[]
----------------    ---------------    --------------------
                |()|           /|\ |  |     oo  Moto
                |  |            |  |  |     ()  Auto
                |[]|            |  |  |     []  Camioncito
                |  |            |  |oo|  [].[]  Camionzote

1.a) [11 pts] Especifique y declare el Rep de un objeto que sirva para representar a los vehículos que aparecen en la simulación. Incluya las declaraciones de los demás objetos de la jerarquía. También declares el(los) contenedor(es) que representa las calles, en donde están los vehículos. Las calles tienen una forma "++" como la que se muestra en la figura; suponga que en cada una de las 2 intersecciones hay un semáforo.

1.b) [11 pts] Durante la simulación es necesario usar un ciclo que sirve para calcular, segundo por segundo, cuál es la posición de cada vehículo en la carretera. Algunos duran menos que otros en cruzar cada trozo de la calle, pues tienen una velocidad mayor. Pero no puede ocurrir que el de "atrás" rebase al de "adelante", pues las calles no son anchas. Además, cuando los vehículos llegan al semáforo tienen que esperar a que la luz esté en "verde" para continuar. El truco para que "lleguen" autos es usar una función generadora FG() que es invocada en cada iteración del ciclo de simulación, la que utiliza un generador de números aleatorios para "insertar" vehículos "nuevos" en las calles de entrada a esta red vial (otras "funciones generadoras" de la clase sirven para definir los demás atributos de los "autos nuevos"). Cuando un vehículo se sale del trozo de calles que se está simulando, simplemente basta removerlo del contenedor. Especifique y declare el objeto "Simulacion" que se requiere para hacer la simulación.

1.c) [11 pts] Implemente el ciclo principal, que simula el estado de toda la red vial segundo por segundo. Documente bien lo que hace.

2) [33 pts] El Partido Estatal Democrático Organizado ha iniciado una campaña anti-corrupción para evitar que los familiares estén en las Juntas Directiva de las instituciones públicas. Para implementarlo es necesario contar con un programa de computadora que permita determinar si 2 personas son hermanos, hijos, primos o tíos.

2.a) [6 pts] Declare la clase "Viejillo" que tiene los datos de cada persona. No se le olvide incluir el número de cédula. Use punteros para registrar quién es el padre y la madre de cada viejillo.

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

2.b) [0 pts] Discuta si esta red familiar es o no un contenedor.

2.c) [5 pts] Las Juntas Directivas están compuestas de varios viejillos quienes no deben ser familiares. Declare el Rep para la clase "Junta_Directiva".

2.d) [5 pts] Especifique y e implemente el método "Agregar()" que sirve para agregarle otro viejillo a una Junta Directiva. Levante la excepción "CHORICERO" si se violenta la invariante de la clase.

2.e) [6 pts] Especifique e implemente el "check_ok()" para la clase "Junta_Directiva". No olvide definir la invariante de la clase.

2.f) [11 pts] Especifique e implemente el método "Es_Familia()" que sirve para saber si 2 viejillos pueden o no estar en la misma Junta Directiva. No olvide reportar qué tipo de familiaridad tienen.

2.g) [0 pts] Diga por cuánta plata implementaría usted un programa que lea el "padrón nacional" y determine cuáles son los choriceros que están nombrados ahora en las instituciones autónomas.

3) [33 pts] Una "escalera" es una clase que contiene una hilera de caracteres a la que se le pueden aplicar estas operaciones:

suba(E,n): Traslada el n-ésimo elemento hacia arriba una vez (si se puede).
Suba("!bcde",1) ==> "b!cde"
Suba("abcd!",5) ==> "abcd!"
aparea(E): Intercambia todas las parejas de elementos en la escalera (excepto el último si hay una cantidad impar).
Aparea("abcdefg") ==> "badcfeg"
caiga(E): Traslada el elemento del fondo.
Caiga("abcde!") ==> "!abcde"
cuenta(E): Función que regresa la cantidad de elementos de "E".
Cuenta("abcde") ==> 5
print(E): Imprime la escalera.

La rutina "circular()" corre circularmente el primer elemento de la "escalera", imprimiéndola antes de cada corrimiento. La invocación circular("!abcd") debería producir la siguiente salida:

!abcd
a!bcd
ab!cd
abc!d
abcd!
!abcd
a!bcd  etc...

3.a) [6 pts] Implemente la rutina "circular()" usando la "escalera", de forma que se produzca la salida arriba descrita. Use únicamente las operaciones arriba indicadas (No se le meta al Rep).

3.b) [0 pts] Se ha determinado que ninguna escalera será más grande que 2387 caracteres. Escriba las declaraciones de una implementación de la "escalera" en que se usen vectores de letras.

3.c) [5 pts] Indique cómo modificaría usted el procedimiento "circular()" de la parte a) para que trabaje adecuadamente en la nueva implementación usando arreglos.

3.d) [11 pts] Si la "escalera" inicial es "aicoca", indique cuáles de las siguientes escaleras pueden ser impresas usando las operaciones arriba indicadas:

"aicoca"
"iaocac"
"aocaci"
"aoccai"
"coacia"

3.e) [11 pts] ¿Es posible usar únicamente estas operaciones del Tipo de datos abstracto "escalera" para implementar un procedimiento que ordene [escaleras de caracteres]? Si se puede hacer, impleméntelo. De lo contrario... ¡explique!

Soluciones

$[/\]$