Probabilidad de que la suma de todos los números obtenidos al lanzar un dado N veces esté entre dos enteros dados

Posted on by Rudeus Greyrat

Dados tres números enteros N , A y B , la tarea es calcular la probabilidad de que la suma de los números obtenidos al lanzar los dados exactamente N veces se encuentre entre A y B .

Ejemplos:

Entrada: N = 1, A = 2, B = 3
Salida: 0.333333
Explicación: Formas de obtener la suma 2 por N ( = 1) lanzamientos de dados es 1 {2}. Por lo tanto, probabilidad requerida = 1/6 = 0.33333

Entrada: N = 2, A = 3, B = 4
Salida: 0,138889

 

Enfoque recursivo: siga los pasos a continuación para resolver el problema:

  • Calcula las probabilidades de todos los números entre A y B y súmalos para obtener la respuesta.
  • Llame a la función find(N, sum) para calcular la probabilidad de cada número de a a b , donde un número entre a y b se pasará como sum .
    • Los casos base son:
      • Si la suma es mayor que 6 * N o menor que N , entonces devuelva 0 ya que es imposible tener una suma mayor que N * 6 o menor que  N .
      • Si N es igual a 1 y la suma está entre 1 y 6, devuelve 1/6.
    • Dado que en cada estado puede salir cualquier número del 1 al 6 en un solo lanzamiento de dados, por lo tanto, se debe hacer una llamada recursiva para la (suma hasta ese estado – i) donde 1≤ i ≤ 6.
    • Devuelve la probabilidad resultante.

Llamada recursiva:
f(n, sum)=\sum_{i=1}^6\frac{f(n-1, sum-i)}{6}

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

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the
// probability for the given
// sum to be equal to sum in
// N throws of dice
long double find(int N, int sum)
{
    // Base cases
    if (sum > 6 * N || sum < N)
        return 0;
 
    if (N == 1) {
 
        if (sum >= 1 && sum <= 6)
            return 1.0 / 6;
        else
            return 0;
    }
    long double s = 0;
    for (int i = 1; i <= 6; i++)
        s = s + find(N - 1, sum - i) / 6;
 
    return s;
}
 
// Driver Code
int main()
{
    int N = 4, a = 13, b = 17;
    long double probability = 0.0;
 
    for (int sum = a; sum <= b; sum++)
        probability = probability + find(N, sum);
 
    // Print the answer
    cout << fixed << setprecision(6) << probability;
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to calculate the
// probability for the given
// sum to be equal to sum in
// N throws of dice
static double find(int N, int sum)
{
    // Base cases
    if (sum > 6 * N || sum < N)
        return 0;
    if (N == 1)
    {
        if (sum >= 1 && sum <= 6)
            return 1.0 / 6;
        else
            return 0;
    }
    double s = 0;
    for (int i = 1; i <= 6; i++)
        s = s + find(N - 1, sum - i) / 6;
    return s;
}
   
// Driver code
public static void main(String[] args)
{
    int N = 4, a = 13, b = 17;
    double probability = 0.0;
    for (int sum = a; sum <= b; sum++)
        probability = probability + find(N, sum);
 
    // Print the answer
    System.out.format("%.6f", probability);
}
}
 
// This code is contributed by code_hunt.

Python3

# Python 2 program for above approach
 
# Function to calculate the
# probability for the given
# sum to be equal to sum in
# N throws of dice
def find(N, sum):
 
    # Base cases
    if (sum > 6 * N or sum < N):
        return 0
    if (N == 1):
        if (sum >= 1 and sum <= 6):
            return 1.0 / 6
        else:
            return 0
    s = 0
    for i in range(1, 7):
        s = s + find(N - 1, sum - i) / 6
    return s
 
# Driver Code
if __name__ == "__main__":
    N = 4
    a = 13
    b = 17
    probability = 0.0
    for sum in range(a, b + 1):
        probability = probability + find(N, sum)
 
    # Print the answer
    print(round(probability, 6))
 
    # This code is contributed by chitranayal.

C#

// C# program for the above approach
using System;
class GFG
{
     
    // Function to calculate the
    // probability for the given
    // sum to be equal to sum in
    // N throws of dice
    static double find(int N, int sum)
    {
       
        // Base cases
        if (sum > 6 * N || sum < N)
            return 0;
        if (N == 1)
        {
            if (sum >= 1 && sum <= 6)
                return 1.0 / 6;
            else
                return 0;
        }
        double s = 0;
        for (int i = 1; i <= 6; i++)
            s = s + find(N - 1, sum - i) / 6;
        return s;
    }
 
  // Driver code
  static void Main()
  {
    int N = 4, a = 13, b = 17;
    double probability = 0.0;
    for (int sum = a; sum <= b; sum++)
        probability = probability + find(N, sum);
  
    // Print the answer
    Console.WriteLine(Math.Round(probability,6));
  }
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
    // Javascript program for the above approach
     
    // Function to calculate the
    // probability for the given
    // sum to be equal to sum in
    // N throws of dice
    function find(N, sum)
    {
        
        // Base cases
        if (sum > 6 * N || sum < N)
            return 0;
        if (N == 1)
        {
            if (sum >= 1 && sum <= 6)
                return 1.0 / 6;
            else
                return 0;
        }
        let s = 0;
        for (let i = 1; i <= 6; i++)
            s = s + find(N - 1, sum - i) / 6;
        return s;
    }
     
    let N = 4, a = 13, b = 17;
    let probability = 0.0;
    for (let sum = a; sum <= b; sum++)
        probability = probability + find(N, sum);
   
    // Print the answer
    document.write(probability.toFixed(6));
   
</script>
Producción: 

0.505401

 

Complejidad de Tiempo: O((b-a+1)6 n )
Espacio Auxiliar: O(1)

Enfoque de programación dinámica: el enfoque recursivo anterior debe optimizarse al tratar los siguientes subproblemas superpuestos y la subestructura óptima :

Subproblemas superpuestos:
Árbol de recurrencia parcial para N=4 y suma=15:

Subestructura óptima:
para cada estado, se repite para otros 6 estados, por lo que la definición recursiva de f (N, sum) es:

dp[N][sum]=\sum_{i=1}^6\frac{dp[N-1][sum-i]}{6}

Enfoque de arriba hacia abajo: 

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
float dp[105][605];
 
// Function to calculate the
// probability for the given
// sum to be equal to sum in
// N throws of dice
float find(int N, int sum)
{
    if (dp[N][sum])
        return dp[N][sum];
 
    // Base cases
    if (sum > 6 * N || sum < N)
        return 0;
    if (N == 1) {
        if (sum >= 1 && sum <= 6)
            return 1.0 / 6;
        else
            return 0;
    }
    for (int i = 1; i <= 6; i++)
        dp[N][sum] = dp[N][sum]
                     + find(N - 1, sum - i) / 6;
    return dp[N][sum];
}
 
// Driver Code
int main()
{
    int N = 4, a = 13, b = 17;
    float probability = 0.0;
 
    // Calculate probability of all
    // sums from a to b
    for (int sum = a; sum <= b; sum++)
        probability = probability + find(N, sum);
 
    // Print the answer
    cout << fixed << setprecision(6) << probability;
    return 0;
}

Java

// Java program for above approach
class GFG
{
    static float[][] dp = new float[105][605];
 
    // Function to calculate the
    // probability for the given
    // sum to be equal to sum in
    // N throws of dice
    static float find(int N, int sum)
    {
        if (N < 0 | sum < 0)
            return 0;
        if (dp[N][sum] > 0)
            return dp[N][sum];
 
        // Base cases
        if (sum > 6 * N || sum < N)
            return 0;
        if (N == 1) {
            if (sum >= 1 && sum <= 6)
                return (float) (1.0 / 6);
            else
                return 0;
        }
        for (int i = 1; i <= 6; i++)
            dp[N][sum] = dp[N][sum] + find(N - 1, sum - i) / 6;
        return dp[N][sum];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 4, a = 13, b = 17;
        float probability = 0.0f;
 
        // Calculate probability of all
        // sums from a to b
        for (int sum = a; sum <= b; sum++)
            probability = probability + find(N, sum);
 
        // Print the answer
        System.out.printf("%.6f", probability);
    }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python program for above approach
dp = [[0 for i in range(605)] for j in range(105)];
 
# Function to calculate the
# probability for the given
# sum to be equal to sum in
# N throws of dice
def find(N, sum):
    if (N < 0 | sum < 0):
        return 0;
    if (dp[N][sum] > 0):
        return dp[N][sum];
 
    # Base cases
    if (sum > 6 * N or sum < N):
        return 0;
    if (N == 1):
        if (sum >= 1 and sum <= 6):
            return (float)(1.0 / 6);
        else:
            return 0;
 
    for i in range(1,7):
        dp[N][sum] = dp[N][sum] + find(N - 1, sum - i) / 6;
    return dp[N][sum];
 
# Driver Code
if __name__ == '__main__':
    N = 4; a = 13; b = 17;
    probability = 0.0
    f = 0;
 
    # Calculate probability of all
    # sums from a to b
    for sum in range(a,b+1):
        probability = probability + find(N, sum);
 
    # Print the answer
    print("%.6f"% probability);
 
# This code is contributed by 29AjayKumar

C#

// C# program for above approach
using System;
using System.Collections.Generic;
public class GFG
{
  static float[,] dp = new float[105, 605];
 
  // Function to calculate the
  // probability for the given
  // sum to be equal to sum in
  // N throws of dice
  static float find(int N, int sum)
  {
    if (N < 0 | sum < 0)
      return 0;
    if (dp[N, sum] > 0)
      return dp[N, sum];
 
    // Base cases
    if (sum > 6 * N || sum < N)
      return 0;
    if (N == 1) {
      if (sum >= 1 && sum <= 6)
        return (float) (1.0 / 6);
      else
        return 0;
    }
    for (int i = 1; i <= 6; i++)
      dp[N, sum] = dp[N, sum] + find(N - 1, sum - i) / 6;
    return dp[N, sum];
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int N = 4, a = 13, b = 17;
    float probability = 0.0f;
 
    // Calculate probability of all
    // sums from a to b
    for (int sum = a; sum <= b; sum++)
      probability = probability + find(N, sum);
 
    // Print the answer
    Console.Write("{0:F6}", probability);
  }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for above approach
 
var dp = Array(105).fill().map(()=>Array(605).fill(0.0));
 
// Function to calculate the
// probability for the given
// sum to be equal to sum in
// N throws of dice
function find(N, sum)
{
    if (N < 0 | sum < 0)
        return 0;
    if (dp[N][sum] > 0)
        return dp[N][sum];
 
    // Base cases
    if (sum > 6 * N || sum < N)
        return 0;
    if (N == 1)
    {
        if (sum >= 1 && sum <= 6)
            return  (1.0 / 6);
        else
            return 0;
    }
     
    for(var i = 1; i <= 6; i++)
        dp[N][sum] = dp[N][sum] +
           find(N - 1, sum - i) / 6;
            
    return dp[N][sum];
}
 
// Driver Code
var N = 4, a = 13, b = 17;
var probability = 0.0;
 
// Calculate probability of all
// sums from a to b
for(sum = a; sum <= b; sum++)
    probability = probability + find(N, sum);
 
// Print the answer
document.write(probability.toFixed(6));
 
// This code is contributed by umadevi9616
 
</script>
Producción: 

0.505401

 

Complejidad de Tiempo: O(n*sum)
Espacio Auxiliar: O(n*sum)

Enfoque de abajo hacia arriba:

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
float dp[105][605];
 
// Function to calculate probability
// that the sum of numbers on N throws
// of dice lies between A and B
float find(int N, int a, int b)
{
    float probability = 0.0;
 
    // Base case
    for (int i = 1; i <= 6; i++)
        dp[1][i] = 1.0 / 6;
 
    for (int i = 2; i <= N; i++) {
 
        for (int j = i; j <= 6 * i; j++) {
 
            for (int k = 1; k <= 6; k++) {
 
                dp[i][j] = dp[i][j]
                           + dp[i - 1][j - k] / 6;
            }
        }
    }
 
    // Add the probability for all
    // the numbers between a and b
    for (int sum = a; sum <= b; sum++)
        probability = probability + dp[N][sum];
 
    return probability;
}
 
// Driver Code
int main()
{
    int N = 4, a = 13, b = 17;
 
    float probability = find(N, a, b);
 
    // Print the answer
    cout << fixed << setprecision(6) << probability;
    return 0;
}

Java

// Java program for above approach
import java.util.*;
 
class GFG{
static float [][]dp = new float[105][605];
 
// Function to calculate probability
// that the sum of numbers on N throws
// of dice lies between A and B
static float find(int N, int a, int b)
{
    float probability = 0.0f;
 
    // Base case
    for (int i = 1; i <= 6; i++)
        dp[1][i] = (float) (1.0 / 6);
    for (int i = 2; i <= N; i++)
    {
        for (int j = i; j <= 6 * i; j++)
        {
            for (int k = 1; k <= 6 && k <= j; k++)
            {
                dp[i][j] = dp[i][j]
                           + dp[i - 1][j - k] / 6;
            }
        }
    }
 
    // Add the probability for all
    // the numbers between a and b
    for (int sum = a; sum <= b; sum++)
        probability = probability + dp[N][sum];
    return probability;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 4, a = 13, b = 17;
    float probability = find(N, a, b);
 
    // Print the answer
    System.out.printf("%.6f",probability);
}
}
 
// This codeis contributed by shikhasingrajput

Python3

# Python3 program for above approach
 
dp = [[0 for i in range(605)] for j in range(105)]
 
# Function to calculate probability
# that the sum of numbers on N throws
# of dice lies between A and B
def find(N, a, b) :
 
    probability = 0.0
  
    # Base case
    for i in range(1, 7) :
        dp[1][i] = 1.0 / 6
  
    for i in range(2, N + 1) :
  
        for j in range(i, (6*i) + 1) :
  
            for k in range(1, 7) :
  
                dp[i][j] = dp[i][j] + dp[i - 1][j - k] / 6
  
    # Add the probability for all
    # the numbers between a and b
    for Sum in range(a, b + 1) :
        probability = probability + dp[N][Sum]
  
    return probability
     
N, a, b = 4, 13, 17
 
probability = find(N, a, b)
 
# Print the answer
print('%.6f'%probability)
 
# This code is contributed by divyesh072019.

C#

// C# program for above approach
using System;
public class GFG
{
static float [,]dp = new float[105, 605];
 
// Function to calculate probability
// that the sum of numbers on N throws
// of dice lies between A and B
static float find(int N, int a, int b)
{
    float probability = 0.0f;
 
    // Base case
    for (int i = 1; i <= 6; i++)
        dp[1, i] = (float) (1.0 / 6);
    for (int i = 2; i <= N; i++)
    {
        for (int j = i; j <= 6 * i; j++)
        {
            for (int k = 1; k <= 6 && k <= j; k++)
            {
                dp[i, j] = dp[i, j]
                           + dp[i - 1, j - k] / 6;
            }
        }
    }
 
    // Add the probability for all
    // the numbers between a and b
    for (int sum = a; sum <= b; sum++)
        probability = probability + dp[N, sum];
    return probability;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 4, a = 13, b = 17;
    float probability = find(N, a, b);
 
    // Print the answer
    Console.Write("{0:F6}",probability);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// Javascript program of the above approach
let dp = new Array(105);
 
// Loop to create 2D array using 1D array
for(var i = 0; i < dp.length; i++)
{
    dp[i] = new Array(2);
}
 
for(var i = 0; i < dp.length; i++)
{
    for(var j = 0; j < dp.length; j++)
    {
        dp[i][j] = 0;
    }
}
  
// Function to calculate probability
// that the sum of numbers on N throws
// of dice lies between A and B
function find(N, a, b)
{
    let probability = 0.0;
  
    // Base case
    for(let i = 1; i <= 6; i++)
        dp[1][i] =  (1.0 / 6);
         
    for(let i = 2; i <= N; i++)
    {
        for(let j = i; j <= 6 * i; j++)
        {
            for(let k = 1; k <= 6 && k <= j; k++)
            {
                dp[i][j] = dp[i][j] +
                           dp[i - 1][j - k] / 6;
            }
        }
    }
  
    // Add the probability for all
    // the numbers between a and b
    for(let sum = a; sum <= b; sum++)
        probability = probability + dp[N][sum];
         
    return probability;
}
 
// Driver Code
let N = 4, a = 13, b = 17;
let probability = find(N, a, b);
 
// Print the answer
document.write(probability);
 
// This code is contributed by chinmoy1997pal
 
</script>
Producción: 

0.505401

 

Complejidad de Tiempo: O(N * suma)
Espacio Auxiliar: O(N * suma)

Publicación traducida automáticamente

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