Contar: ¿cuántas formas de subir una escalera?

Question

Estás subiendo una escalera. En cada escalón, puede hacer $1$ subir el escalón, o hacer $2$ subida de escalones. Digamos que una escalera de altura de $3$ . Se puede subir en $3$ formas $(1-1-1,\ 1-2,\ 2-1)$ .

Digamos que una escalera de altura de $4$ Puedes subir $5$ formas.

Dada una escalera de altura de $n$ ¿podrías calcular de cuántas maneras puedes escalar?

---

Intento:

En realidad se trata de un problema de programación, ya he escrito el código C++ en recursividad, pero no sé cómo verificar mi programa utilizando conocimientos matemáticos. Creo que no es un problema matemático complicado, pero aún así no he podido resolverlo. Así que les pido ayuda.

Answer 1

Claro, ese código se ve bien. Cuando ejecuto mi propia versión del código, obtengo la secuencia Fibbonaci, ¿y tú?

$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ \cdots$$

Esto tiene sentido: supongamos que $F_n$ representa el número de vías de ascenso $n$ pasos. Si hay que subir $n$ pasos, tenemos dos opciones: podemos dar 1 paso primero, entonces tendremos $F_{n-1}$ opciones. O podemos dar 2 pasos primero, entonces tendremos $F_{n-2}$ opciones. En otras palabras, $F_{n+1} = F_{n} + F_{n-1}$ total de opciones.

Como caso base especial, tenemos que $F_0 = 1$ (el caso base de su programa), y $F_1 = 1$ .

Answer 2

Este es un ejemplo típico de Secuencia de Fibonacci .

Para llegar hasta, digamos $N^{th}$ paso, necesita llegar a $(N-1)^{th}$ o $(N-2)^{th}$ paso. Es cierto para todos los valores de $N$ donde $N$ es ${1,2,3...}$ .
Se trata, pues, de una recursión, al igual que evidente de su código :

if (numStairs-BIG>=0) return CountWays(numStairs-SMALL)+CountWays(numStairs-BIG); else return CountWays(numStairs-SMALL);