Examen de Programació II UDL 2010 · Primer Parcial Noviembre 2010

Problema 1. Diagrama de llamadas y activación de métodos recursivos

Realizad el diagrama de las llamadas (pila de bloques de activación) que se producen durante la ejecución del siguiente programa. Para cada bloque de activación indicad:

El nombre de la función o método.

Las variables locales y los parámetros con su valor inicial (usad ? cuando estén sin inicializar) y las modificaciones de valor tras las asignaciones.

Los puntos de retorno correspondientes (indicados mediante R1, R2 y R3 en el código). El punto de retorno del método run indicadlo como ACABAR.

Indicad asimismo qué salida genera el programa por pantalla.

public class MisteryProgram extends ConsoleProgram {

public boolean isMisterious(int[] elems, int sumBeforePos, int pos) {

if (pos == elems.length) {

return false;

} else {

return elems[pos] == sumBeforePos ||

isMisterious(elems, sumBeforePos + elems[pos], pos + 1); // R3

}

}

public boolean isMisterious(int[] elems) {

return isMisterious(elems, 0, 0); // R2

}

public void run() {

int[] numbers = {8, 4, 7, 19, 23, 6};

boolean mistery;

mistery = isMisterious(numbers); // R1

if (mistery) {

println("Misterious numbers!");

} else {

println("Regular numbers");

}

}

}

Problema 2. Suma recursiva de diferencias cuadráticas

Dados dos vectores de números en coma flotante ( double) de igual tamaño, se desea implementar un método que obtenga la suma posicional de las diferencias al cuadrado entre sus componentes:

$$\text{sumOfSquaredDiffs}(a, b) = \sum_{i=0}^{n-1} (a_i - b_i)^2$$

En Java el método envoltorio presenta la siguiente signatura:

public double sumOfSquaredDiffs(double[] a, double[] b) {

//...

}

Para implementar la solución de forma recursiva, se añade un parámetro adicional que señale el índice sobre el que se opera:

public double squaredDiffs(double[] a, double[] b, int pos) {

//...

}

Se pide:

a)

Diseñar la función recursiva squaredDiffs razonando y justificando su funcionamiento correcto (caso base, caso recursivo y convergencia).

public double squaredDiffs(double[] a, double[] b, int pos) {

}

b)

Indicar la llamada inicial que efectúa el método envoltorio sumOfSquaredDiffs para computar el total sobre todos los elementos de los vectores.

public double sumOfSquaredDiffs(double[] a, double[] b) {

}

Problema 3. Búsqueda binaria recursiva de coincidencia en vectores ordenados

Dados dos vectores de enteros con la misma longitud, donde uno está ordenado de manera creciente ( asc) y el otro de forma decreciente ( desc), se desea diseñar un método que determine si existe algún índice en el que ambos vectores contengan el mismo valor (por ejemplo, que exista una posición 3 tal que asc[3] == desc[3]).

La signatura del método principal es:

public boolean crossed(int[] asc, int[] desc)

Para conseguir una implementación eficiente aplicando la estrategia de búsqueda binaria, empleamos dos índices para acotar el rango de búsqueda en cada paso:

public boolean crossed(int[] asc, int[] desc, int left, int right)

a.

Diseñar la función recursiva crossed(int[] asc, int[] desc, int left, int right), justificando la validez del descarte de mitades apoyándose en las propiedades de ordenación de los vectores.

public boolean crossed(int[] asc, int[] desc, int left, int right) {

}

b.

Definir la invocación inicial desde crossed(int[] asc, int[] desc) para abarcar ambos vectores al completo.

public boolean crossed(int[] asc, int[] desc) {

}