Problema 1 · Programació II UDL 2010
Tema: Recursión: diseño, traza y diagramas de llamadas · Del examen Examen Primer Parcial Noviembre 2010 (2010)
Enunciado
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");
}
}
}
Solución
Según los criterios oficiales de corrección
Realizad el diagrama de las llamadas (pila de bloques de activación) que se producen durante la ejecución del siguiente programa.
Solución: Traza de la pila de activación: | Nivel | Método | Parámetros y Variables locales | Punto retorno | Evaluación / Acción | | :--- | :--- | :--- | :--- | :--- | | 1 | `run` | `numbers = {8, 4, 7, 19, 23, 6}`<br>`mistery = ? -> true` | ACABAR | Invoca a `isMisterious(numbers)` en R1 | | 2 | `isMisterious(int[])` | `elems = ref(numbers)` | R1 | Invoca a `isMisterious(elems, 0, 0)` en R2 | | 3 | `isMisterious(int[], int, int)` | `elems = ref(numbers)`<br>`sumBeforePos = 0`<br>`pos = 0` | R2 | `pos != 6; elems[0] == 0` (8 == 0 es `false`); evalúa la llamada por cortocircuito `||` en R3 con `sumBeforePos = 8, pos = 1` | | 4 | `isMisterious(int[], int, int)` | `elems = ref(numbers)`<br>`sumBeforePos = 8`<br>`pos = 1` | R3 | `pos != 6; elems[1] == 8` (4 == 8 es `false`); evalúa llamada recursiva en R3 con `sumBeforePos = 12, pos = 2` | | 5 | `isMisterious(int[], int, int)` | `elems = ref(numbers)`<br>`sumBeforePos = 12`<br>`pos = 2` | R3 | `pos != 6; elems[2] == 12` (7 == 12 es `false`); evalúa llamada recursiva en R3 con `sumBeforePos = 19, pos = 3` | | 6 | `isMisterious(int[], int, int)` | `elems = ref(numbers)`<br>`sumBeforePos = 19`<br>`pos = 3` | R3 | `pos != 6; elems[3] == 19` (19 == 19 es true). Por evaluación en cortocircuito del operador `||`, no se realizan más llamadas y retorna directamente `true`. | Retorno de las llamadas: - Nivel 6 devuelve `true` a nivel 5 en R3. - Nivel 5 devuelve `true` a nivel 4 en R3. - Nivel 4 devuelve `true` a nivel 3 en R3. - Nivel 3 devuelve `true` a nivel 2 en R2. - Nivel 2 devuelve `true` a nivel 1 en R1, asignándose `mistery = true`. - En `run`, al cumplirse `mistery == true`, se ejecuta la rama `if`.
Indicad asimismo qué salida genera el programa por pantalla.
Solución: Misterious numbers!
La explicación paso a paso, hecha con IA, es Premium. Premium
Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.
‹ Problema 3 · 2011 · Problema 2 · 2010 ›