剖析一道拼多多的笔试算法题

标签：赋值   学校   基础   公众   方向   offer   初始   交流   cas   

微信公众号：Jerry的算法和NLP

| 题目 掷骰子

掷n个不同面数的骰子，以最大点数为结果，求点数的期望。
一共有n个骰子
第i个骰子面数为ni，点数为[1,ni]，每个面的概率相同
同时掷这n个骰子，所有骰子中的最大点数为最终点数
求骰子投出的期望值

| examlple1

输入

2
2 2

输出

1.75

| examlple2

输入

4
1 2 3 4

输出

2.875

| 分析：

这道题目主要考察的知识点为动态规划
动态规划主要就是要找准它的转移方程和base case以及目标

首先把所有骰子的输入放入xi数组中并且进行排序（倒序 从大到小）
然后建立两个列表
一个是res 存放最终的结果
一个是current 存放遍历到当前骰子的结果

1.先拿出第一个骰子 计算第一个骰子中发生每一个可能点数的概率并存入res和current中 【规定起始状态】

2.开始遍历每一个骰子 我们把当前的骰子记作P
首先先是计算P这个骰子每一面会发生的概率 就是1/P
P这个骰子在转的时候 假设最后所有骰子的点数为Q
A .之前的骰子都是＜Q P这个骰子投出了Q
B .之前的骰子刚好出现Q P这个骰子没投注Q
C .之前的骰子出现Q * 这个骰子投出了Q

3.最后把每个点数 * 概率 求出期望值

举个例子,，方便大家理解
假设现在有三个骰子
分别为2 3 4 存入X中
先将X排倒序 X=【4，3，2】
说明最多有四种情况 1，2，3，4

然后一开始初始化的时候是选择骰子面数最多的4
此时res=[0,1/4,1/4,1/4,1/4]
current=[0,1/4,1/4,1/4,1/4]

然后从第二个骰子开始遍历到第N个骰子
现在第二个骰子是3
投出1，2，3的概率都是1/3
基于第一个骰子的基础上 投出第二个骰子
那么最后结果为X的可能性由以下三个方面组成

1.之前的骰子投出的结果a=sum(res[:j])(1/xi[i])
（之前出现1，2，3，...,X-1的概率 当前出现X的概率）

2.之前骰子投出结果=X的概率 乘以 当前骰子投出b=res[j]((j-1)/xi[i]
(之前恰好是X 当前出现1，2，3，...,X-1的概率)

3.之前骰子投出X 乘以 当前骰子投出X的概率
c=res[j]*(1/xi[i])
（之前恰好是X 且当前也是X）

把三种情况的概率相加a+b+c赋值给current[i] 然后用current更新res即可

| 总结

 1n=int(input())
 2xi=list(map(int,input().split()))
 3xi.sort(reverse=True)
 4res=[0]
 5current=[0]
 6for i in range(xi[0]):
 7    res.append(1/xi[0])
 8    current.append(1/xi[0])
 9
10
11for i in range(1,n):
12    for j in range(1,xi[i]+1):
13        print(res)
14        a=sum(res[:j])*(1/xi[i])#之前的骰子投出的结果

剑指offer刷题交流群

扫码添加微信，一定要备注研究方向+地点+学校+昵称（如机器学习+上海+上交+汤姆），只有备注正确才可以加群噢。

▲长按加群

剖析一道拼多多的笔试算法题

标签：赋值   学校   基础   公众   方向   offer   初始   交流   cas   

原文地址：https://blog.51cto.com/15054042/2564174