Saltar al contenido

¿Cuántas formas distintas de subir escaleras en 1 o 2 escalones a la vez?

Intenta entender el código bien previamente a usarlo a tu trabajo y si tdeseas aportar algo puedes compartirlo con nosotros.

Solución:

Sea $F_n$ el número de maneras de subir $n$ escaleras tomando solo $1$ o $2$ pasos. Sabemos que $F_1 = 1$ y $F_2 = 2$. Ahora, considere $F_n$ para $nge 3$. El paso final será de tamaño $1$ o $2$, entonces $F_n$ = $F_n-1 + F_n-2$. Esta es la recurrencia de Fibonacci.

De hecho, la solución a este problema corresponde a los números de Fibonacci, como lo menciona @fahrbach.

Aquí hay una ilustración de lo que está tratando de resolver para el caso de $ n = 4 $ pasos (tomado de este sitio web, que también brinda una solución combinatoria)

ingrese la descripción de la imagen aquí

Cualquier escalera con $n$ escalones que permitan caminos con incrementos de 1 o 2 escalones a la vez terminará en uno de dos estados antes de tomar el último camino: ya hemos subido $(n-1)$ escalones y tenemos $colorredun$ paso más por dar, o ya hemos subido $(n-2)$ pasos y tenemos $colorbluedos$ pasos más por dar (si dimos solo un paso aquí, entonces terminaríamos en un arreglo desde el primer estado).

ingrese la descripción de la imagen aquí

Por lo tanto, para obtener el número total de formas posibles de subir $n$ escalones, solo sumamos el número de formas posibles de subir $(n-1)$ escalones y el número de formas posibles de subir $(n-2) )$ pasos, dando la familiar relación de recurrencia:

beginecuación* F_n = left{ beginarray[email protected][email protected]l 1 & n = 0,1\ colorredF_n-1 + colorblueF_n-2 & n ge 2 endarray Correcto. endecuación*

valoraciones y comentarios

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *