Estación de tren | Código TCS Vita 2020

Posted on by Rudeus Greyrat

Dado un número entero N , que representa el número de estaciones que se encuentran entre el origen y el destino. Hay tres trenes disponibles en cada estación y sus patrones de parada son los siguientes:

  • Tren 1: Para en todas las estaciones
  • Tren 2: Para en cada estación alternativa
  • Tren 3: Para en cada tercera estación

La tarea es encontrar el número de formas de llegar al destino desde el origen utilizando cualquier combinación posible de trenes.

Ejemplos:

Entrada: N = 2 
Salida: 4
Explicación: 
Existen cuatro formas posibles de viajar desde el origen hasta el destino con 2 estaciones en medio:
Tren 1 (desde el origen) -> Tren 1 (desde la estación 1) -> Tren 1 (desde la estación 2) -> Tren de destino
2 (desde el origen) -> Tren 1 (desde la estación 2) ->
Tren de destino 1 (desde el origen) -> Tren 2 (desde la estación 1) ->
Tren de destino 3 (desde el origen) -> Destino

Entrada: N = 0
Salida: 1
Explicación: No hay ninguna estación presente entre el origen y el destino. Por lo tanto, solo hay una forma de viajar, es decir,
Tren 1 (desde el origen) -> Destino

Enfoque: La idea principal para resolver el problema es usar Recursión con Memoización para resolver este problema. La relación de recurrencia es la siguiente:

 F(N) = F(N – 1) + F(N – 2) + F(N – 3),

donde,
F(N – 1) cuenta las formas de viajar hasta (N – 1) la estación.
F(N – 2) cuenta las formas de viajar hasta (N – 2) la estación.
F(N – 3) cuenta las formas de viajar hasta (N – 3) la estación.

Siga los pasos a continuación para resolver el problema:

  1. Inicialice una array dp[] para memorización. Establezca todos los índices en -1 inicialmente.
  2. Defina una función recursiva findWays() para calcular el número de formas de llegar a la N -ésima estación.
  3. Se requiere considerar los siguientes casos base:
    • Para x < 0 devuelve 0.
    • Para x = 0 , devuelve 1.
    • Para x = 1 , devuelve 2.
    • Para x = 2, devuelve 4.
  4. Si el estado actual, digamos x , ya está evaluado, es decir, dp[x] no es igual a -1 , simplemente devuelva el valor evaluado.
  5. De lo contrario, calcule findWays(x – 1) , findWays(x – 2) y findWays(x – 3) recursivamente y almacene su suma en dp[x] .
  6. Retorna dp[x] .

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

C++14

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Dp table for memoization
int dp[100000];
 
// Function to count the number
// of ways to N-th station
int findWays(int x)
{
    // Base Cases
    if (x < 0)
        return 0;
 
    if (x == 0)
        return 1;
 
    if (x == 1)
        return 2;
 
    if (x == 2)
        return 4;
 
    // If current state is
    // already evaluated
    if (dp[x] != -1)
        return dp[x];
 
    // Recursive calls
 
    // Count ways in which
    // train 1 can be chosen
    int count = findWays(x - 1);
 
    // Count ways in which
    // train 2 can be chosen
    count += findWays(x - 2);
 
    // Count ways in which
    // train 3 can be chosen
    count += findWays(x - 3);
 
    // Store the current state
    dp[x] = count;
 
    // Return the number of ways
    return dp[x];
}
 
// Driver Code
int main()
{
 
    // Given Input
    int n = 4;
 
    // Initialize DP table with -1
    memset(dp, -1, sizeof(dp));
 
    // Function call to count
    // the number of ways to
    // reach the n-th station
    cout << findWays(n) << "\n";
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Dp table for memoization
  static int dp[] = new int[100000];
 
  // Function to count the number
  // of ways to N-th station
  static int findWays(int x)
  {
 
    // Base Cases
    if (x < 0)
      return 0;
 
    if (x == 0)
      return 1;
 
    if (x == 1)
      return 2;
 
    if (x == 2)
      return 4;
 
    // If current state is
    // already evaluated
    if (dp[x] != -1)
      return dp[x];
 
    // Recursive calls
 
    // Count ways in which
    // train 1 can be chosen
    int count = findWays(x - 1);
 
    // Count ways in which
    // train 2 can be chosen
    count += findWays(x - 2);
 
    // Count ways in which
    // train 3 can be chosen
    count += findWays(x - 3);
 
    // Store the current state
    dp[x] = count;
 
    // Return the number of ways
    return dp[x];
  }
 
  // Driven Code
  public static void main(String[] args)
  {
 
    // Given Input
    int n = 4;
 
    // Initialize DP table with -1
    Arrays.fill(dp, -1);
 
    // Function call to count
    // the number of ways to
    // reach the n-th station
    System.out.print(findWays(n));
  }
}
 
// This code is contributed by splevel62.

Python3

# Python3 program of the above approach
 
# Dp table for memoization
dp = [-1 for i in range(100000)]
 
# Function to count the number
# of ways to N-th station
def findWays(x):
     
    # Base Cases
    if (x < 0):
        return 0
 
    if (x == 0):
        return 1
 
    if (x == 1):
        return 2
 
    if (x == 2):
        return 4
 
    # If current state is
    # already evaluated
    if (dp[x] != -1):
        return dp[x]
 
    # Recursive calls
 
    # Count ways in which
    # train 1 can be chosen
    count = findWays(x - 1)
 
    # Count ways in which
    # train 2 can be chosen
    count += findWays(x - 2)
 
    # Count ways in which
    # train 3 can be chosen
    count += findWays(x - 3)
 
    # Store the current state
    dp[x] = count
 
    # Return the number of ways
    return dp[x]
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    n = 4
     
    # Function call to count
    # the number of ways to
    # reach the n-th station
    print(findWays(n))
 
# This code is contributed by SURENDRA_GANGWAR

C#

// C# program to implement above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // Dp table for memoization
  static int[] dp = new int[100000];
 
  // Function to count the number
  // of ways to N-th station
  static int findWays(int x)
  {
    // Base Cases
    if (x < 0)
      return 0;
 
    if (x == 0)
      return 1;
 
    if (x == 1)
      return 2;
 
    if (x == 2)
      return 4;
 
    // If current state is
    // already evaluated
    if (dp[x] != -1)
      return dp[x];
 
    // Recursive calls
 
    // Count ways in which
    // train 1 can be chosen
    int count = findWays(x - 1);
 
    // Count ways in which
    // train 2 can be chosen
    count += findWays(x - 2);
 
    // Count ways in which
    // train 3 can be chosen
    count += findWays(x - 3);
 
    // Store the current state
    dp[x] = count;
 
    // Return the number of ways
    return dp[x];
  }
 
  // Driver Code
  public static void Main(string[] args){
 
    // Given Input
    int n = 4;
 
    // Initialize DP table with -1
    for(int i = 0 ; i < dp.Length ; i++){
      dp[i] = -1;
    }
 
    // Function call to count
    // the number of ways to
    // reach the n-th station
    Console.Write(findWays(n) + "\n");
 
  }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

<script>
 
// JavaScript program of the above approach
 
// Dp table for memoization
let dp = new Array(100000).fill(-1)
 
// Function to count the number
// of ways to N-th station
function findWays(x){
     
    // Base Cases
    if (x < 0)
        return 0
 
    if (x == 0)
        return 1
 
    if (x == 1)
        return 2
 
    if (x == 2)
        return 4
 
    // If current state is
    // already evaluated
    if (dp[x] != -1)
        return dp[x]
 
    // Recursive calls
 
    // Count ways in which
    // train 1 can be chosen
    let count = findWays(x - 1)
 
    // Count ways in which
    // train 2 can be chosen
    count += findWays(x - 2)
 
    // Count ways in which
    // train 3 can be chosen
    count += findWays(x - 3)
 
    // Store the current state
    dp[x] = count
 
    // Return the number of ways
    return dp[x]
}
 
// Driver Code
     
// Given Input
let n = 4
 
// Function call to count
// the number of ways to
// reach the n-th station
document.write(findWays(n))
 
// This code is contributed by shinjanpatra
 
</script>
Producción: 

13

 

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

Publicación traducida automáticamente

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