1

tengo una tarea que no entiendo como empezar , me piden que cuente de cuantas maneras puedo subir una escalera de N escalones ej: pepito puede subir de 1 o 2 escalones de cuantas maneras puede subir una escalera de 4 escalones , a lo que me tendria que mostrar en pantalla

a) 1,1,1,1 (1 escalon y luego 1 hasta llegar a 4)

b) 1,1,2

c) 1,2,1

d) 2,2

necesito de su ayuda porfavor

1
  • 1
    bienvenido, por favor lee Cómo preguntar y replantea tu pregunta añadiendo lo que haz tratado por que de otro modo se percibe sin ningún intento tuyo y creeme aqui nadie te lo resolverá, lo que si puedes pedir es apoyo a lo que lleves intentado para lograrlo
    – user75901
    el 25 oct. 2018 a las 22:38

1 respuesta 1

0

¿Has intentado algo? En lugar de darte el código con la solución voy a darte algunas ideas para que intentes llegar a ello por tí mismo.

La clave de la recursividad consiste en implementar una función que resuelva el caso trivial (ej: escalera de 1 escalón o de 2), y que para resolver casos más complejos resuelva primero una escalera más pequeña (llamándose a sí misma) y use esa solución para resolver la escalera más grande.

En el caso de la escalera tienes que pensar... "Si yo tuviera una función a la que le paso el número de peldaños de una escalera (digamos M) y me devuelve la lista con todas las posibles formas de subir esa escalera... ¿cómo podría usarlo para resolver una escalera con más peldaños, digamos N?"

Si te paras a pensar un poco la solución podría ir así:

  • La escalera de N peldaños la puedo comenzar subiendo 1 escalón, o también subiendo 2. Son las únicas formas. Digamos que elijo subir p peldaños para empezar.
  • Una vez subidos los primeros peldaños, lo que me queda por delante es una escalera más pequeña, con N-p peldaños.
  • Usemos la función que resuelve la escalera menor. Me retornará una lista de las formas de subir esa sub-escalera. A cada elemento de esa lista le añado por delante el valor de p
  • Si hago lo anterior dos veces, una para p=1 y otra para p=2, ya tengo todas las formas de subir la escalera de tamaño N.

Ahora, el milagro de la recursividad es que esa otra función que te resuelve escaleras menores ¡es la misma que la que te resuelve escaleras mayores! Basta añadirle por delante código que detecte si la escalera a subir tiene sólo 1 ó 2 peldaños para que en esos casos retorne las soluciones triviales "precalculadas".

El pseudo-codigo sería por tanto:

def escalera(N):
   si N==1 retornar una lista con un solo elemento [[1]], pues sólo hay una forma
           de subir una escalera de un escalón
   si N==2 retornar una lista con dos elementos [[1,1], [2]], pues hay dos formas
           de subir una escalera de dos escalones. O de uno en uno, o los dos a la vez
   Para el resto de casos:
   repetir para p=1 y p=2
      obtener soluciones para escalera de tamaño N-p
      a cada solución concatenarle p por delante
   retornar la lista de soluciones halladas.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.