原文:
给定一个表示骰子点数的整数 n ，任务是找出将 n 个骰子扔在一起可以得到的每个可能值的概率。
示例:
输入: n = 1 输出: 1:0.17 2:0.17 3:0.17 4:0.17 5:0.17 6:0.17 说明:掷骰子时，从[1，6]开始的所有数值出现在顶部的概率为 1/6 = 0.17
输入: n = 2 输出: 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【t11
方法:思路是用和 存储每个可能值的概率。
- 存储投掷 1 个骰子时出现的所有 6 个数字的概率。
- 现在，对于 n=2，在[2，12]之间的所有可能和的概率等于加起来的两个数各自概率的乘积之和。例如，
掷出 2 个骰子概率为 4 =(概率为 1 ) (概率为 3) (概率为 2) (概率为 2) (概率为 3 ) *(概率为 1)
- 因此对于 n 个骰子，
和的概率 s =(1 的概率)(使用 n -1 个骰子 s–1 的概率) (2 的概率)(使用 n-1 个骰子 s–2 的概率) ….. (6 的概率)*(使用 n -1 个骰子的 s–6 的概率)
- 因此，为了解决这个问题，我们需要使用自上而下的方法从 2 到 n 填充 dp[][]表，使用以下关系:
dp[i][x] = dp[1][y] dp[i-1][z]，其中 x = y z，i 表示骰子数
- 显示为 n 存储的所有概率作为答案。
下面是上述方法的实现:
c
// c program to calculate
// the probability of
// all the possible values
// that can be obtained
// throwing n dices
#include
using namespace std;
void dicessum(int n)
{
// store the probabilities
vector > 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
python 3
# 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
java 描述语言
output:
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
时间复杂度:o(n2) t7】辅助空间:o(n2)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
