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
|
