由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 没看懂leetcode大牛关于一道概率题的答案
相关主题
这题怎么做?再问个C programming考试的题目
Leetcode 689居然是fb的高频题?用python写leetcode,sys.maxint怎么办?
发个论坛上某已经淡出隐牛的一道Google Onsite概率题Leetcode上的Unique Paths II,我的code对吗?
Leetcode Combination Sum复杂度leetcode triganle 通不过。。。
Leetcode Two Sum,我这个O(n)解法为啥不讨服务器的好呢请教一个leetcode上的题
leetcode题,有的看不了??Leetcode上面的题Max Points on a Line
question about Leetcode #113 LeetCode – Path Sum II (Java)Pairwise Sum 算法follow up
LeetCode Medium被刷差不多了是不是可以面很多公司了?Google电面
相关话题的讨论汇总
话题: max话题: trials话题: sum话题: value话题: 筛子
进入JobHunting版参与讨论
1 (共1页)
f*********m
发帖数: 726
1
原帖:
http://www.mitbbs.com/article_t1/JobHunting/32293265_0_1.html
题目:
给一个筛子, 最大可以抛3次, 每次可以选择是否继续丢, 给一个策略让最后筛子的
点数最大化。
比如如果第一次丢就得到1点,很明显需要继续下去
如果第一次丢得到6点,很明显没必要继续下去,因为后面再丢的两次最大也不会超过
六点
如果第一次丢得到5点,可能要考虑是不是博一下了。
扩展问题是把3次推广到N次。
*****
Leetcode大牛给的答案:
给个数学公式。这道题应该也可以用递推来解,但还没想清楚怎么弄。
Define:
n = number of trials.
m = max value of all trials.
P(m, n) = (1/6^n) * Sum(k = 1 .. n) C(n, k) * (m - 1)^(n - k)
Therefore,
Expected value of max value after n trials:
E = Sum(k = 1 .. 6) k * P(k, n)
E(Max when Trials = 1) = 3.5
E(Max when Trials = 2) = 4.4722
E(Max when Trials = 3) = 4.9583
E(Max when Trials = 4) = 5.2446
所以,只要看期望值,就知道需不需要再扔筛子了。
《〈〈〈〈〈〈〈〈〈〈〈〈〈〈〈
请问各位公式中(m - 1)^(n - k)是怎么来的?
谢谢。
s*********l
发帖数: 103
2

http://www.spellscroll.com/spellscrolls/question/_--5PjOWfgA/
dynamic programming
E(1次) = 3.5
E(2次) = 3/6*3.5 + 1/6*(4+5+6) = 17/4 = 4.25
E(3次) = 4/6*4.25 + 1/6*(5+6) = 14/3
...
E(N次) = \sum_i=1^6 1/6 * max(i, E(N-1次))

【在 f*********m 的大作中提到】
: 原帖:
: http://www.mitbbs.com/article_t1/JobHunting/32293265_0_1.html
: 题目:
: 给一个筛子, 最大可以抛3次, 每次可以选择是否继续丢, 给一个策略让最后筛子的
: 点数最大化。
: 比如如果第一次丢就得到1点,很明显需要继续下去
: 如果第一次丢得到6点,很明显没必要继续下去,因为后面再丢的两次最大也不会超过
: 六点
: 如果第一次丢得到5点,可能要考虑是不是博一下了。
: 扩展问题是把3次推广到N次。

s*********l
发帖数: 103
3

E(N = 4) = 89/18 < 5
E(N = 5) = 277/54 = 6 - 47/54
E(N >= 5) = 6 - 47/54*(5/6)^(N-5) -> 6

【在 s*********l 的大作中提到】
:
: http://www.spellscroll.com/spellscrolls/question/_--5PjOWfgA/
: dynamic programming
: E(1次) = 3.5
: E(2次) = 3/6*3.5 + 1/6*(4+5+6) = 17/4 = 4.25
: E(3次) = 4/6*4.25 + 1/6*(5+6) = 14/3
: ...
: E(N次) = \sum_i=1^6 1/6 * max(i, E(N-1次))

r*********n
发帖数: 4553
4
T(n) n throw expected value
the recursion is given by
T(n) = 1/6 * \sum_{i=1}^6 ( max(i - T(n-1), 0) + T(n-1) )
T(0) = 0
f******t
发帖数: 18
5
正解

【在 s*********l 的大作中提到】
:
: E(N = 4) = 89/18 < 5
: E(N = 5) = 277/54 = 6 - 47/54
: E(N >= 5) = 6 - 47/54*(5/6)^(N-5) -> 6

a*******6
发帖数: 520
6
嗯,spellscroll这个才是正解,如果看不懂可以参看刚刚我写的细化版本的解:
http://www.mitbbs.com/article/JobHunting/32351345_0.html
两者等价

【在 s*********l 的大作中提到】
:
: E(N = 4) = 89/18 < 5
: E(N = 5) = 277/54 = 6 - 47/54
: E(N >= 5) = 6 - 47/54*(5/6)^(N-5) -> 6

f*********m
发帖数: 726
7
\sum_i=1^6是说i从1到6?

【在 s*********l 的大作中提到】
:
: E(N = 4) = 89/18 < 5
: E(N = 5) = 277/54 = 6 - 47/54
: E(N >= 5) = 6 - 47/54*(5/6)^(N-5) -> 6

s******u
发帖数: 550
8
新人飘过
EE的看CS的文字果然着急,完全看不懂
如果我来回答,答案如下
假设最多可以抛N次,当前已经抛了n(1<=n 下面决定抛不抛下一次,
考虑之后的N-n次抛出不能比m点数大的概率为 1-(m/6)^(N-n)
然后看这个概率比不比0.5大就好了,为什么一定要用dynamic programming呢?
求解各位大牛
R******1
发帖数: 58
9
C(n, k) * (m - 1)^(n - k)
是个排列,因为最大值的是m,所以出现的值小于等于m
假设有k个m出现,另外的(n-k)个都是小于m的,也就是说(m-1)种可能
所以 C(n,k) k个m出现的位置 * (m-1)^(n-k) 另外(n-k)个位置的可能性
PS: 建议看8楼surexuxu的解答,更简练直接。

【在 f*********m 的大作中提到】
: 原帖:
: http://www.mitbbs.com/article_t1/JobHunting/32293265_0_1.html
: 题目:
: 给一个筛子, 最大可以抛3次, 每次可以选择是否继续丢, 给一个策略让最后筛子的
: 点数最大化。
: 比如如果第一次丢就得到1点,很明显需要继续下去
: 如果第一次丢得到6点,很明显没必要继续下去,因为后面再丢的两次最大也不会超过
: 六点
: 如果第一次丢得到5点,可能要考虑是不是博一下了。
: 扩展问题是把3次推广到N次。

R******1
发帖数: 58
10
这个很赞,直接简捷!

【在 s******u 的大作中提到】
: 新人飘过
: EE的看CS的文字果然着急,完全看不懂
: 如果我来回答,答案如下
: 假设最多可以抛N次,当前已经抛了n(1<=n: 下面决定抛不抛下一次,
: 考虑之后的N-n次抛出不能比m点数大的概率为 1-(m/6)^(N-n)
: 然后看这个概率比不比0.5大就好了,为什么一定要用dynamic programming呢?
: 求解各位大牛

R******1
发帖数: 58
11
你的这个不对吧,反例是E(2) = 161/36 = 4.4722 (leetcode的答案是对的)
暴力枚举就可以:
E(2) = (1*1 + 2*3 + 3*5 + 4*7 + 5*9 + 6*11) / 36
说不上你的逻辑哪里不对,但是3/6*3.5感觉怪怪的。

【在 s*********l 的大作中提到】
:
: E(N = 4) = 89/18 < 5
: E(N = 5) = 277/54 = 6 - 47/54
: E(N >= 5) = 6 - 47/54*(5/6)^(N-5) -> 6

1 (共1页)
进入JobHunting版参与讨论
相关主题
Google电面Leetcode Two Sum,我这个O(n)解法为啥不讨服务器的好呢
求一个array的算法题leetcode题,有的看不了??
请教一个老算法题, k-th largest sumquestion about Leetcode #113 LeetCode – Path Sum II (Java)
请问那个给leetcode题目难易程度list的网站是什么?LeetCode Medium被刷差不多了是不是可以面很多公司了?
这题怎么做?再问个C programming考试的题目
Leetcode 689居然是fb的高频题?用python写leetcode,sys.maxint怎么办?
发个论坛上某已经淡出隐牛的一道Google Onsite概率题Leetcode上的Unique Paths II,我的code对吗?
Leetcode Combination Sum复杂度leetcode triganle 通不过。。。
相关话题的讨论汇总
话题: max话题: trials话题: sum话题: value话题: 筛子