Programa en C para contar las formas de llegar al escalón n

Hay n escaleras y una persona parada en la parte inferior quiere llegar a la cima. La persona puede subir 1 o 2 escalones a la vez. Cuente el número de formas en que la persona puede llegar a la cima.
 

Considere el ejemplo que se muestra en el diagrama. El valor de n es 3. Hay 3 formas de llegar a la cima. El diagrama está tomado de los rompecabezas de Fibonacci más fáciles  
. Ejemplos: 
 

Input: n = 1
Output: 1
There is only one way to climb 1 stair

Input: n = 2
Output: 2
There are two ways: (1, 1) and (2)

Input: n = 4
Output: 5
There are five ways: (1, 1, 1, 1), (1, 1, 2), 
(2, 1, 1), (1, 2, 1), (2, 2)

Método 1 : Recursión.
Enfoque: podemos encontrar fácilmente la naturaleza recursiva en el problema anterior. La persona puede llegar ^al escalón n desde (n-1) ^este escalón o desde (n-2) ^este escalón. Por lo tanto, para cada escalón n , tratamos de encontrar el número de formas de llegar al n-1 ^escalón y al n-2 ^escalón y las sumamos para dar la respuesta para el n- ^ésimo escalón. Por lo tanto, la expresión para tal enfoque resulta ser: 
 

ways(n) = ways(n-1) + ways(n-2)

La expresión anterior es en realidad la expresión de los números de Fibonacci , pero hay una cosa a tener en cuenta, el valor deways(n) es igual a fibonacci(n+1). 
 

ways(1) = fib(2) = 1
ways(2) = fib(3) = 2
ways(3) = fib(4) = 3

Para una mejor comprensión, consultemos el árbol de recursión a continuación: 
 

Input: N = 4

                  fib(5)
           '3'  /        \   '2'
               /          \
           fib(4)         fib(3)
     '2'  /      \ '1'   /      \  
         /        \     /        \ 
     fib(3)     fib(2)fib(2)      fib(1) 
     /    \ '1' /   \ '0'
'1' /   '1'\   /     \ 
   /        \ fib(1) fib(0) 
fib(2)     fib(1)

Entonces podemos usar la función para los números de Fibonacci para encontrar el valor de las vías (n). 
A continuación se muestra la implementación de la idea anterior. 
 

// A C program to count number of
// ways to reach n't stair when
// a person can climb 1, 2, ..m stairs at a time.
#include <stdio.h>
 
// A simple recursive program to find
// n'th fibonacci number
int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
 
// Returns number of ways to reach s'th stair
int countWays(int s)
{
    return fib(s + 1);
}
 
// Driver program to test above functions
int main()
{
    int s = 4;
    printf("Number of ways = %d", countWays(s));
    getchar();
    return 0;
}

Number of ways = 5

Análisis de Complejidad: 
 

1. Como en el enfoque anterior, estamos haciendo cálculos redundantes, como encontrar fib(3) más de ‘1’ número de veces. Esto aumenta su complejidad de tiempo a exponencial.
2. Se puede optimizar para que funcione en tiempo O (Logn) utilizando las optimizaciones de funciones de Fibonacci discutidas anteriormente .

Generalización del problema anterior 
Cómo contar el número de formas si la persona puede subir hasta m escaleras para un valor dado m. 
Por ejemplo, si m es 4, la persona puede subir 1 escalón o 2 escalones o 3 escalones o 4 escalones a la vez.
Enfoque: Para la generalización del enfoque anterior, podemos usar la siguiente relación recursiva. 
Podemos escribir la recurrencia de la siguiente manera. 
 

ways(n, m) = ways(n-1, m) + ways(n-2, m) + 
             ... + ways(n-m, m) 

En este enfoque para llegar a una escalera-‘n’ intentamos subir todo el número posible de escaleras menor que igual a ‘n’ desde la escalera actual. 
 

// A C program to count number of
// ways to reach n't stair when
// a person can climb either 1 or 2
// stairs at a time
#include <stdio.h>
 
// A recursive function used by countWays
int countWaysUtil(int n, int m)
{
    if (n <= 1)
        return n;
    int res = 0;
    for (int i = 1; i <= m && i <= n; i++)
        res += countWaysUtil(n - i, m);
    return res;
}
 
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
    return countWaysUtil(s + 1, m);
}
 
// Driver program to test above functions-
int main()
{
    int s = 4, m = 2;
    printf("Number of ways = %d", countWays(s, m));
    return 0;
}

Number of ways = 5

Análisis de Complejidad: 
 

• Complejidad temporal: O(2^n). 
  1. Como en el enfoque anterior, estamos haciendo cálculos redundantes, como encontrar fib (3, 2) más de ‘1’ número de veces, lo que aumenta su complejidad de tiempo a exponencial.
  2. Se puede optimizar a O(m*n) usando programación dinámica. Construimos una tabla ‘res[]’ de forma ascendente.
• Espacio Auxiliar: O(1). 
  o uso de cualquier estructura de datos para almacenar valores. 
   

Método 2 : Programación Dinámica.
Enfoque: Este método utiliza la técnica de Programación Dinámica para llegar a la solución.
Enfoque: creamos una tabla res[] de forma ascendente usando la siguiente relación: 
 

res[i] = res[i] + res[i-j] for every (i-j) >= 0

tal que el i ^-ésimo índice de la array contendrá el número de caminos requeridos para alcanzar el i- ^ésimo paso considerando todas las posibilidades de ascenso (es decir, de 1 a i ).
El siguiente código implementa el enfoque anterior:
 

// A C program to count number
// of ways to reach n't stair when
// a person can climb 1, 2, ..m
// stairs at a time
#include <stdio.h>
 
// A recursive function used by countWays
int countWaysUtil(int n, int m)
{
    int res[n];
    res[0] = 1;
    res[1] = 1;
    for (int i = 2; i < n; i++) {
        res[i] = 0;
        for (int j = 1; j <= m && j <= i; j++)
            res[i] += res[i - j];
    }
    return res[n - 1];
}
 
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
    return countWaysUtil(s + 1, m);
}
 
// Driver program to test above functions
int main()
{
    int s = 4, m = 2;
    printf("Number of ways = %d", countWays(s, m));
    return 0;
}

Number of ways = 5

Análisis de Complejidad: 
 

• Complejidad temporal: O(m*n). 
  En cuanto a cada escalera, comprobamos todas las posibilidades ‘m’ y el número de escaleras es ‘n’.
• Espacio Auxiliar: O(n). 
  Uso de array para almacenar valores intermedios.

Consulte el artículo completo sobre las formas de contar para llegar al escalón n para obtener más detalles.