2019校招真题--拼多多--「骰子的最大值期望」

题目描述

有 n 个骰子,每个骰子取值不同,在$[1,x_i]$之间。求投掷这 n 个骰子得到最大值的期望。

输入:两行,第一行为整数 n,第二行为 n 个整数,代表每个骰子的最大点数
输出:一个数字,代表这些骰子投掷产生的最大值的期望,保留小数点后两位

解题思路

最大值为 i 的概率 = 全部不大于 i 的概率 - 最大值小于 i 的概率。

代码

Python 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys


def get_mean(n, x):
res = {}
max_num = max(x)
prod = 1
for i in x:
prod *= i
res[1] = 1 / prod # 用来存储所有结果的概率,最后求期望
sum_old = res[1] # 已经遍历过的结果的概率和
for i in range(2, max_num + 1):
tmp = 1
for num in x:
if num >= i:
# 对所有大于等于 i 的数字算小于等于 i 的概率
tmp *= i / num
tmp -= sum_old # 最大值为 i 的概率 = 全部不大于 i 的概率 - 最大值小于 i 的概率
sum_old += tmp
res[i] = tmp
result = 0
for key, val in res.items():
# 求期望
result += key * val
return result


if __name__ == "__main__":
n = int(sys.stdin.readline().strip())
x = list(map(int, sys.stdin.readline().strip().split()))
print("{:.2f}".format(get_mean(n, x)))