Cuente el número de formas de llegar al N-ésimo escalón dando saltos de 1 a N

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: 4

Entrada: 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: 

  1. Cree una suma variable para almacenar la cantidad de formas de llegar a una escalera en particular. Inicializarlo con 0 .
  2. Ejecute un bucle de i=1 a i=N-1 y para cada iteración:
    1. Cree una variable, diga cur para almacenar el número de caminos a la escalera actual. Entonces, cur = suma + 1 .
    2. Cambie sum a sum = sum + cur .
  3. 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>
Producción

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

Deja una respuesta

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