Dado un número entero N de escalones , la tarea es contar el número de formas de llegar al enésimo escalón dando 1 o 2 pasos cualquier número de veces pero dando un paso de 3 exactamente una vez.
Ejemplos:
Entrada: N = 4
Salida: 2
Explicación:
Ya que un paso de 3 se tiene que dar obligatoriamente y una sola vez. Entonces, solo hay dos formas posibles: (1, 3) o (3, 1)
Entrada: N = 5
Salida: 5
Explicación:
Hay cinco formas posibles de llegar al quinto escalón: (2, 3), (3, 2 ), (1, 1, 3), (1, 3, 1), (3, 1, 1)
Enfoque: este problema se puede resolver utilizando el concepto de permutaciones y combinaciones . Existe una restricción según la cual se deben tomar 3 pasos a la vez exactamente una vez. La idea es contar el número de posiciones que son posibles para dar 3 pasos.
Ahora, la siguiente tarea es encontrar el número de dos pasos posibles en el movimiento hacia el escalón N , que es (N – 3) / 2. De esta manera, se cubrirán todas las formas posibles si el conteo de dos pasos El paso se incrementa de uno en uno y para cada paso se calculan todas las combinaciones posibles.
Después de generalizar los pasos, se mostrarán las posibles combinaciones para cada secuencia posible.
Ways = (Length of sequence)! * (Count of 2-step)!
------------------------------------------
(Count of 1-step)!
Algoritmo:
- Inicialice la longitud de la secuencia a (N – 2).
- Inicialice la cuenta de 1 paso a (N – 3).
- Inicializar el conteo de 2 pasos a 0
- Inicialice la cuenta posible de 2 pasos a (N-3)/2.
- Ejecute un bucle hasta que la cuenta posible de 2 pasos sea igual a la cuenta real de 2 pasos.
- Encuentre el número posible de formas con la ayuda de la longitud actual de la secuencia, el recuento de 1 paso, el recuento de 2 pasos y las fórmulas anteriores.
- Reduce la longitud de la secuencia en 1.
- Aumente la cuenta de 2 pasos en 1
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 or 2 steps at a time and
// 3rd step exactly once
#include <bits/stdc++.h>
using namespace std;
int factorial(int n)
{
// Single line to find factorial
return (n == 1 || n == 0) ? 1 :
n * factorial(n - 1);
}
// Function to find
// the number of ways
int ways(int n)
{
// Base Case
if (n < 3)
{
return 0;
}
// Count of 2-steps
int c2 = 0;
// Count of 1-steps
int c1 = n - 3;
// Initial length of sequence
int l = c1 + 1;
int s = 0;
// Expected count of 2-steps
int exp_c2 = c1 / 2;
// Loop to find the ways for
// every possible sequence
while (exp_c2 >= c2)
{
int f1 = factorial(l);
int f2 = factorial(c1);
int f3 = factorial(c2);
int f4 = (f2 * f3);
s += f1 / f4;
c2 += 1;
c1 -= 2;
l -= 1;
}
return s;
}
// Driver code
int main()
{
int n = 7;
int ans = ways(n);
cout << ans << endl;
return 0;
}
// This code is contributed by coder001
Java
// Java implementation to find the number
// the number of ways to reach Nth stair
// by taking 1 or 2 steps at a time and
// 3rd step exactly once
class GFG {
static int factorial(int n)
{
// Single line to find factorial
return (n == 1 || n == 0) ? 1 :
n * factorial(n - 1);
}
// Function to find
// the number of ways
static int ways(int n)
{
// Base Case
if (n < 3)
{
return 0;
}
// Count of 2-steps
int c2 = 0;
// Count of 1-steps
int c1 = n - 3;
// Initial length of sequence
int l = c1 + 1;
int s = 0;
// Expected count of 2-steps
int exp_c2 = c1 / 2;
// Loop to find the ways for
// every possible sequence
while (exp_c2 >= c2)
{
int f1 = factorial(l);
int f2 = factorial(c1);
int f3 = factorial(c2);
int f4 = (f2 * f3);
s += f1 / f4;
c2 += 1;
c1 -= 2;
l -= 1;
}
return s;
}
// Driver Code
public static void main(String args[])
{
int n = 7;
int ans = ways(n);
System.out.println(ans);
}
}
// This code is contributed by rutvik_56
Python3
# Python3 implementation to find the number # the number of ways to reach Nth stair # by taking 1 or 2 steps at a time and # 3rd Step exactly once import math # Function to find # the number of ways def ways(n): # Base Case if n < 3: return 0 # Count of 2-steps c2 = 0 # Count of 1-steps c1 = n-3 # Initial length of sequence l = c1 + 1 s = 0 # expected count of 2-steps exp_c2 = c1 / 2 # Loop to find the ways for # every possible sequence while exp_c2 >= c2: f1 = math.factorial(l) f2 = math.factorial(c1) f3 = math.factorial(c2) s += f1//(f2 * f3) c2 += 1 c1 -= 2 l -= 1 return s # Driver Code if __name__ == "__main__": N = 7 print(ways(N))
C#
// C# implementation to find the number
// the number of ways to reach Nth stair
// by taking 1 or 2 steps at a time and
// 3rd step exactly once
using System;
class GFG{
static int factorial(int n)
{
// Single line to find factorial
return (n == 1 || n == 0) ? 1 :
n * factorial(n - 1);
}
// Function to find
// the number of ways
static int ways(int n)
{
// Base Case
if (n < 3)
{
return 0;
}
// Count of 2-steps
int c2 = 0;
// Count of 1-steps
int c1 = n - 3;
// Initial length of sequence
int l = c1 + 1;
int s = 0;
// Expected count of 2-steps
int exp_c2 = c1 / 2;
// Loop to find the ways for
// every possible sequence
while (exp_c2 >= c2)
{
int f1 = factorial(l);
int f2 = factorial(c1);
int f3 = factorial(c2);
int f4 = (f2 * f3);
s += f1 / f4;
c2 += 1;
c1 -= 2;
l -= 1;
}
return s;
}
// Driver code
static void Main()
{
int n = 7;
int ans = ways(n);
Console.WriteLine(ans);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript implementation to find the number
// the number of ways to reach Nth stair
// by taking 1 or 2 steps at a time and
// 3rd step exactly once
function factorial(n)
{
// Single line to find factorial
return (n == 1 || n == 0) ? 1 :
n * factorial(n - 1);
}
// Function to find
// the number of ways
function ways(n)
{
// Base Case
if (n < 3)
{
return 0;
}
// Count of 2-steps
let c2 = 0;
// Count of 1-steps
let c1 = n - 3;
// Initial length of sequence
let l = c1 + 1;
let s = 0;
// Expected count of 2-steps
let exp_c2 = Math.floor(c1 / 2);
// Loop to find the ways for
// every possible sequence
while (exp_c2 >= c2)
{
let f1 = factorial(l);
let f2 = factorial(c1);
let f3 = factorial(c2);
let f4 = (f2 * f3);
s += Math.floor(f1 / f4);
c2 += 1;
c1 -= 2;
l -= 1;
}
return s;
}
// Driver code
let n = 7;
let ans = ways(n);
document.write(ans);
// This code is contributed by Surbhi Tyagi.
</script>
20
Análisis de rendimiento:
- Complejidad de tiempo: como en el enfoque anterior, hay un ciclo para verificar las posibles permutaciones para cada secuencia que puede ir hasta (N-3) que toma tiempo O (N) y para encontrar las posibles combinaciones tomará O (N) ), Por lo tanto la Complejidad del Tiempo será O(N 2 ) .
- Complejidad espacial: como en el enfoque anterior, no se utiliza espacio adicional, por lo que la complejidad espacial será O(1) .
Nota: La complejidad del tiempo se puede mejorar hasta O(N) calculando previamente los factoriales para cada número hasta N.
Publicación traducida automáticamente
Artículo escrito por yashbeersingh42 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA