CI-1101 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1101
I Semestre 2014

$[\/]$

CI-1101 Programación I

Examen Final [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] ProductoMorboso() no sirve para determinar si algún renglón de la matriz es factor de otro.

1.a) [4 pts] Declare la clase Matriz con los métodos que necesite para implementar ProductoMorboso(). No olvide declarar los campos de la clase.

1.b) [11 pts] Especifique el método ProductoMorboso() debe retornar un ArrayList<> de valores numéricos que contiene todos los productos que no son nulos. Para calcularlos se multiplican los valores que están en el renglón impar por los correspondientes valores del siguiente renglón par de la matriz, pero se van sumando y restando hasta el final.

[3] →  0    11   23    5    8   13   21    34    55    89     1   44
[4] →  0    92   23   37    2    0   36    85    47    75    80    7
      --- ----- ---- ---- ---- --------- ------ ----- ----- ---- ----
[*] →  0  1012  529   185  16    0  756   2890  2585   6675  80   308    Productos
+/- →  0 -1012  529  -185  16    0  756  -2890  2585  -6675  80  -308   -7104 → Total

1.c) [18 pts] Implemente el método Matriz.ProductoMorboso().

2) [33 pts] “List.parteLista()”

2.a) [0 pts] Haga un diagrama de una lista que contiene los valores {(a),(b),(c),(d),(e),(f),(g)}.

2.b) [6 pts] Es bien sabido que en una lista doblemente enlazada se puede usar cirugía de punteros para dejar todos los valores en orden inverso con el simple algoritmo de intercambiar los campos “next” y “prev” de cada nodo. Muestre cómo queda el diagrama del punto anterior después de aplicarle este sencillo algoritmo; suponga que usa la lista vista en clase.

2.c) [11 pts] Implemente el método “List.alVerres()” usando el algoritmo descrito anteriormente para invertir los valores de una lista sin hacer copias de los nodos o de los valores.

2.d) [6 pts] Especifique el método “list.parteLista()” que toma la mitad de los valores del final de la lista y los pone al principio. Incluya un diagrama del resultado de usar este método.

2.e) [10 pts] Implemente “list.parteLista()”.

3) [33 pts] Los primeros 12 números de Fibonnacci son estos: { 0,1,1,2,3,5,8,13,21,34,55,89 }, los que se pueden calcular usando el siguiente método:

public static long fibonacci(long n) {
    if ( n<=2 ) {
        return ((n<=0) ? 0 : 1);
    }
    else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
} // Fibonacci()

3.a) [6 pts] Haga la especificación del método estaFibonachizado(n) que determina si un 'n' es alguno de estos números enteros (que se obtienen concatenado los números de Fibonacci):

 0 → 0
 1 → 1
 1 → 11
 2 → 112
 3 → 1123
 5 → 11235
 8 → 112358
13 → 11235813
21 → 1123581321
34 → etc.

3.b) [27 pts] Utilice esta implementación de fibonacci() para implementar estaFibonachizado(n). Recuerde que un entero Java tipo “long” de 64 bits no puede almacenar números superiores a 2^63-1 == [ 9,223,372,036,854,775,807 ] (que es el valor de la constante java.lang.Long.MAX_VALUE). Recuerde incluir suficientes comentarios explicativos en su algoritmo. Además, evite sobrepasar el valor máximo que se puede almacenar en un entero de 64 bits.

Soluciones

$[/\]$