数学逻辑_丢鸡蛋_谷歌面试题

问题：
有一栋楼，共100层。
定义：鸡蛋在第n层楼扔下，不会碎，第n+1层扔下，会碎，那么第n层就叫临界楼层
你手中有两个鸡蛋（默认理想状态：两个鸡蛋完全相同），如何优化尝试策略，使得使用最少次数，测出临界楼层
即，使用此策略，最差也可以在多少次以内测出临界楼层

（ps:假定鸡蛋一定会在某层楼下落后碎掉）

解题思路：

注意：手中只有俩鸡蛋，必须要保证全碎之前测试出临界楼层

1. 为了不让鸡蛋碎掉，我们从一楼开始测试，这样只需要一个鸡蛋，当到达临界楼层的上一层n+1时，我们可以得出，n层是临界楼层，这是最原始的方法，遍历。

这种策略最糟糕的情况会是测试到100楼鸡蛋才会碎，测试次数是100次，临界楼层是99楼。最好的情况是测试到2楼鸡蛋就碎了，测试次数是2次，临界楼层是1层。

2. 我们手中有俩鸡蛋，为了充分利用条件，我们可以利用第一个鸡蛋来缩小范围。

我们可以先跑到50楼去扔，没碎的话，我们再去75楼去扔···直到第一个鸡蛋碎掉。

如果我们从50楼扔，没碎，说明50楼以下是安全的，50楼以上还有50楼，那我们再去上面的50楼的一半——75楼去扔，在75楼碎了，说明临界楼层在50层~74层之间，我们就利用第二个鸡蛋，遍历51层到74层。这是运用二分法。

这种策略最糟糕的情况会是50层鸡蛋就碎了，49层是临界楼层，测试次数是1+49次，临界楼层是99楼。最好的情况是1楼是临界楼层，测试次数是1+2次。

3. 还有没有更好的办法呢？我们手中有两个鸡蛋，尝试使每个鸡蛋的测试任务大致相当，即给100开个平方根，第一个鸡蛋只测试整十楼层，第二个鸡蛋测试两个整十楼层之间的楼层。我们可以先测10楼，20楼，30楼···，直到第一个鸡蛋碎掉。

如果我们测到30楼，第一个鸡蛋碎了，那我们就用第二个鸡蛋遍历测试21~29楼。

这种策略最糟糕的情况会是99层是临界楼层，测试次数是10+9次。最好的情况是1楼是临界楼层，测试次数是1+2次。

4. 这个时候我们产生了疑问，第三种方法是最好的策略吗？我们怎么验证呢？

验证这种事情，我们肯定要借助数学工具了

首先，我们我们假定存在一种最优策略，最多n次测试就能找到临界楼层

那么，最糟糕的状况会是哪一种呢？

从上面的分析可以看出，测试次数分为两部分

第一颗鸡蛋的测试次数x，用来缩小范围

第二颗鸡蛋用来在小范围内查找临界楼层y

即x+y=n

那么当测试次数固定为n时，每当x增加1，y则减少1

即，每当第一颗鸡蛋测试一次，那么所留给第二颗鸡蛋探查的范围就应该减少1

此处内容用于帮助各位理解：

如果n=10,那么第一次探查了20楼，使用了一次机会，如果碎了，确定的范围是1~19，那么，第二颗鸡蛋需要使用10-1次机会去探查19层，在最糟糕的情形下显然无法完成。

显然当n=10时，第一次探查为10楼显然更合适，确定下来的范围是1~9，第二颗鸡蛋使用10-1次探查9层楼，最糟糕的情形下也能满足。

如果探查10楼后鸡蛋没碎，而在第二次探查时碎了呢？我们第二次探查应该把范围再缩小1，如果第一个鸡蛋多探查一次，那么留给第二颗鸡蛋的探查机会就少一次，我们要保证在最糟糕的情形下也能探查到，所以留给第二颗鸡蛋的探查范围应该与其探查机会相等。即第一颗鸡蛋的第二次机会应该探查第19层，确定下来的范围需要探查的范围是11~18，第二颗鸡蛋的剩余探查次数刚好为10-2，匹配成功

·····

根据以上分析，我们可以发现，每一次的探查范围都减一，即n-1,n-2,n-3,....2,1,0

最后我们的探查范围会缩小到0

那么我们把这些探查范围加起来，再加上n就是我们的探查总范围

 即n+(n-1)+(n-2)+······+3+2+1+0=100

解的n刚好为正整数14，即使用此策略最多探查14次即可在100楼中找到临界楼层

另外，当探查总范围发生改变时，解的n可能为小数，显然，探查次数只能为整数且n越小探查总范围越小，

即n应向上取整 

另外一种理解方式：

对这个问题，原始问题：100层楼，最少需要几次测试，才能得到摔碎鸡蛋的楼层 ，直接考虑不容易考虑，但是，如果将这个问题进行一种等价的转换，这个问题将会变得非常容易解答。

个人认为，这个转换是解决这个问题的核心，这个转换是：

转换问题：两个鸡蛋，进行k次测试，最多可以测试几层楼

如果大家能想到将“原始问题”变为“转换问题”，这个问题个人认为已经解决一半了，转换后，这个问题豁然开朗，思路全开。

现在我们以“转换问题”为模板进行考虑，有两个鸡蛋，第一个鸡蛋如果破碎，第二个鸡蛋就必须只能一层一层的测试了，而且，我们要求进行k次测试就将摔碎鸡蛋的楼层必须找到.

考虑第一次测试。第一次测试的时候，第一个鸡蛋不能放置的楼层太高了，否则，如果第一个鸡蛋破碎，第二个鸡蛋可能不能在k次测试后得到结果。但是也不能放置的矮了，因为如果放置的矮了，第一个鸡蛋破碎了还好说，如果没破，我们浪费了一次测试机会，也不能说是完全浪费了，不过至少是让效用没有最大化。所以，第一次测试的时候必须让第一个鸡蛋放置的不高不矮。

不高不矮是多高？高到如果第一个鸡蛋破碎后第二个鸡蛋刚好能完成k次测试得到结果这个目标。由此可知，第一次测试所在的楼层高度为k，如果第一次测试第一枚鸡蛋破碎，则剩下k-1层楼，一层一层的试，k次一定能完成目标。

如果第一次测试，第一枚鸡蛋没有破碎，则我们现在只有k-1次测试机会了，而且直到了k楼及其以下都是安全的了。我们消耗了一次测试机会，但是一次就测试了k层楼。

然后只有k-1次机会了，第二次测试，我们可以在k层的基础上再增加k-1层了，注意，这个时候由于我们只有k-1次机会，所以这次只能再增加k-1层，以保证测试的时候第一枚鸡蛋破碎的情况下仍然能完成任务。

于是，重复上述过程，直到最后一次机会，我们总共测试的楼层数为：

这里的k相当于(k-1) + 1，对于一个鸡蛋，k-1次机会最多可以测试k-1层楼，再以此类推

然后，再回到“原始问题”，100层楼，如果需要k次测试才能测试完成，则必须有：

则可以得到，k≥14

要是求N层楼把这里的100换成N就行了，k仍然需要向上取整

然后，这个问题这个时候还可以扩展了，如果我们有三个鸡蛋，有k次机会，我们最大可以测试多少层楼？

思路同前面一样，第一次测试，不能太高也能太矮，必须恰到好处，也就是第一枚鸡蛋如果破碎，剩余k-1次机会能将剩余楼层给测试完。

由上面结论，k-1次机会最多可以测试k(k-1)/2层楼，所以第一次在k(k-1)/2+1层楼，第一次如果第一枚鸡蛋不碎，第二次在此基础上增加(k-1)(k-2)/2+1层楼，于是，三个鸡蛋k次机会总共测试楼层数为：

至于四个鸡蛋，五个鸡蛋，以至于M个鸡蛋，可以以此类推，方法同上。此处原理讲通，就不推导了

附：

动态规划解法

定义状态f[n][m]：N个鸡蛋从M层摔找出最少的尝试次数，测试出鸡蛋不会摔碎的临界点

状态转移方程：f[n][m] = 1+max( f[n-1][k-1]，f[n][m-k] ) （1