Broken Ways (problema de lógica)

Este problema fue publicado en el sitio web de la Escuela Newton, “Pregunta del día 9/ene/2023”.

Planteamiento del problema:

Newton quiere llegar a la parte superior de una escalera que tiene algunos escalones rotos (no puede visitar esos escalones). Puede subir 1 o 2 escalones a la vez.

Ejemplo de escalera de 15 peldaños con los peldaños 3 y 9 rotos. Los pasos válidos para visitar son: 1,2, 4,5,6,7,8, 10,11,12,13,14,15.

Una posible forma de llegar a la cima de esta escalera es visitando los escalones: 2,4,5,7,8,10,12,14,15 (unas veces Newton subía 1 escalón y otras subía 2 escalones).

El objeto del problema es encontrar el número de maneras diferentes en que Newton puede llegar a la parte superior de la escalera.

Aquí muestro una solución:

Este problema recuerda la “Secuencia de Fibonacci”. ¿Pero por qué? Debido a que solo puede alcanzar un paso desde el paso 1 o el paso 2, la cantidad de formas en que puede alcanzar un paso es la suma de "formas en que puede alcanzar el paso 1" + "formas en que puede alcanzar el paso 2". ”.

Entonces, para llegar al paso 1, solo tiene 1 camino (subir desde el suelo hasta el paso 1); para llegar al paso 2 tienes 2 formas (subir desde el suelo directamente al paso 2 o subir desde el paso 1), para llegar al paso 3 tienes 3 formas (1 forma desde el paso 1 + 2 formas desde el paso 2), para llegar al paso 4 tienes 5 vías (2 vías del paso 2 + 3 vías del paso 3), para llegar al paso 5 tienes 8 vías (3 vías del paso 3 + 5 vías del paso 4) y así hasta el último paso.

¡Pero esta es exactamente la secuencia de Fibonacci! Sí, pero este problema tiene un giro, se han agregado "pasos rotos" . De acuerdo, no hay problema, dado que Newton no puede visitar los escalones rotos, solo establezca 0 formas de llegar a ellos.

Volviendo a nuestro ejemplo, con los pasos 3 y 9 rotos, tenemos esta "secuencia rota de Fibonacci" : 1, 2, 0, 2, 2, 4, 6, 10, 0, 10, 10, 20, 30, 50, 80.

Entonces, en esta escalera, Newton tiene 80 formas diferentes de subirla.

Ahora, puede implementar el algoritmo de secuencia rota de Fibonacci en su lenguaje de programación favorito y cargarlo en el sitio web de la Escuela Newton , que tiene muchos problemas geniales para resolver en la sesión de la Pregunta del día.

¡Divertirse!