Pregunta 2.a-b · Prácticas de programación UOC 2021
Tema: Comprensión y traza de algoritmos recursivos · Del examen Prueba de síntesis. Enero de 2021 (2021)
Enunciado
Se facilita la siguiente rutina recursiva escrita en lenguaje C:
#define MAX 42
int guess(int v[MAX], int a, int b)
{
int result;
assert(0 <= a && a < MAX && 0 <= b && b < MAX && a <= b);
if (a == b) // (1)
result = v[b]; // (2)
else { // (3)
result = guess(v, a + 1, b); // (4)
if (result > v[a]) // (5)
result = v[a]; // (6)
} // (7)
return result; // (8)
}
a.
[10%] ¿Qué repercusiones acarrea sustituir la llamada de la línea (4) por la instrucción result = guess(v, a + 2, b); ?
b.
[10%] Detalla la finalidad del algoritmo guess (qué cálculo resuelve sobre los datos). Asimismo, refleja la secuencia de ejecución paso a paso (mediante traza o diagrama de llamadas) ante la siguiente invocación con un array de muestra:
int datos[] = {0, -4, 2, 6, 1, 3};
int test = guess(datos, 2, 5);
Solución
Según los criterios oficiales de corrección
a. [10%] ¿Qué repercusiones acarrea sustituir la llamada de la línea (4) por la instrucción result = guess(v, a + 2, b);?
Solución: La corrección de una definición recursiva se fundamenta en el principio de inducción: es indispensable garantizar que toda llamada avance hacia el caso base para asegurar la convergencia. Al saltar de dos en dos (a + 2), si la distancia entre a y b (b - a) fuese impar, el índice a superaría a b sin llegar a cumplirse la igualdad a == b. Ello rompería la condición de parada, violaría la aserción y provocaría recursión infinita o desbordamiento de memoria.
b. [10%] Valor devuelto asignado a test en guess(datos, 2, 5)
Solución: 1
b. [10%] Detalla la finalidad del algoritmo guess y refleja la secuencia de ejecución paso a paso (mediante traza o diagrama de llamadas) ante la invocación guess(datos, 2, 5)
Solución: Comportamiento del método: Determina y devuelve el elemento de valor mínimo presente en el subvector delimitado entre los índices a y b (ambos inclusivos). Traza de la ejecución para el vector con elementos en las posiciones 2 a 5: - Posición 2: 2 - Posición 3: 6 - Posición 4: 1 - Posición 5: 3 Secuencia de llamadas y resolución de retornos: 1. guess(datos, 2, 5) queda en espera de guess(datos, 3, 5). 2. guess(datos, 3, 5) queda en espera de guess(datos, 4, 5). 3. guess(datos, 4, 5) queda en espera de guess(datos, 5, 5). 4. guess(datos, 5, 5) alcanza el caso base (a == b) y devuelve v[5] = 3. 5. En el nivel (4, 5): compara el valor recibido (3) con v[4] = 1. Puesto que 3 > 1, asigna result = 1 y lo devuelve. 6. En el nivel (3, 5): compara el valor recibido (1) con v[3] = 6. Como no es mayor (1 ≯ 6), mantiene result = 1 y lo devuelve. 7. En el nivel (2, 5): compara el valor recibido (1) con v[2] = 2. Como 1 ≯ 2, mantiene result = 1 y lo devuelve. El valor asignado a test es 1.
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.
‹ Pregunta 2.a y 2.b · 2021 · Pregunta 2.a · Juny 2020 ›