Examen de Programació II UDL 2012 · Primer Parcial Curso 2012-2013

Problema 1. Diagrama de llamadas y traza de ejecución recursiva

Realizad el diagrama de las llamadas (pila de llamadas / marcos de activación) producidas a lo largo de la ejecución del siguiente programa en Java, especificando detalladamente para cada registro:

El nombre de la función invocada (tened en cuenta que las operaciones básicas como concatenaciones de texto no originan marcos de activación adicionales).

Las variables locales y los parámetros formales, reflejando su valor concreto (o '?' si carecen todavía de inicialización), así como las modificaciones progresivas provocadas por cada asignación. Para los subprogramas predefinidos como println donde se desconozca el identificador del parámetro, emplead param. Podéis abreviar la representación del array inmutable como {2, -4,...}.

Los puntos exactos de retorno a los que se transfiere el flujo, señalando la línea del programa correspondiente.

1 public class MisteryProgram extends ConsoleProgram {

2

3 public int isMisterious(int[] coefs, int left, int right) {

4 if (left == right) {

5 return left;

6 } else {

7 int middle = (left + right) / 2;

8 if (coefs[middle] >= 0) {

9 return 1 + isMisterious(coefs, left, middle - 1);

10 } else {

11 return 1 - isMisterious(coefs, middle, right);

12 }

13 }

14 }

15

16 public int isMisterious(int[] elems) {

17 return isMisterious(elems, 0, elems.length);

18 }

19

20 public void run() {

21 int[] vector = {2, -4, 4, 5, 3, -3, 1, 2};

22 int pos = isMisterious(vector);

23 println("El resultado es " + pos);

24 }

25

26 }

Podéis subir la foto del diagrama de pila de marcos de activación o redactar/completar el desarrollo en el recuadro:

Problema 2. Función recursiva para contar apariciones en sufijo

Diseñad e implementad un método recursivo que, a partir de:

un vector de números enteros (garantizado no nulo),

un entero que indica la posición inicial a partir de la cual se considera el sufijo del vector,

un valor entero a buscar,

calcule y retorne la cantidad total de apariciones de dicho valor en el sufijo especificado.

La signatura requerida es:

public int timesInSuffix(int[] elems, int pos, int value) {

// Implementación

}

Nota: Es imprescindible incluir la justificación formal o inductiva del diseño (definición de casos base y regla inductiva sobre el tamaño del sufijo).

public int timesInSuffix(int[] elems, int pos, int value) {

}

Problema 3. Copia recursiva de vector mediante prefijos

Diseñad e implementad un método recursivo que, dado un vector de enteros no nulo, cree y devuelva un nuevo vector idéntico (con idéntica dimensión y los mismos valores situados en idénticas posiciones).

public int[] copyVector(int[] source) {

// Implementación

}

Para evitar la sobrecarga de instanciar y replicar vectores en cada nivel de recursión, debéis apoyar la solución en una función auxiliar con parámetros adicionales que opere estructurándose sobre los prefijos de los vectores.

Nota: Se requiere justificar detalladamente el diseño inductivo o recursivo.