好多公司经常面的一道智力题，加分的

Question

一幢 200 层的大楼，给你两个鸡蛋。如果在第 n 层扔下鸡蛋，鸡蛋不碎，那么从第 n-1 层扔鸡蛋，都不碎。这两只鸡蛋一模一样，不碎的话可以扔无数次。最高从哪层楼扔下时鸡蛋不会碎？

Answer 1

这道题应该是考察至少需要抛几次来判断鸡蛋最高从多少层掉下去不会碎吧。

要减少最大尝试次数，最常规的思路就是使每种投掷情况看上去更“平均”。
这里我们假设最少需要抛掷的次数为n，那么我第一次抛掷的楼层会选择第n层，因为一旦滴一个鸡蛋在第n层摔落时碎了，则第二个鸡蛋我们需要从第1层到第n-1层逐一尝试来寻找，这样最大的尝试次数是在第n-1层投掷时才知道鸡蛋在这一层会不会碎，也就是需要n次实验。

如果在第n层没碎，则我们需要再向上选择楼层抛第一个鸡蛋，由于之前已经抛过一次，那么这次我们只能选择n+n-1层来抛，这样才能保证如果在n+n-1层出现蛋碎的情况下，从n+1层实验到n+n-1层所尝试的次数加上前2次的总和为n。

此处省略。

如果之前的尝试都没有成功，而我们离n次的限制还剩余1次了，这一次就必须只能存在一个可选楼层上，这也应该是最高一层。

如此看来，可以得到一个公式，

$$ n + (n - 1) + (n - 2) + ... + 1 >= 200 $$

进行公式的简化

$$ n ^ 2 + n - 400 >= 0 $$

求这个公式的最小整数解为 20 。
所以，最少需要抛掷 20 次。

Answer 2

明确变量，稍微地整理一下问题和最高票答案。
在一幢200层的大楼上给你两个鸡蛋。
如果鸡蛋在a层时扔下不碎，那么他从1到a-1都不会碎。
求最少需要扔多少次才能确认a的最大值？

解：
假设需要扔n次可以确认a的最大值，两个鸡蛋分别为鸡蛋A和鸡蛋B。
下面开始推导：
1)、如果第一次从n层扔下A鸡蛋并且A碎了，那么剩下的B鸡蛋只能从1开始往n-1试，试n-1次
2)、如果A鸡蛋没碎，那么剩余可以尝试的次数是n-1次，所以第二次扔的楼层是n+n-1层，如果碎了，就从n+1层到n+n-1层之间进行尝试
3)、如果A鸡蛋依然没碎，第三次从n+n-1+n-2层开始扔...

直到n次扔完，但是n层扔完的楼层总数不低于200，由此可得：
n+(n-1)+(n-2)+···+3+2+1 >= 200

(1+n) n / 2 >= 200

n取最小整数解为20.

所以从第20层开始扔，能最快找到n的最大值。

Answer 3

2的n次方 我猜的

Answer 4

可以拿一个鸡蛋从第一层开始一层一层向高层试，O(n)的解法。也可以拿两个鸡蛋同时从1层3层试，3层扔下的鸡蛋没破就把1层的鸡蛋拿到5层，破了就把1层的鸡蛋拿到2层，循环下去，O(n/2)的解法。

Answer 5

有两个鸡蛋，鸡蛋不碎可以无限扔，可以从偶数层开始扔

Answer 6

一层层丢过去，哪层碎了就是哪层咯

Answer 7

相隔14层测试，
失败后第二个鸡蛋从之前的成功点向上测试
最多14+13次测试出来

Answer 8

我看了一个动态规划解决的方法，还不错
http://blog.csdn.net/joylnwan...
策略概括来说是：当我们想要解决一个2颗鸡蛋的问题，我们会想先把一个颗鸡蛋在n/2的位置扔出去。如果碎了，那我们只剩下一颗鸡蛋，只能从第一层开始一层一层向上扔。如果没碎，在3n/4的位置扔出去。类似于2分查找的样子。复杂度大概是O(n/2).
我们可以将这样的问题简记为W(n,k)，其中n代表可用于测试的鸡蛋数，k代表被测试的楼层数。对于问题W(2,36)我们可以如此考虑，将第1颗鸡蛋，在第i层扔下（i可以为1～k的任意值），如果碎了，则我们需要用第2颗鸡蛋，解决从第1层到第i-1层楼的子问题W(1,i-1)，如果这颗鸡蛋没碎，则我们需要用这两颗鸡蛋，解决从i+1层到第36层的子问题W(2,36-i)，解决这两个问题，可以分别得到一个尝试次数p，q，我们取这两个次数中的较大者(假设是p)，与第1次在i层执行测试的这1次相加，则p+1就是第一次将鸡蛋仍在i层来解决W(2，36)所需的最少测试次数次数ti。对于36层楼的问题，第一次，我们可以把鸡蛋仍在36层中的任何一层，所以可以得到36中解决方案的测试次数T{t1,t2,t3,……,t36}，在这些结果中，我们选取最小的ti，使得对于集合T中任意的值tj(1<=j<=36,j!=i)，都有ti<=tj，则ti就是这个问题的答案。用公式来描述就是
W(n, k) = 1 + min{max(W(n -1, x -1), W(n, k - x))}, x in {2, 3, ……，k}，其中x是第一次的测试的楼层位置。

Answer 9

假设第一个鸡蛋投出去的楼层分别为

如果第一个鸡蛋在ai楼层碎掉，那么下面第二个鸡蛋在保证必须检测出楼层的情况下必须扔出

所以在若第一个鸡蛋在ai层碎掉时，苏需要扔出的总次数为

最坏的情况（次数最多）可能出现在以下情况中

可以看出{a{i}} 为递减数列，取max时有a1=i.
max>=200，解出a1=20 .
所以扔的楼层分别为20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5
次数为20.

Answer 10

难道不是第200层吗...=_=

Answer 11

我只想说, 为什么不用二分法呢? 有人追评我再来解释.

到第8步, 后有同样有4种情况. 所以最多9步.判断出最高楼层.

Answer 12

感觉这个问题没描述清楚

Answer 13

吃到肚子里，然后跳楼。。。