珍珠湾ART

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

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

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

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

问题是不是应该改成，以怎样的策略才能使自己得到尽可能大的钻石？

因为要保证得到最大的钻石似乎不可能？

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

对，是尽可能大，也可以说是期望值最大

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

在达到某一层前不拿。
通过比较前几层的选较大的一个？

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

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

作者: 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

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

....

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))

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.

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

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

我想知道在美国到 Microsoft 面试，是不是也考这种问题。

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

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

作者: 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.

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

记错了，sqr(N)是另一道题

欢迎光临珍珠湾ART (http://zzwav.com/)