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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原帖: : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原帖: : http://www.mitbbs.com/article_t1/JobHunting/32293265_0_1.html : 题目: : 给一个筛子, 最大可以抛3次, 每次可以选择是否继续丢, 给一个策略让最后筛子的 : 点数最大化。 : 比如如果第一次丢就得到1点,很明显需要继续下去 : 如果第一次丢得到6点,很明显没必要继续下去,因为后面再丢的两次最大也不会超过 : 六点 : 如果第一次丢得到5点,可能要考虑是不是博一下了。 : 扩展问题是把3次推广到N次。
|
R******1 发帖数: 58 | 10 这个很赞,直接简捷!
【在 s******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 新人飘过 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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
|