一个CS面试题: 一个骰子最多掷三次，求最佳策略 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一个CS面试题: 一个骰子最多掷三次，求最佳策略

一个CS面试题: 一个骰子最多掷三次，求最佳策略# JobHunting - 待字闺中

l*n2010-09-07 07:09

1 楼

一个program的PM让我去NSF review panel
审几个proposal，都是同一类topic的
但是我刚投了一个同样topic的到这个PROGRAM
是不是就是等到过我PROPOSAL的时候要把我excuse一下？

h*82010-09-07 07:09

2 楼

有一个普通6面骰子，游戏者最多掷三次，可以选择掷一次或两次后停止。奖金是最后
一次的骰子的点数乘上100美元。比如最后一次是6点，获得600美元。如果是3点，获得
300美元。
请问如何找出最佳策略这样游戏者可以获得最多的奖金？

n*l2010-09-07 07:09

3 楼

要是你的proposal也在那个Panel的话，你就能看到是谁审
你的proposal，这应该不行吧？

【在 l********n 的大作中提到】

: 一个program的PM让我去NSF review panel
: 审几个proposal，都是同一类topic的
: 但是我刚投了一个同样topic的到这个PROGRAM
: 是不是就是等到过我PROPOSAL的时候要把我excuse一下？

x*p2010-09-07 07:09

4 楼

The expectation of the number of points for each throw is
(1/6)(1+2+3+4+5+6) = 3.5
So the best strategy is:
If you get 4, 5 or 6, stop, otherwise, throw 2nd or 3rd time.

l*n2010-09-07 07:09

5 楼

对啊，是很奇怪啊
但是应该是一个panel
完全同样的topic
而且很窄的topic
我和pm说我愿意去了
看他怎么回复吧。。。

【在 n*******l 的大作中提到】

: 要是你的proposal也在那个Panel的话，你就能看到是谁审
: 你的proposal，这应该不行吧？

d*s2010-09-07 07:09

6 楼

ha. I didn't get why it's a interview question for CS.

【在 x*****p 的大作中提到】

: The expectation of the number of points for each throw is
: (1/6)(1+2+3+4+5+6) = 3.5
: So the best strategy is:
: If you get 4, 5 or 6, stop, otherwise, throw 2nd or 3rd time.

m*c2010-09-07 07:09

7 楼

you are not eligible for this, direct COI. The PI must have made some
mistake not recogonized your name or something.

【在 l********n 的大作中提到】

h*82010-09-07 07:09

8 楼

我怎么觉得不应该这么简单？你如何证明这是最优？
比如如果第1次是4点，我觉得应该还要掷第2次或者第3次，因为再掷2次里面出现5或者
6的概率大于50%。

【在 x*****p 的大作中提到】

: The expectation of the number of points for each throw is
: (1/6)(1+2+3+4+5+6) = 3.5
: So the best strategy is:
: If you get 4, 5 or 6, stop, otherwise, throw 2nd or 3rd time.

l*d2010-09-07 07:09

9 楼

这个肯定不行！
你要提醒pm说
你有proposal在同一个panel里。

【在 l********n 的大作中提到】

f*g2010-09-07 07:09

10 楼

Each roll is independent, and every time there is 1/6 chance to get each
number.

【在 h****8 的大作中提到】

: 我怎么觉得不应该这么简单？你如何证明这是最优？
: 比如如果第1次是4点，我觉得应该还要掷第2次或者第3次，因为再掷2次里面出现5或者
: 6的概率大于50%。

u*n2010-09-07 07:09

11 楼

It happened to me once. Just email PM to explain the situation. Most likely
s/he made a mistake.

h*k2010-09-07 07:09

12 楼

好像不对。
你的分析对第二次是对的，即如果是4、5、6就不掷了。但是对第一次掷就不对了，因
为第二次掷的期待值变了。
对于第一次，我们知道如果掷第二次，可能的平均收益是4+5+6+3.5*3，这里3.5*3是指
第二次如果掷出1、2、3，我们肯定要掷第三次，所以掷1、2、3的平均收益都是3.5。
这样第二次掷的平均收益是(4+5+6+3.5*3)/6=4.25 > 4。
所以总的策略是，第一次掷出5、6不再掷，如果1、2、3、4掷第二次；第二次掷出4、5
、6不再掷，如果1、2、3掷第三次。

【在 x*****p 的大作中提到】

: The expectation of the number of points for each throw is
: (1/6)(1+2+3+4+5+6) = 3.5
: So the best strategy is:
: If you get 4, 5 or 6, stop, otherwise, throw 2nd or 3rd time.

f*y2010-09-07 07:09

13 楼

用动态规划做，
第三次的期望值是3.5，所以当第二次是4,5,6时停止，这样仍完第一次后的期望是，
1/2*（3.5）+1/6(4+5+6)=4.25,也就是说如果第一次是5或6，停止，否则继续仍。总的
期望值是,2/3*(4.25)+1/6(5+6)=4.83,即483元。

【在 h****8 的大作中提到】

: 有一个普通6面骰子，游戏者最多掷三次，可以选择掷一次或两次后停止。奖金是最后
: 一次的骰子的点数乘上100美元。比如最后一次是6点，获得600美元。如果是3点，获得
: 300美元。
: 请问如何找出最佳策略这样游戏者可以获得最多的奖金？

d*e2010-09-07 07:09

14 楼

都是独立事件，出现5和6的概率不变。
赞成大过3就停

【在 h****8 的大作中提到】

d*e2010-09-07 07:09

15 楼

嗯，有道理。thanks

、5

【在 h**k 的大作中提到】

: 好像不对。
: 你的分析对第二次是对的，即如果是4、5、6就不掷了。但是对第一次掷就不对了，因
: 为第二次掷的期待值变了。
: 对于第一次，我们知道如果掷第二次，可能的平均收益是4+5+6+3.5*3，这里3.5*3是指
: 第二次如果掷出1、2、3，我们肯定要掷第三次，所以掷1、2、3的平均收益都是3.5。
: 这样第二次掷的平均收益是(4+5+6+3.5*3)/6=4.25 > 4。
: 所以总的策略是，第一次掷出5、6不再掷，如果1、2、3、4掷第二次；第二次掷出4、5
: 、6不再掷，如果1、2、3掷第三次。

h*82010-09-07 07:09

16 楼

你的分析似乎合理。但是你怎么证明这是最优的？

、5

【在 h**k 的大作中提到】

h*k2010-09-07 07:09

17 楼

考虑了所有可能的情况下，这个策略的期待值最大，所以是最优的。

【在 h****8 的大作中提到】

: 你的分析似乎合理。但是你怎么证明这是最优的？
:
: 、5

t*a2010-09-07 07:09

18 楼

if we have two chances to throw the dice, let X and Y denote the number in
the first and second throw respectively:
P(Max(x,y)=1) = P(x=1)*P(y=1) = 1/6 * 1/6 = 1/36
P(Max(x,y)=2) = P(x=2)*P(y<2) + P(x<2)*P(y=2) + P(x=2)*P(y=2) = 1/6 * 1/6 *
3 = 3/36
P(Max(x,y)=3) = P(x=3)*P(y<3) + P(x<3)*P(y=3) + P(x=3)*P(y=3) = 1/6 * 2/6 *
2 + 1/6 * 1/6 = 5/36
P(Max(x,y)=4) = P(x=4)*P(y<4) + P(x<4)*P(y=4) + P(x=4)*P(y=4) = 1/6 * 3/6 *
2 + 1/6 * 1/6 = 7/36
P(Max(x,y)=5) = P(x=5)*P(y<5) + P(x<5)*P(y=5) + P(x=5)*P

f*y2010-09-07 07:09

19 楼

The answer is right, but the logic is wrong, as you can only throw the dice
sequentially.

*
*
*
*

【在 t****a 的大作中提到】

: if we have two chances to throw the dice, let X and Y denote the number in
: the first and second throw respectively:
: P(Max(x,y)=1) = P(x=1)*P(y=1) = 1/6 * 1/6 = 1/36
: P(Max(x,y)=2) = P(x=2)*P(y<2) + P(x<2)*P(y=2) + P(x=2)*P(y=2) = 1/6 * 1/6 *
: 3 = 3/36
: P(Max(x,y)=3) = P(x=3)*P(y<3) + P(x<3)*P(y=3) + P(x=3)*P(y=3) = 1/6 * 2/6 *
: 2 + 1/6 * 1/6 = 5/36
: P(Max(x,y)=4) = P(x=4)*P(y<4) + P(x<4)*P(y=4) + P(x=4)*P(y=4) = 1/6 * 3/6 *
: 2 + 1/6 * 1/6 = 7/36
: P(Max(x,y)=5) = P(x=5)*P(y<5) + P(x<5)*P(y=5) + P(x=5)*P

t*a2010-09-07 07:09

20 楼

Nothing wrong.
The sequential have nothing to do with the strategy after the first round.
Only the distribution of Max(x,y) does matter with our choice.

dice

【在 f********y 的大作中提到】

: The answer is right, but the logic is wrong, as you can only throw the dice
: sequentially.
:
: *
: *
: *
: *

d*22010-09-07 07:09

21 楼

wrong. 4.25 is correct answer for two throws.

【在 t****a 的大作中提到】

: Nothing wrong.
: The sequential have nothing to do with the strategy after the first round.
: Only the distribution of Max(x,y) does matter with our choice.
:
: dice

f*y2010-09-07 07:09

22 楼

你计算第二三投dice的期望是完全信息下的情况，也就是说你可以投两次而取其最大，
而实际的情况是你投了第二次后，要做一个选择要不要投第三次，这两个的期望值是不
一样的，前者总是大于后者，因为是完全信息下的期望值。
如果这个dice有12点，你的结论也就不一定正确，就目前的题目，这两者的期望值都在
4和5之间，所以你的结论是对的。

【在 t****a 的大作中提到】

: Nothing wrong.
: The sequential have nothing to do with the strategy after the first round.
: Only the distribution of Max(x,y) does matter with our choice.
:
: dice

t*a2010-09-07 07:09

23 楼

奖金是最后一次的骰子的点数乘上100美元。
you are right.

【在 f********y 的大作中提到】

: 你计算第二三投dice的期望是完全信息下的情况，也就是说你可以投两次而取其最大，
: 而实际的情况是你投了第二次后，要做一个选择要不要投第三次，这两个的期望值是不
: 一样的，前者总是大于后者，因为是完全信息下的期望值。
: 如果这个dice有12点，你的结论也就不一定正确，就目前的题目，这两者的期望值都在
: 4和5之间，所以你的结论是对的。

p*72010-09-07 07:09

24 楼

第一次投的是四的话，那么后面2次投的都小于等于四的概率是2/3*2/3 = 4/9，所以其
实第一次是4，还可以投。
第二次投的是大于等于4就不投了，如果小于，继续投

h*82010-09-07 07:09

25 楼

请问动态规划的英文是什么？想去补习一下这方面的概率知识。

【在 f********y 的大作中提到】

: 用动态规划做，
: 第三次的期望值是3.5，所以当第二次是4,5,6时停止，这样仍完第一次后的期望是，
: 1/2*（3.5）+1/6(4+5+6)=4.25,也就是说如果第一次是5或6，停止，否则继续仍。总的
: 期望值是,2/3*(4.25)+1/6(5+6)=4.83,即483元。

f*y2010-09-07 07:09

26 楼

dynamic programing

【在 h****8 的大作中提到】

: 请问动态规划的英文是什么？想去补习一下这方面的概率知识。

d*g2010-09-07 07:09

27 楼

This a quant interview question. Using backward method and optimal american
option pricing.

d*j2010-09-07 07:09

28 楼

哈哈. 我也在面试中被问过这个问题，当时没有回答出来，已经没有时间了
简单的说，根据给n次机会的期望值E(n)来确定当前是否停止。
用递推的思想，把投掷的n次机会分成第一次和后(n-1)次。
如果第一次的值大于E(n-1)，那么马上停止，否则的话，用(n-1)的投掷策略。
假定第n次投掷骰子的值为 v_n，
用 avg(1:v_n)表示1,2,...,v_n的期望/均值，
avg(v_n:6)表示v_n, v_n+1,...,6的期望/均值，
那么可以得出这样的迭代:
E(1) = 3.5 (=1/6 * 1 + 1/6 *2 ....+ 1/6 * 6)
E(2) = P(v_1E(1))* avg(v_1:6)
= 1/2 * 3.5 + 1/2 * avg(4,5,6) = 4.25
E(3) = P(v_2E(2)) * avg(5,6)
= 4/6 * 4.25 + 2/6 * 5.5
....
E(n) = P( v_(n-1) < E(n-1) ) *

d*j2010-09-07 07:09

29 楼

打过3就停的策略是不对的。
反例就是，给你100次，1000次机会，还是大过3就停？
肯定是扔到6出现了才停啊，机会多的是啊