Dado un número entero N que representa el número de escalones, la tarea es contar el número de formas de llegar al N -ésimo escalón dando saltos de 1 a N.
Ejemplos:
Entrada: N = 2
Salida: 2
Explicación: Dos formas de llegar son: (1, 1) y (2)Entrada: N = 3
Salida: 4Entrada: N = 4
Salida: 8
Enfoque: En este problema, el número de formas de llegar a la i -ésima escalera es:
Formas de llegar a la i -ésima escalera = (Suma de las formas de llegar a las escaleras 1 a i-1)+1
Como cualquier escalera anterior a la i , se puede llegar a la i – ésima escalera de un solo salto. Y +1 por saltar directamente a i .
Ahora para resolver este problema:
- Cree una suma variable para almacenar la cantidad de formas de llegar a una escalera en particular. Inicializarlo con 0 .
- Ejecute un bucle de i=1 a i=N-1 y para cada iteración:
- Cree una variable, diga cur para almacenar el número de caminos a la escalera actual. Entonces, cur = suma + 1 .
- Cambie sum a sum = sum + cur .
- Devuelve sum + 1 después de que finaliza el ciclo como la respuesta a este problema.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the number of ways // to reach Nth stair int findWays(int N) { int sum = 0; for (int i = 1; i < N; i++) { int cur = sum + 1; sum += cur; } return sum + 1; } // Driver Code int main() { int N = 10; cout << findWays(N); }
Java
// Java code for the above approach import java.util.*; public class GFG { // Function to count the number of ways // to reach Nth stair static int findWays(int N) { int sum = 0; for (int i = 1; i < N; i++) { int cur = sum + 1; sum += cur; } return sum + 1; } // Driver Code public static void main(String args[]) { int N = 10; System.out.print(findWays(N)); } } // This code is contributed by Samim Hossain Mondal.
Python3
# python3 code for the above approach # Function to count the number of ways # to reach Nth stair def findWays(N): sum = 0 for i in range(1, N): cur = sum + 1 sum += cur return sum + 1 # Driver Code if __name__ == "__main__": N = 10 print(findWays(N)) # This code is contributed by rakeshsahni
C#
// C# code to implement above approach using System; class GFG { // Function to count the number of ways // to reach Nth stair static int findWays(int N) { int sum = 0; for (int i = 1; i < N; i++) { int cur = sum + 1; sum += cur; } return sum + 1; } // Driver code public static void Main() { int N = 10; Console.Write(findWays(N)); } } // This code is contributed by Samim Hossain Mondal.
Javascript
<script> // JavaScript code for the above approach // Function to count the number of ways // to reach Nth stair function findWays(N) { let sum = 0; for (let i = 1; i < N; i++) { let cur = sum + 1; sum += cur; } return sum + 1; } // Driver Code let N = 10; document.write(findWays(N)); // This code is contributed by Potta Lokesh </script>
512
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prasanna1995 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA