电梯问题

zyang131 · 发表于 2006-3-10 04:56:25

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

新用户 · 发表于 2006-3-10 05:20:42

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

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

zyang131 · 发表于 2006-3-10 06:12:57

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

math59 · 发表于 2006-3-10 16:17:11

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

zyang131 · 发表于 2006-3-11 07:42:35

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

QL · 发表于 2006-3-11 08:33:30

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:41

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

constant · 发表于 2006-3-12 04:22:02

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

QL · 发表于 2006-3-12 06:27:04

若是第一个问题，应该是放过前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:01

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

		自动登录	找回密码
密码			立即注册

动态微博

电梯问题

回复：电梯问题

回复：回复：电梯问题

验证下思路

回复：电梯问题

回复：电梯问题

谁能告诉我这个问题的英文网站？我 google 半天，没找到。

回复：电梯问题

回复：回复：电梯问题

回复：回复：回复：电梯问题