Imprime todas las formas de llegar al N-ésimo escalón con el salto de 1 o 2 unidades a la vez

Posted on by Rudeus Greyrat

Dado un número entero positivo N que representa N escalones y una persona en el primer escalón , la tarea es imprimir todas las formas de llegar al N escalón con el salto de 1 o 2 unidades a la vez.

Ejemplos:

Entrada: N = 3
Salida: 
11
2
Explicación:
La enésima escalera se puede alcanzar de las siguientes maneras con saltos de 1 o 2 unidades cada una como:

  1. Realiza los dos saltos de 1 unidad cada uno como 1 -> 1.
  2. Realiza los dos saltos de 1 unidad cada uno como 2.

Entrada: N = 5
Salida:
1111
112
121
211
22

 

Enfoque: El problema dado se puede resolver usando recursividad . La idea es cubrir los dos casos de uno o dos saltos a la vez en cada índice e imprimir todas las formas posibles de llegar al peldaño N. Siga los pasos a continuación para resolver el problema dado:

  • Defina una función recursiva, digamos totalPossibleJumps(int N) que devuelva todas las formas posibles de saltos para llegar al N -ésimo escalón .
    • En el punto de partida de la verificación de recursividad para los casos base como:
      • Si N < 0 , entonces no es una forma válida. Así que devuelve una array vacía
      • Si N = 0 , entonces es una forma válida. Así que devuelva una array de tamaño 1 que contenga un espacio vacío.
    • Llame a la función recursiva dos veces en cada llamada recursiva, una para el salto de 1 unidad y otra para el salto de 2 unidades y almacene los resultados por separado.
    • Inicialice una array de strings , digamos totalJumps para almacenar formas de alcanzar el i -ésimo índice y almacene todas las formas posibles de alcanzar el índice i con los resultados almacenados en las dos llamadas recursivas anteriores.
  • Después de completar los pasos anteriores, imprima todas las combinaciones posibles devueltas por las llamadas recursivas anteriores como totalPossibleJumps(N) .

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all the ways to reach
// Nth stair using one or two jumps
vector<string> TotalPossibleJumps(int N)
{
    // Base Cases
    if ((N - 1) == 0) {
        vector<string> newvec;
        newvec.push_back("");
        return newvec;
    }
    else {
        if (N < 0) {
            vector<string> newvec;
            return newvec;
        }
    }
 
    // Recur for jump1 and jump2
    vector<string> jump1
        = TotalPossibleJumps(N - 1);
    vector<string> jump2
        = TotalPossibleJumps(N - 2);
 
    // Stores the total possible jumps
    vector<string> totaljumps;
 
    // Add "1" with every element
    // present in jump1
    for (string s : jump1) {
        totaljumps.push_back("1" + s);
    }
 
    // Add "2" with every element
    // present in jump2
    for (string s : jump2) {
        totaljumps.push_back("2" + s);
    }
 
    return totaljumps;
}
 
// Driver Code
int main()
{
    int N = 3;
    vector<string> Ans = TotalPossibleJumps(N);
    for (auto& it : Ans)
        cout << it << '\n';
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    // Function to find all the ways to reach
    // Nth stair using one or two jumps
    static ArrayList<String> TotalPossibleJumps(int N)
    {
        // Base Cases
        if ((N - 1) == 0) {
            ArrayList<String> newvec
                = new ArrayList<String>();
            newvec.add("");
            return newvec;
        }
        else {
            if (N < 0) {
                ArrayList<String> newvec
                    = new ArrayList<String>();
                return newvec;
            }
        }
 
        // Recur for jump1 and jump2
        ArrayList<String> jump1 = TotalPossibleJumps(N - 1);
        ArrayList<String> jump2 = TotalPossibleJumps(N - 2);
 
        // Stores the total possible jumps
        ArrayList<String> totaljumps
            = new ArrayList<String>();
 
        // Add "1" with every element
        // present in jump1
        for (String s : jump1) {
            totaljumps.add("1" + s);
        }
 
        // Add "2" with every element
        // present in jump2
        for (String s : jump2) {
            totaljumps.add("2" + s);
        }
 
        return totaljumps;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 3;
        ArrayList<String> Ans = TotalPossibleJumps(N);
        for (String it : Ans)
            System.out.println(it);
    }
}
 
// This code is contributed by ukasp.

Python3

# python program for the above approach
 
# Function to find all the ways to reach
# Nth stair using one or two jumps
 
 
def TotalPossibleJumps(N):
 
    # Base Cases
    if ((N - 1) == 0):
        newvec = []
        newvec.append("")
        return newvec
 
    else:
        if (N < 0):
            newvec = []
            return newvec
 
    # Recur for jump1 and jump2
    jump1 = TotalPossibleJumps(N - 1)
    jump2 = TotalPossibleJumps(N - 2)
 
    # Stores the total possible jumps
    totaljumps = []
 
    # Add "1" with every element
    # present in jump1
    for s in jump1:
        totaljumps.append("1" + s)
 
    # Add "2" with every element
    # present in jump2
    for s in jump2:
        totaljumps.append("2" + s)
 
    return totaljumps
 
 
# Driver Code
if __name__ == "__main__":
 
    N = 3
    Ans = TotalPossibleJumps(N)
    for it in Ans:
        print(it)
 
    # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find all the ways to reach
// Nth stair using one or two jumps
static List<string> TotalPossibleJumps(int N)
{
    // Base Cases
    if ((N - 1) == 0) {
        List<string> newvec = new List<string>();
        newvec.Add("");
        return newvec;
    }
    else {
        if (N < 0) {
            List<string> newvec = new List<string>();
            return newvec;
        }
    }
 
    // Recur for jump1 and jump2
    List<string> jump1
        = TotalPossibleJumps(N - 1);
    List<string> jump2
        = TotalPossibleJumps(N - 2);
 
    // Stores the total possible jumps
    List<string> totaljumps = new List<string>();
 
    // Add "1" with every element
    // present in jump1
    foreach (string s in jump1) {
        totaljumps.Add("1" + s);
    }
 
    // Add "2" with every element
    // present in jump2
    foreach (string s in jump2) {
        totaljumps.Add("2" + s);
    }
 
    return totaljumps;
}
 
// Driver Code
public static void Main()
{
    int N = 3;
    List<string> Ans = TotalPossibleJumps(N);
    foreach(string it in Ans)
        Console.WriteLine(it);
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function to find all the ways to reach
    // Nth stair using one or two jumps
    const TotalPossibleJumps = (N) => {
        // Base Cases
        if ((N - 1) == 0) {
            let newvec = [];
            newvec.push("");
            return newvec;
        }
        else {
            if (N < 0) {
                let newvec = [];
                return newvec;
            }
        }
 
        // Recur for jump1 and jump2
        let jump1 = TotalPossibleJumps(N - 1);
        let jump2 = TotalPossibleJumps(N - 2);
 
        // Stores the total possible jumps
        let totaljumps = [];
 
        // Add "1" with every element
        // present in jump1
        for (let s in jump1) {
            totaljumps.push("1" + jump1[s]);
        }
 
        // Add "2" with every element
        // present in jump2
        for (let s in jump2) {
            totaljumps.push("2" + jump2[s]);
        }
 
        return totaljumps;
    }
 
    // Driver Code
 
    let N = 3;
    let Ans = TotalPossibleJumps(N);
    for (let it in Ans)
        document.write(`${Ans[it]}<br/>`);
 
// This code is contributed by rakeshsahni
</script>
Producción: 

11
2

 

Complejidad temporal: O(2 N ) 
Espacio auxiliar: O(N)  

Publicación traducida automáticamente

Artículo escrito por user_ax8z 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 *