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:
- Lanzar la primera y la segunda moneda una vez y la tercera moneda dos veces modifica la configuración a “TTH”.
- Lanzar la 1ª y 3ª moneda una vez y la 2ª moneda dos veces modifica la configuración a “THT”.
- 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