Cuente todos los resultados únicos posibles realizando S lanzamientos en N monedas

Posted on by Rudeus Greyrat

Dados dos enteros positivos N y S , la tarea es contar el número de resultados únicos posibles cuando se realizan S operaciones de volteo en N monedas.

Ejemplos:

Entrada: N = 3, S = 4
Salida: 3
Explicación: Considerando que la configuración inicial de monedas es “HHH”, entonces las posibles combinaciones de 4 lanzamientos son:

  1. Lanzar la primera y la segunda moneda una vez y la tercera moneda dos veces modifica la configuración a “TTH”.
  2. Lanzar la 1ª y 3ª moneda una vez y la 2ª moneda dos veces modifica la configuración a “THT”.
  3. Lanzar la segunda y la tercera moneda una vez y la primera moneda dos veces modifica la configuración a “HTT”.

Las tres combinaciones anteriores son únicas. Por lo tanto, la cuenta total es 3.

Entrada: N = 3, S = 6
Salida: 4

Enfoque ingenuo: el problema dado se puede resolver utilizando la recursividad cuyo estado recursivo se define como:

  • Considere que F(N, S) representa el número de resultados únicos cuando se lanzan N monedas con el número total de lanzamientos igual a S.
  • Entonces F(N, S) también se puede expresar como la suma de todas las combinaciones con 1 lanzamiento o 2 lanzamientos, es decir,

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

  • El caso base para esta relación de recurrencia es F(K, K) cuyo valor es 1 para todo (K > 1) .
  • A continuación se muestra la tabla que muestra la distribución de F(N, S) = F(N – 1, S – 1) + F(N – 1, S – 2) , donde F(K, K) = 1 .

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

  • Declare una función, digamos numberOfUniqueOutcomes(N, S) que tome la cantidad de monedas y lanzamientos permitidos como parámetros respectivamente y realice los siguientes pasos:
    • Si el valor de S es menor que N , devuelve 0 desde la función.
    • Si el valor de N es S o 1 , devuelva 1 de la función, ya que esta es una de las combinaciones únicas.
    • Devuelve recursivamente la suma de los dos estados recursivos como:

devuelve númeroDeResultadosÚnicos(N – 1, S – 1) + númeroDeResultadosÚnicos(N – 1, S – 2)

  • Después de completar los pasos anteriores, imprima el valor devuelto por la función numberOfUniqueOutcomes(N, S) como el número resultante de resultados.

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 recursively count the
// number of unique outcomes possible
// S flips are performed on N coins
int numberOfUniqueOutcomes(int N, int S)
{
    // Base Cases
    if (S < N)
        return 0;
    if (N == 1 || N == S)
        return 1;
 
    // Recursive Calls
    return (numberOfUniqueOutcomes(N - 1, S - 1)
            + numberOfUniqueOutcomes(N - 1, S - 2));
}
 
// Driver Code
int main()
{
    int N = 3, S = 4;
 
    cout << numberOfUniqueOutcomes(N, S);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
class GFG
{
 
  // Function to recursively count the
  // number of unique outcomes possible
  // S flips are performed on N coins
  static int numberOfUniqueOutcomes(int N, int S)
  {
 
    // Base Cases
    if (S < N)
      return 0;
    if (N == 1 || N == S)
      return 1;
 
    // Recursive Calls
    return (numberOfUniqueOutcomes(N - 1, S - 1)
            + numberOfUniqueOutcomes(N - 1, S - 2));
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    int N = 3, S = 4;
    System.out.println(numberOfUniqueOutcomes(N, S));
  }
}
 
//  This code is contributed by avanitrachhadiya2155

Python3

# Python3 program for the above approach
 
# Function to recursively count the
# number of unique outcomes possible
# S flips are performed on N coins
def numberOfUniqueOutcomes(N, S):
     
    # Base Cases
    if (S < N):
        return 0
    if (N == 1 or N == S):
        return 1
 
    # Recursive Calls
    return (numberOfUniqueOutcomes(N - 1, S - 1) +
            numberOfUniqueOutcomes(N - 1, S - 2))
 
# Driver Code
if __name__ == '__main__':
     
    N, S = 3, 4
 
    print (numberOfUniqueOutcomes(N, S))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to recursively count the
// number of unique outcomes possible
// S flips are performed on N coins
static int numberOfUniqueOutcomes(int N, int S)
{
     
    // Base Cases
    if (S < N)
        return 0;
    if (N == 1 || N == S)
        return 1;
     
    // Recursive Calls
    return (numberOfUniqueOutcomes(N - 1, S - 1) +
            numberOfUniqueOutcomes(N - 1, S - 2));
}
 
// Driver Code
static public void Main()
{
    int N = 3, S = 4;
     
    Console.WriteLine(numberOfUniqueOutcomes(N, S));
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
        // Javascript program for the above approach
 
        // Function to recursively count the
        // number of unique outcomes possible
        // S flips are performed on N coins
        function numberOfUniqueOutcomes(N, S) {
            // Base Cases
            if (S < N)
                return 0;
            if (N == 1 || N == S)
                return 1;
 
            // Recursive Calls
            return (numberOfUniqueOutcomes(N - 1, S - 1)
                + numberOfUniqueOutcomes(N - 1, S - 2));
        }
 
        // Driver Code
 
        let N = 3, S = 4;
 
        document.write(numberOfUniqueOutcomes(N, S))
 
        // This code is contributed by Hritik
    </script>
Producción: 

3

 

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

Enfoque eficiente: el enfoque anterior también se puede optimizar almacenando los estados recursivos, ya que contiene subproblemas superpuestos . Por lo tanto, la idea es utilizar la memorización para almacenar los estados repetidos. Siga los pasos a continuación para resolver el problema:

  • Inicialice una array 2D , digamos dp[][] de dimensiones N*M tales que dp[i][j] almacene la cantidad de resultados posibles usando i monedas y j cantidad de lanzamientos.
  • Declare una función, digamos numberOfUniqueOutcomes(N, S) , que tome la cantidad de monedas y lanzamientos permitidos como parámetros respectivamente y realice los siguientes pasos:
    • Si el valor de S es menor que N , actualice el valor de dp[N][S] como 0 y devuelva este valor desde la función.
    • Si el valor de N es S o 1 , actualice el valor de dp[N][S] como 1 y devuelva este valor de la función, ya que esta es una de las combinaciones únicas.
    • Si el valor de dp[N][S] ya está calculado, devuelva el valor dp[N][S] de la función.
    • Actualice recursivamente el valor de la suma de dp[N][S] de los dos estados recursivos como se muestra a continuación y devuelva este valor de la función.

dp[N][S] = númeroDeResultadosÚnicos(N – 1, S – 1) + númeroDeResultadosÚnicos(N – 1, S – 2)

  • Después de completar los pasos anteriores, imprima el valor devuelto por la función numberOfUniqueOutcomes(N, S) como el número resultante de resultados.

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;
 
// Dimensions of the DP table
#define size 1001
 
// Stores the dp states
int ans[size][size] = { 0 };
 
// Function to recursively count the
// number of unique outcomes possible
// by performing S flips on N coins
int numberOfUniqueOutcomes(int n, int s)
{
    // Base Case
    if (s < n)
        ans[n][s] = 0;
 
    else if (n == 1 || n == s)
        ans[n][s] = 1;
 
    // If the count for the current
    // state is not calculated, then
    // calculate it recursively
    else if (!ans[n][s]) {
        ans[n][s] = numberOfUniqueOutcomes(n - 1,
                                           s - 1)
                    + numberOfUniqueOutcomes(n - 1,
                                             s - 2);
    }
 
    // Otherwise return the
    // already calculated value
    return ans[n][s];
}
 
// Driver Code
int main()
{
    int N = 5, S = 8;
 
    cout << numberOfUniqueOutcomes(N, S);
 
    return 0;
}

Java

// Java program for the above approach
 
import java.util.*;
 
class GFG{
  
 // Dimensions of the DP table
static int size = 100;
static int [][]ans = new int[size][size];
   
static void initialize()
{
   
  // Stores the dp states
  for(int i = 0; i < size; i++)
  {
    for(int j = 0; j < size; j++)
    {
        ans[i][j] = 0;
    }
}
}
 
// Function to recursively count the
// number of unique outcomes possible
// by performing S flips on N coins
static int numberOfUniqueOutcomes(int n, int s)
{
    // Base Case
    if (s < n)
        ans[n][s] = 0;
 
    else if (n == 1 || n == s)
        ans[n][s] = 1;
 
    // If the count for the current
    // state is not calculated, then
    // calculate it recursively
    else if (ans[n][s] == 0) {
        ans[n][s] = numberOfUniqueOutcomes(n - 1,
                                           s - 1)
                    + numberOfUniqueOutcomes(n - 1,
                                             s - 2);
    }
 
    // Otherwise return the
    // already calculated value
    return ans[n][s];
}
 
// Driver Code
public static void main(String args[])
{
    initialize();
    int N = 5, S = 8;
    System.out.println(numberOfUniqueOutcomes(N, S));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

Python3

# Python3 program for the above approach
 
# Dimensions of the DP table
size = 100
 
# Stores the dp states
ans = [[0 for i in range(size)]
          for j in range(size)]
 
# Function to recursively count the
# number of unique outcomes possible
# by performing S flips on N coins
def numberOfUniqueOutcomes(n, s):
     
    # Base Case
    if (s < n):
        ans[n][s] = 0;
     
    elif (n == 1 or n == s):
        ans[n][s] = 1;
     
    # If the count for the current
    # state is not calculated, then
    # calculate it recursively
    elif(ans[n][s] == 0):
        ans[n][s] = (numberOfUniqueOutcomes(n - 1, s - 1) +
                     numberOfUniqueOutcomes(n - 1, s - 2))
     
    # Otherwise return the
    # already calculated value
    return ans[n][s];
 
# Driver Code
N = 5
S = 8
 
print(numberOfUniqueOutcomes(N, S))
 
# This code is contributed by rag2127

C#

// C# program for the above approach
using System;
 
class GFG{
  
// Dimensions of the DP table
static int size = 100;
static int [,]ans = new int[size, size];
   
static void initialize()
{
   
    // Stores the dp states
    for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size; j++)
        {
            ans[i, j] = 0;
        }
    }
}
 
// Function to recursively count the
// number of unique outcomes possible
// by performing S flips on N coins
static int numberOfUniqueOutcomes(int n, int s)
{
     
    // Base Case
    if (s < n)
        ans[n, s] = 0;
 
    else if (n == 1 || n == s)
        ans[n, s] = 1;
 
    // If the count for the current
    // state is not calculated, then
    // calculate it recursively
    else if (ans[n, s] == 0)
    {
        ans[n, s] = numberOfUniqueOutcomes(n - 1,
                                           s - 1) +
                    numberOfUniqueOutcomes(n - 1,
                                           s - 2);
    }
 
    // Otherwise return the
    // already calculated value
    return ans[n,s];
}
 
// Driver Code
public static void Main(string []args)
{
    initialize();
    int N = 5, S = 8;
     
    Console.WriteLine(numberOfUniqueOutcomes(N, S));
}
}
 
// This code is contributed by AnkThon

Javascript

<script>
 
    // JavaScript program for the above approach
     
    // Dimensions of the DP table
    let size = 100;
    let ans = new Array(size);
 
    function initialize()
    {
 
      // Stores the dp states
      for(let i = 0; i < size; i++)
      {
          ans[i] = new Array(size);
        for(let j = 0; j < size; j++)
        {
            ans[i][j] = 0;
        }
      }
    }
 
    // Function to recursively count the
    // number of unique outcomes possible
    // by performing S flips on N coins
    function numberOfUniqueOutcomes(n, s)
    {
        // Base Case
        if (s < n)
            ans[n][s] = 0;
 
        else if (n == 1 || n == s)
            ans[n][s] = 1;
 
        // If the count for the current
        // state is not calculated, then
        // calculate it recursively
        else if (ans[n][s] == 0) {
            ans[n][s] = numberOfUniqueOutcomes(n - 1,
                                               s - 1)
                        + numberOfUniqueOutcomes(n - 1,
                                                 s - 2);
        }
 
        // Otherwise return the
        // already calculated value
        return ans[n][s];
    }
     
    initialize();
    let N = 5, S = 8;
    document.write(numberOfUniqueOutcomes(N, S));
     
</script>
Producción: 

15

 

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

Publicación traducida automáticamente

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