珍珠湾ART

标题: 电梯问题 [打印本页]

作者: zyang131    时间: 2006-3-10 04:56
标题: 电梯问题

一楼到十楼的每层电梯门口都放着一颗钻石,钻石大小不一。你乘坐电梯从一楼到十楼,每层楼电梯门都会打开一次,只能拿一次钻石,问怎样才能拿到最大的一颗?
www.ddhw.com

 

作者: 新用户    时间: 2006-3-10 05:20
标题: 回复:电梯问题

问题是不是应该改成,以怎样的策略才能使自己得到尽可能大的钻石?
因为要保证得到最大的钻石似乎不可能?
www.ddhw.com

 

作者: zyang131    时间: 2006-3-10 06:12
标题: 回复:回复:电梯问题

对, 是尽可能大, 也可以说是期望值最大
www.ddhw.com

 

作者: math59    时间: 2006-3-10 16:17
标题: 验证下思路

在达到某一层前不拿。
通过比较前几层的选较大的一个?www.ddhw.com

 

作者: zyang131    时间: 2006-3-11 07:42
标题: 回复:电梯问题

这道题我也不知道答案, 不过我在想是不是可以象求maximun likehood estimator 那样搞一个公式出来再求极值
www.ddhw.com

 

作者: QL    时间: 2006-3-11 08:33
标题: 回复:电梯问题

Here is a simple strategy: Assume there are N floors (in this case N = 10). We pick some M
 www.ddhw.com
After the M-th floor, pick the first diamond which is larger than each of the first M diamonds.
 
To find the optimal M, we do the following calculation: let X_M be random variable of the rank of the largest diamond among all. (here we rank diamonds from small to large, so the smallest diamond gets rank 1 and the largest gets rank N), the following is easy to see:
p(X_M
p(X_M
....www.ddhw.com
and from these, we get the distribution of X_M:
p(X_M=K) = p(X_M
 
Now, the probability that the aferomentioned strategy picks the largest diamond is:
p(X_M=M)/(N-M) + p(X_M=M+1)/(N-(M+1)) + ... p(X_M=N-1)/(N-(N-1))www.ddhw.com
The idea is that, if X_M = K, then there will be N-K diamonds that are larger than any of the first M diamonds, and in order for the strategy to work, the largest diamonds has to apear first among these N-K diamonds.
 
Then, we only have to find M that maximize this probability -- I guess it will be hard to get a close form formula, but clearly solvable for a N as small as 10.
 
 
 
 


 www.ddhw.com

 

  本贴由[QL]最后编辑于:2006-3-11 8:3:32  


作者: 有空想想    时间: 2006-3-12 01:26
标题: 谁能告诉我这个问题的英文网站?我 google 半天,没找到。

我想知道在美国到 Microsoft 面试,是不是也考这种问题。
www.ddhw.com

 

作者: constant    时间: 2006-3-12 04:22
标题: 回复:电梯问题

这个问题有两个问法,一个是取得最大钻石的概率最大,一个是取得钻石大小的期望值最大。若是第一个问题,应该是放过前sqr(N)个钻石,然后取下一个比前面都大的。若是第二个问题,取法可能和钻石大小的分布有关。
www.ddhw.com

 

作者: QL    时间: 2006-3-12 06:27
标题: 回复:回复:电梯问题

若是第一个问题,应该是放过前sqr(N)个钻石,然后取下一个比前面都大的。
Can you give the proof?
 
若是第二个问题,取法可能和钻石大小的分布有关。
How about this: find a strategy, so that you will get the largest expected rank.
For example, you pick one diamond out of the 10, and it happened to be the largest, then you get a score of 10. If it is the smallest, you get a score of 1. Your goal is to maximize the expected score.
I guess this might be a hard problem.
www.ddhw.com

 

作者: constant    时间: 2006-3-13 17:50
标题: 回复:回复:回复:电梯问题

记错了,sqr(N)是另一道题
www.ddhw.com

 





欢迎光临 珍珠湾ART (http://zzwav.com/) Powered by Discuz! X3