Ejercicios corregidos algoritmo recursivo

Los siguientes ejercicios corregidos se refieren al principio del algoritmo recursivo, por ejemplo Fibonacci, las Torres de Hanoi y muchos otros casos Matemáticas.

algoritmo recursivo

Ejercicio 1

Reescriba los siguientes algoritmos en forma recursiva en forma terminal cuando sea posible.

algoritmo recursivo ejercicios corregidos terminal recursivo árbol de llamadas de recursividad múltiple

algoritmo recursivo

algoritmo recursivo

Una última para el camino. ¡Esta vez tienes que entender lo que hace antes de convertirlo en terminal recursivo!

algoritmo mcd

Consideramos que n es un entero positivo o cero.

algoritmo recursivo terminal

algoritmo recursivo terminal

algo3 ya es recursivo pero no terminal. Dado que el algoritmo devuelve 2^no, cambiaremos su estructura para convertirlo en terminal.

algoritmo recursivo terminal

Por el último algoritmo, primero debemos entender que calcula el mcd entre a y b. Haga una prueba a mano, comprenderá que la primera rama es inútil, por lo que la eliminaremos para la recursividad. La variable r no está presente para reemplazar el valor de a y b, por lo que no encajará en la recursividad.

algoritmo mcd

Ejercicio 2

El problema de Fibonacci (1170 – 1250):

“Teniendo originalmente una pareja de conejos, ¿cuántas parejas obtienes en doce meses si cada pareja genera una nueva pareja cada mes a partir del segundo mes de su existencia? Los conejos nunca mueren.

Entonces, si tomamos un ejemplo de los primeros 7 meses.

Mes

1

2

3

4

5

6

7

Pareja

1

1

2

3

5

8

13

a – Expresar la población de parejas del mes n en función de los meses anteriores.

b – Escriba un algoritmo iterativo que calcule el número de parejas después de 12 meses.

c – Modifique el algoritmo iterativo para calcular el número de meses después de los cuales la población de parejas de conejos supera los 300.

d – Escribe el algoritmo recursivo para calcular el número de parejas de conejos después de n meses.

posee -

El número de parejas de conejos en el mes n es la suma de las parejas existentes el mes anterior (en el mes n − 1) y las parejas nuevas en el mes n.

Sin embargo, el texto especifica que todas las parejas existentes dos meses antes (en el mes n − 2) se reproducen.

Por tanto, en el mes n ≥ 2 el número de conejos es igual a la suma del mes n-1 y n-2. En el mes 0 y el mes 1, solo hay un par.

b-

Ejercicios corregidos algoritmo recursivo algoritmo recursivo

contra -

Ejercicios corregidos algoritmo recursivo algoritmo recursivo

d-

algoritmo recursivo de fibonacci

No calcularemos el complejidad arriba. Para los que quieren perder la cabeza, aquí los invito: https://miashs-www.u-ga.fr/prevert/Prog/Complexite/nombresFibonacci.html

Ejercicio 3

a – Escribe un algoritmo que calcule el máximo de 2 números reales 

b – Escribe un algoritmo recursivo que calcule el máximo de 3 números reales usando el algoritmo de a. Mostrar árbol de llamadas.

c – Escribe un algoritmo recursivo que calcule el máximo de 4 números reales usando el algoritmo de a. Mostrar árbol de llamadas.

d – ¿El algoritmo es recursivo?

posee -

algoritmo recursivo máximo

b-

algoritmo recursivo máximo

Aquí, Maximum2 actúa como la condición terminal del algoritmo recursivo. La pila de llamadas es la siguiente:

algoritmo recursivo máximo

contra -

algoritmo recursivo máximo

La pila de llamadas es la siguiente:

algoritmo recursivo máximo

d – Aunque parece una recursividad, es más una sobrecarga de función o una llamada de función para reducir el tamaño del problema. No es un algoritmo recursivo per se.

Ejercicio 4

a – ¿Están los algoritmos por debajo de los algoritmos recursivos? 

b – ¿Son terminales?

c – ¿Terminan?

algoritmo recursivo de registro

algoritmo recursivo de potencia

algoritmo recursivo de suma

posee -

Los algoritmos log y sum son recursivos: cada uno contiene al menos una llamada a sí mismo, por otro lado, power no lo es: llama al algoritmo entonces. Es necesario reemplazar luego por energía.

b- 

log es terminal, power y sum no lo son porque requieren cálculo durante la recursividad.

contra -

log termina para cualquier entero x. La iteración de la división de enteros por 2 conduce a 0, y el caso base 0 termina con la ejecución de return. 

Para el algoritmo de potencia (corregido), el caso base 0 finaliza con la ejecución de return. Si el algoritmo termina para el valor n−1, también termina para el valor n está ejecutando return. No olvide que un usuario puede ingresar cualquier cosa como potencia (2, – 5), por lo que debe verificar su terminación.

sum no termina cuando n es estrictamente positivo. De hecho, el algoritmo para n termina solo si el algoritmo termina para n+1. Sin embargo, no existe un entero estrictamente positivo para el cual el algoritmo se detenga.

Ejercicio 5

a – Queremos escribir una función recursiva que calcule el cuadrado de un número entero. Para hacer esto, tendremos que usar una relación entre cuadrado(n) y cuadrado(n-1) sabiendo que cuadrado(1)=1. Representa la pila de llamadas para carre(5).

b – Las combinaciones son un concepto matemático que describe las diferentes formas de elegir un número dado de objetos de un conjunto de tamaño dado. Por ejemplo, cuánto es posible sacar 6 bolas de Lotto de 60 en el carrete. O saca 3 cartas de una baraja de tarot. La combinación de elegir p elementos de n elementos se denota C(p,n)=(n/p)*C(p-1, n-1). Obtuvimos C(0,n)=1 y C(n,n)=1. 

Escriba la función recursiva no terminal, luego la función recursiva terminal y muestre la pila de llamadas para C(3,7). A través de la función terminal, deducir la función iterativa.

c – Para las combinaciones, generalmente preferimos evitar el método b porque las divisiones pueden crear problemas de redondeo. En su lugar, utilizaremos la siguiente relación: C(p,n)=C(p,n-1)+C(p-1,n-1). Escriba la función recursiva y la pila o árbol pide C(2,4).

a – Para encontrar un vínculo entre cuadrado(n) y cuadrado(n-1), usamos la fórmula: (n+ 1)² = n² + 2n+ 1. Lo escribimos en función de n a n-1: n² = (n−1)²+2(n−1)+1 por lo tanto cuadrado(n)=cuadrado(n-1)+2*n-1. Eso es todo !

algoritmo cuadrado recursivo

La pila de llamadas es:

algoritmo cuadrado recursivo

b – Todo está dicho en el enunciado, sólo resta anotarlo.

combinación de algoritmo recursivo

Aquí está la lista de llamadas para C(3,7):

combinación de algoritmo recursivo

Y ahora para la versión de terminal, es un poco más complicado porque tienes que preguntarte qué tienes que guardar en la memoria para la recursividad. En cada iteración hicimos n/p veces la anterior, entonces n/p * (n-1)/(p-1). Podríamos haberlo escrito n(n-1)/p(p-1). Entonces podríamos almacenar la multiplicación de n decreciente en un lado y p decreciente en el otro.

combinación de algoritmo recursivo

Aquí está la pila de llamadas para C(3,7,1,1):

combinación de algoritmo recursivo

Deducimos la función iterativa de la función terminal. Simplemente haga un hasta que se alcance la condición de parada.

combinación de algoritmo recursivo

c – Ya tenemos la relación recursiva en el enunciado.

combinación de algoritmo recursivo

Aquí está el árbol de llamadas para C(2,4):

combinación de algoritmo recursivo

Ejercicio 6

Definimos la función de McCarthy de la siguiente manera:

Algoritmo de McCarthy

¿Qué hace la función para n>100? para n=98, 99, 100? En general para n<=100?

Vamos a hacer un poco de matemática... Si n > 100 tendremos n-10. El problema surge cuando empezamos con n<=100. Calcula para 98, 99 y 100. Haremos una demostración directa.

Para n entre 90 y 100 inclusive, es decir, 11 valores consecutivos, esto será útil más adelante. Haremos Carthy(Carthy(n+1)) por lo que excederemos el valor de 100. Entonces tendremos Carthy(n+1) al final. Si n+1 aún no es mayor que 100, volvemos a colocar la tapa. Entonces paramos cuando pasamos de 100 a 101, o Carthy(101)=101-10=91.

En resume lo que dejamos al principio del párrafo anterior. Sobre los últimos 11 valores consecutivos, tendremos un resultado de 91. Observamos que cualquier número entre 0 y 89, al que le sumamos 11 siempre que sea menor que 90, tendrá un valor final entre 90 y 100 inclusive.

Deducimos que Carthy en un valor de 100 o menos dará el valor de 91.

Necesitaba un poco de matemática. ¡La informática es solo otra forma sintáctica de hacer matemáticas!

Ejercicio 7

Hablamos de recursión se cruzan cuando dos funciones se llaman recursivamente.

Probaremos en una recursividad cruzada para saber si un número es par (verdadero) o impar (falso). Aquí está la propuesta:

algoritmo recursivo cruzado

Pruebe par (2), impar (3), par (3) e impar (2). ¿Es correcto el algoritmo? De lo contrario cámbialo para comprobar la corrección ← PD: si el profesor pregunta eso es porque el algo tiene un problema CQFD

Obviamente el algoritmo no es correcto. Tome par (3) → impar (2) → par (1) → impar (0) → par (-1) → impar (-2) → etc. Esto se debe a que las condiciones de parada solo funcionan si el número del método par es par y el método impar es impar. Solo cambiaremos el método impar.

recursividad cruzada incluso impar

¡Depende de usted volver a probar si es correcto ahora!

Ejercicio 8

Es imposible concluir sobre el recursivo sin mencionar las famosas Torres de Hanoi (¡la obsesión de los estudiantes y, a veces, también de los profesores y profesores!). Así que vamos a tomarlo con calma.

torres de hanoi

Hay n bandejas de diferentes tamaños y 3 varillas, numeradas del 0 al 2.

Inicialmente, todas las bandejas están ubicadas en el vástago i. El objetivo es transferirlos al varilla j, respetando las siguientes reglas:

– Solo puedes mover un tablero a la vez.

– Las bandejas deben estar siempre dispuestas en tamaño decreciente sobre una varilla (las más grandes en la parte inferior y luego en orden decreciente subiendo sobre la varilla).

1 – Resuelva el problema a mano si n = 2, i = 0 y j = 2 (entonces 2 bandejas, todas están basadas en la barra 0 y queremos ponerlas en la barra 2).

2 – Resuelva el problema a mano si n = 3, i = 0 y j = 2 (entonces 3 bandejas, todas están basadas en la barra 0 y queremos ponerlas en la barra 2).

3 – Supongamos que un amigo tuyo sabe cómo resolver el problema para algún n, y cualquier que i y j. Se le pide que resuelva el problema para n + 1. Tiene derecho para utilizar la ayuda de su amigo. ¿Cómo lo haces?

4 – Escribe la función recursiva que resuelve este problema para todo n, i, j (Si puedes hacerlo sin hacer trampas, ¡enhorabuena! De lo contrario es normal, casi todos pasamos por ese gran momento de incomprensión y cuestionamiento de su carrera…)

1 – 

El tablero pequeño se transfiere de 0 a 1. 

El tablero grande se transfiere de 0 a 2. 

Pasamos la bandeja chica del 1 al 2.

2 –

El tablero pequeño se transfiere de 0 a 2. 

Transferimos la meseta promedio de 0 a 1.

Pasamos el tablero pequeño del 2 al 1. (movimos 2 tableros del 0 al 1). 

El tablero grande se transfiere de 0 a 2. 

El tablero pequeño se transfiere de 1 a 0. 

Pasamos el tablero mediano de 1 a 2. 

Pasamos el tablero pequeño del 0 al 2. (movimos 2 tableros del 1 al 2).

3 –

Movemos n bandejas desde i hasta la ubicación que no es ni i ni j (mediante la serie de tres manipulaciones del punto 2). Luego movemos el último tablero (el más grande) de i a j. Le pedimos al amigo que mueva las n bandejas a j. 

4 –

Si encuentras eso… ¡champaña! Renombraremos para mayor facilidad los tallos en d para el inicial, a para el de llegada y r para el restante

torres de hanoi

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: