Universidad de Costa Rica
Escuela de Computación		 Examen 01
 CI-1201 Programación II - 2016b
Profesor Jeisson Hidalgo-Céspedes

En cada ejercicio se evaluará la eficiencia del código, el uso de identificadores significativos, la indentación, escritura correcta de llaves {} y el uso adecuado de la palabra reservada const. Se dispone de tres horas para entregar la prueba y debe realizarse en forma estrictamente individual.

Problema 1: ¿puede formar palíndromo?

Para el desarrollo de un videojuego de palabras se necesita una función que dadas unas letras (un texto), indique si con todas ellas se puede o no formar al menos un texto palíndromo, pues este hecho puede favorecer o no la puntuación del jugador. Un palíndromo es un texto que se puede leer igual de derecha a izquierda que en el sentido opuesto.

El equipo del videojuego requiere que además de la función, usted provea un pequeño programa que permita probarla. El programa debe leer textos de la entrada estándar, y para cada uno de ellos indicar con un 1 si se puede formar al menos un palíndromo y con 0 lo contrario, como se ve a la derecha. Aunque en el juego no se usan textos más largos de 100 letras, el equipo quisiera poder probar textos de hasta 1000 letras en inglés, todas en minúscula.

  1. [5%] Implementa programa de prueba correctamente.
  2. [15%] Implementa correctamente función que determina si un texto puede formar palíndromo.
  3. [5%] Aplica buenas prácticas de programación.

Ejemplo de entrada:

parar
matematica
ranarene
soldadosolo

Ejemplo de salida:

parar: 1
matematica: 0
ranarene: 1
soldadosolo: 1

Problema 2: ts

  1. [5%] ¿Qué imprime en la salida estándar el programa de la derecha?
  2. [10%] Rastree la memoria del programa. Su dibujo debe ilustrar el estado del programa cuando el control está por iniciar la ejecución de la línea 20.
  3. [5%] Describa qué trabajo realiza la función ts().
  4. [5%] ¿Cuáles serían identificadores significativos para las siguientes variables:?
    • b
    • p
    • q
    • c
    • ts
  5. [5% opcional] ¿Qué imprime el programa si la línea 25 se reeplaza por printf("[%s][%s]\n", ts(1234567890ull), ts(0));. Explique rápidamente.
 
]]>

Problema 3: Gauss-Jordan

Ejemplo de entrada:

3
3 5 8 63
2 3 6 41
1 2 3 24

Ejemplo de salida:

   3.0   5.0   8.0 |  63.0
   2.0   3.0   6.0 |  41.0
   1.0   2.0   3.0 |  24.0

f1 /= 3.0:
   1.0   1.7   2.7 |  21.0
   2.0   3.0   6.0 |  41.0
   1.0   2.0   3.0 |  24.0

f2 += -2.0 f1:
f3 += -1.0 f1:
   1.0   1.7   2.7 |  21.0
   0.0  -0.3   0.7 |  -1.0
   0.0   0.3   0.3 |   3.0

f2 /= -0.3:
   1.0   1.7   2.7 |  21.0
  -0.0   1.0  -2.0 |   3.0
   0.0   0.3   0.3 |   3.0

f1 += -1.7 f2:
f3 += -0.3 f2:
   1.0   0.0   6.0 |  16.0
  -0.0   1.0  -2.0 |   3.0
   0.0   0.0   1.0 |   2.0

f3 /= 1.0:
   1.0   0.0   6.0 |  16.0
  -0.0   1.0  -2.0 |   3.0
   0.0   0.0   1.0 |   2.0

f1 += -6.0 f3:
f2 += 2.0 f3:
   1.0   0.0   0.0 |   4.0
   0.0   1.0   0.0 |   7.0
   0.0   0.0   1.0 |   2.0

La eliminación de Gauss Jordan es un método algebraico para resolver un sistema de n ecuaciones con n incógnitas. Varios software matemáticos populares realizan este proceso y reportan el resultado, pero no los pasos que realizaron para llegar a él. Estos pasos son muy útiles para estudiantes de cursos de álgebra.

Implemente un programa que realiza la eliminación de Gauss-Jordan e imprime los pasos que aplicó en el proceso. El programa lee de la entrada estándar una matriz aumentada de n ecuaciones con n incógnitas. El número en la primera fila indica este tamaño n. Cada fila representa una ecuación, con los coeficientes las n variables y el valor de equivalencia. Por ejemplo la segunda fila en el ejemplo de la derecha representa la ecuación 3x1 + 5x2 + 8x3 = 63. El programa debe transformar la matriz aumentada en una matriz identidad siguiendo el algoritmo de Gauss-Jordan:

  1. Por cada fila (o ecuación) f de la matriz:

    1. Hacer el elemento de la diagonal de esa fila Mf,f en 1, multiplicando la ecuación completa por el inverso de Mf,f. Por ejemplo, para la fila f=1 (línea 1 en el ejemplo de salida) se tiene que M1,1=3.0, por lo que todos los coeficientes de la fila f=1 se dividirán por 3.0 para convertir a M1,1 en 1. Esta es la primera operación (f1 /= 3.0, impresa en la línea 5 del ejemplo de salida) y el resultado se ve en la segunda matriz impresa entre las líneas 6 a 8 del ejemplo de la derecha.

    2. Por cada una de las restantes filas (o ecuaciones) g:

      1. Tomar el opuesto aditivo de Mg,f, llámese -Mg,f. Por ejemplo, para la segunda ecuación g=2 (en la línea 7) se toma -Mg,f = -M2,1 = -2.0 como opuesto aditivo.

      2. Por cada columna c de la fila o ecuación g:

        1. Sumar al coeficiente Mg,c el resultado de multiplicar el opuesto -Mg,f con Mf,c para convertir a Mg,f en 0.0. Por ejemplo el 0.0 de la segunda ecuación g=2 en la primera columna c=1 (línea 13) se obtiene como Mg,c += -Mg,f * Mf,c, es decir, M2,1 += -2.0 * 1.0 => 0.0. Para la segunda columna c=3 se tendrá Mg,c += -Mg,f * Mf,c => M2,3 += -2.0 * 2.66 => 6.0 += -2.0 * 2.66 => 6.0 += -5.33 => 0.66 (aparece redondeado como 0.7 en línea 13).

En cada paso, se debe imprimir las operaciones sobre las filas que se le están aplicando a la matriz (por ejemplo f1 /= 3.0 indica que se está dividiendo por 3.0 todos los coeficientes de la fila 1). Tras aplicar el algoritmo a todas las filas, se debe obtener la matriz identidad que encuentra los valores solución al sistema de ecuaciones.

  1. [5%] Lee matrices reales correctamente de la entrada estándar.
  2. [10%] El programa se puede usar con matrices muy grandes (por ejemplo, mayores a 8MB) sin producir fugas de memoria.
  3. [20%] Implementa correctamente la reducción de Gauss-Jordan.
  4. [10%] Imprime cada una de las operaciones en las filas.
  5. [5%] Imprime el estado de la matriz en cada una de las operaciones.