Dado un número entero N que denota el número de dados, la tarea es encontrar la probabilidad de cada valor posible que se puede obtener lanzando N dados juntos.
Ejemplos:
Entrada: N = 1
Salida:
1: 0,17
2: 0,17
3: 0,17
4: 0,17
5: 0,17
6: 0,17
Explicación: Al lanzar un dado, la probabilidad de que todos los valores de [1, 6] aparezcan en la parte superior es 1 /6 = 0,17Entrada: N = 2
Salida:
2: 0,028
3: 0,056
4: 0,083
5: 0,11
6: 0,14
7: 0,17
8: 0,14
9: 0,11
10: 0,083
11: 0,056
12: 0,028
Explicación: Los posibles valores de la suma de los dos números que aparecen en la parte superior al lanzar dos dados juntos oscila entre [2, 12].
Enfoque: La idea es utilizar la programación dinámica y la tabla DP para almacenar la probabilidad de cada valor posible.
- Almacena las probabilidades de los 6 números que pueden aparecer al lanzar 1 dado.
- Ahora, para N=2, la probabilidad de todas las sumas posibles entre [2, 12] es igual a la suma del producto de la probabilidad respectiva de los dos números que suman esa suma. Por ejemplo,
Probabilidad de 4 al lanzar 2 dados = (Probabilidad de 1) * (Probabilidad de 3) + (Probabilidad de 2) * (Probabilidad de 2) + (Probabilidad de 3) * (Probabilidad de 1)
- Por lo tanto, para N dados,
Probabilidad de Sumar S = (Probabilidad de 1) * (Probabilidad de S – 1 usando N-1 dados) + (Probabilidad de 2) * (Probabilidad de S – 2 usando N-1 dados) + ….. + (Probabilidad de 6) * (Probabilidad de S – 6 usando N -1 dados)
- Por lo tanto, para resolver el problema, necesitamos llenar la tabla dp[][] de 2 a N usando un enfoque de arriba hacia abajo usando la relación:
dp[i][x] = dp[1][y] + dp[i-1][z] donde x = y + z e i denota el número de dados
- Muestre todas las probabilidades almacenadas para N como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to calculate
// the probability of
// all the possible values
// that can be obtained
// throwing N dices
#include <bits/stdc++.h>
using namespace std;
void dicesSum(int n)
{
// Store the probabilities
vector<map<int, double> > dp(n + 1);
// Precompute the probabilities
// for values possible using 1 dice
dp[1] = { { 1, 1 / 6.0 },
{ 2, 1 / 6.0 },
{ 3, 1 / 6.0 },
{ 4, 1 / 6.0 },
{ 5, 1 / 6.0 },
{ 6, 1 / 6.0 } };
// Compute the probabilities
// for all values from 2 to N
for (int i = 2; i <= n; i++) {
for (auto a1 : dp[i - 1]) {
for (auto a2 : dp[1]) {
dp[i][a1.first + a2.first]
+= a1.second * a2.second;
}
}
}
// Print the result
for (auto a : dp[n]) {
cout << a.first << " "
<< setprecision(2)
<< a.second
<< endl;
}
}
// Driver code
int main()
{
int n = 2;
dicesSum(n);
return 0;
}
Java
// Java program to calculate
// the probability of all the
// possible values that can
// be obtained throwing N dices
import java.io.*;
import java.util.*;
class GFG{
static void dicesSum(int n)
{
// Store the probabilities
double[][] dp = new double[n + 1][6 * n + 1];
// Precompute the probabilities
// for values possible using 1 dice
for(int i = 1; i <= 6; i++)
dp[1][i] = 1 / 6.0;
// Compute the probabilities
// for all values from 2 to N
for(int i = 2; i <= n; i++)
for(int j = i - 1; j <= 6 * (i - 1); j++)
for(int k = 1; k <= 6; k++)
{
dp[i][j + k] += (dp[i - 1][j] *
dp[1][k]);
}
// Print the result
for(int i = n; i <= 6 * n; i++)
{
System.out.println(i + " " +
Math.round(dp[n][i] * 1000.0) /
1000.0);
}
}
// Driver Code
public static void main(String[] args)
{
int n = 2;
dicesSum(n);
}
}
// This code is contributed by jithin
Python3
# Python3 program to calculate
# the probability of all the
# possible values that can
# be obtained throwing N dices
def diceSum(n):
# Initialize a 2d array upto
# (n*total sum possible) sum
# with value 0
dp = [[ 0 for j in range(n * 6)]
for i in range(n + 1)]
# Store the probability in a
# single throw for 1,2,3,4,5,6
for i in range(6):
dp[1][i] = 1 / 6
# Compute the probabilities
# for all values from 2 to N
for i in range(2, n + 1):
for j in range(len(dp[i - 1])):
for k in range(6):
if (dp[i - 1][j] != 0 and
dp[i - 1][k] != 0):
dp[i][j + k] += (dp[i - 1][j] *
dp[1][k])
# Print the result
for i in range(len(dp[n]) - n + 1):
print("%d %0.3f" % (i + n, dp[n][i]))
# Driver code
n = 2
# Call the function
diceSum(n)
# This code is contributed by dipesh99kumar
C#
// C# program to calculate
// the probability of all the
// possible values that can
// be obtained throwing N dices
using System;
class GFG {
static void dicesSum(int n)
{
// Store the probabilities
double[,] dp = new double[n + 1,6 * n + 1];
// Precompute the probabilities
// for values possible using 1 dice
for(int i = 1; i <= 6; i++)
dp[1,i] = 1 / 6.0;
// Compute the probabilities
// for all values from 2 to N
for(int i = 2; i <= n; i++)
for(int j = i - 1; j <= 6 * (i - 1); j++)
for(int k = 1; k <= 6; k++)
{
dp[i,j + k] += (dp[i - 1,j] *
dp[1,k]);
}
// Print the result
for(int i = n; i <= 6 * n; i++)
{
Console.WriteLine(i + " " +
Math.Round(dp[n,i] * 1000.0) /
1000.0);
}
}
static void Main() {
int n = 2;
dicesSum(n);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript program to calculate
// the probability of all the
// possible values that can
// be obtained throwing N dices
function dicesSum(n)
{
// Store the probabilities
let dp = new Array(n+1);
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 < 6 * n + 1; j++) {
dp[i][j] = 0;
}
}
// Precompute the probabilities
// for values possible using 1 dice
for(let i = 1; i <= 6; i++)
dp[1][i] = 1 / 6.0;
// Compute the probabilities
// for all values from 2 to N
for(let i = 2; i <= n; i++)
for(let j = i - 1; j <= 6 * (i - 1); j++)
for(let k = 1; k <= 6; k++)
{
dp[i][j + k] += (dp[i - 1][j] *
dp[1][k]);
}
// Print the result
for(let i = n; i <= 6 * n; i++)
{
document.write(i + " " +
Math.round(dp[n][i] * 1000.0) /
1000.0 + "<br/>");
}
}
// Driver Code
let n = 2;
dicesSum(n);
</script>
2 0.028 3 0.056 4 0.083 5 0.11 6 0.14 7 0.17 8 0.14 9 0.11 10 0.083 11 0.056 12 0.028
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )