Dado un número N que denota el número de escalones, la tarea es llegar al enésimo escalón dando 1, 2 escalones cualquier número de veces y dando un escalón de 3 exactamente una vez.
Ejemplos:
Entrada: N = 4
Salida: 2
Explicación:
Dado que un paso de 3 se tiene que dar obligatoriamente y solo una vez,
solo hay dos formas posibles: (1, 3) o (3, 1)
Entrada: N = 5
Salida: 5
Explicación:
Dado que un paso de 3 se tiene que dar obligatoriamente y solo una vez,
solo hay 5 formas posibles:
(1, 1, 3), (1, 3, 1), (3, 1, 1), (2, 3), (3, 2)
Enfoque: Este problema se puede resolver usando Programación Dinámica . Para llegar al escalón N , la persona debe estar en (N – 1) th , (N – 2) th o (N – 3) th . Por lo tanto, Para llegar al N escalón desde la base Alcance (N – 1) el escalón que incluye exactamente solo un escalón de 3, Alcance (N – 2) el escalón con los escalones que incluye exactamente un escalón de 3 y Alcance el (N – 3) paso sin tomar ningún paso de 3. Entonces, la relación de recurrencia para este problema será –
incluye_3[i] = incluye_3[i-1] + incluye_3[i-2] + no_incluye[i-3]
mientras que la relación de recurrencia cuando no se permite el número de 3 pasos a la vez es
no_incluye[i] = no_incluye[i – 1] + no_incluye[i – 2]
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation to find the number // the number of ways to reach Nth stair // by taking 1, 2 step at a time and // 3 Steps at a time exactly once. #include <iostream> using namespace std; // Function to find the number // the number of ways to reach Nth stair int number_of_ways(int n) { // Array including number // of ways that includes 3 int includes_3[n + 1] = {}; // Array including number of // ways that doesn't includes 3 int not_includes_3[n + 1] = {}; // Initially to reach 3 stairs by // taking 3 steps can be // reached by 1 way includes_3[3] = 1; not_includes_3[1] = 1; not_includes_3[2] = 2; not_includes_3[3] = 3; // Loop to find the number // the number of ways to reach Nth stair for (int i = 4; i <= n; i++) { includes_3[i] = includes_3[i - 1] + includes_3[i - 2] + not_includes_3[i - 3]; not_includes_3[i] = not_includes_3[i - 1] + not_includes_3[i - 2]; } return includes_3[n]; } // Driver Code int main() { int n = 7; cout << number_of_ways(n); return 0; }
Java
// Java implementation to find the number // the number of ways to reach Nth stair // by taking 1, 2 step at a time and // 3 Steps at a time exactly once. class GFG { // Function to find the number // the number of ways to reach Nth stair static int number_of_ways(int n) { // Array including number // of ways that includes 3 int []includes_3 = new int[n + 1]; // Array including number of // ways that doesn't includes 3 int []not_includes_3 = new int[n + 1]; // Initially to reach 3 stairs by // taking 3 steps can be // reached by 1 way includes_3[3] = 1; not_includes_3[1] = 1; not_includes_3[2] = 2; not_includes_3[3] = 3; // Loop to find the number // the number of ways to reach Nth stair for (int i = 4; i <= n; i++) { includes_3[i] = includes_3[i - 1] + includes_3[i - 2] + not_includes_3[i - 3]; not_includes_3[i] = not_includes_3[i - 1] + not_includes_3[i - 2]; } return includes_3[n]; } // Driver Code public static void main(String[] args) { int n = 7; System.out.print(number_of_ways(n)); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation to find the number # the number of ways to reach Nth stair # by taking 1, 2 step at a time and # 3 Steps at a time exactly once. # Function to find the number # the number of ways to reach Nth stair def number_of_ways(n): # Array including number # of ways that includes 3 includes_3 = [0]*(n + 1) # Array including number of # ways that doesn't includes 3 not_includes_3 = [0] * (n + 1) # Initially to reach 3 stairs by # taking 3 steps can be # reached by 1 way includes_3[3] = 1 not_includes_3[1] = 1 not_includes_3[2] = 2 not_includes_3[3] = 3 # Loop to find the number # the number of ways to reach Nth stair for i in range(4, n + 1): includes_3[i] = includes_3[i - 1] + \ includes_3[i - 2] + \ not_includes_3[i - 3] not_includes_3[i] = not_includes_3[i - 1] + \ not_includes_3[i - 2] return includes_3[n] # Driver Code n = 7 print(number_of_ways(n)) # This code is contributed by mohit kumar 29
C#
// C# implementation to find the number // the number of ways to reach Nth stair // by taking 1, 2 step at a time and // 3 Steps at a time exactly once. using System; class GFG { // Function to find the number // the number of ways to reach Nth stair static int number_of_ways(int n) { // Array including number // of ways that includes 3 int []includes_3 = new int[n + 1]; // Array including number of // ways that doesn't includes 3 int []not_includes_3 = new int[n + 1]; // Initially to reach 3 stairs by // taking 3 steps can be // reached by 1 way includes_3[3] = 1; not_includes_3[1] = 1; not_includes_3[2] = 2; not_includes_3[3] = 3; // Loop to find the number // the number of ways to reach Nth stair for (int i = 4; i <= n; i++) { includes_3[i] = includes_3[i - 1] + includes_3[i - 2] + not_includes_3[i - 3]; not_includes_3[i] = not_includes_3[i - 1] + not_includes_3[i - 2]; } return includes_3[n]; } // Driver Code public static void Main(String[] args) { int n = 7; Console.Write(number_of_ways(n)); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // JavaScript implementation to find the number // the number of ways to reach Nth stair // by taking 1, 2 step at a time and // 3 Steps at a time exactly once. // Function to find the number // the number of ways to reach Nth stair function number_of_ways(n) { // Array including number // of ways that includes 3 let includes_3 = new Uint8Array(n + 1); // Array including number of // ways that doesn't includes 3 let not_includes_3 = new Uint8Array(n + 1); // Initially to reach 3 stairs by // taking 3 steps can be // reached by 1 way includes_3[3] = 1; not_includes_3[1] = 1; not_includes_3[2] = 2; not_includes_3[3] = 3; // Loop to find the number // the number of ways to reach Nth stair for (let i = 4; i <= n; i++) { includes_3[i] = includes_3[i - 1] + includes_3[i - 2] + not_includes_3[i - 3]; not_includes_3[i] = not_includes_3[i - 1] + not_includes_3[i - 2]; } return includes_3[n]; } // Driver Code let n = 7; document.write(number_of_ways(n)); // This code is contributed by Surbhi Tyagi. </script>
20
Artículo similar: Cuente las formas de llegar a Nth Stair usando 1, 2 o 3 pasos a la vez
Publicación traducida automáticamente
Artículo escrito por shubhank7673 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA