100层楼2个鸡蛋，测试其最低破碎楼层问题

原文章链接

http://www.cnblogs.com/yangai/p/5391533.html

http://www.tuicool.com/articles/NzUNJr

http://blog.sina.com.cn/s/blog_6c813dbd0101bh98.html

有一栋楼共100层，一个鸡蛋从第N层及以上的楼层落下来会摔破， 在第N层以下的楼层落下不会摔破。给你2个鸡蛋，设计方案找出N，并且保证在最坏情况下， 最小化鸡蛋下落的次数。 

我们先假设最坏情况下，鸡蛋下落次数为x，即我们为了找出N，一共用鸡蛋做了x次的实验。 那么，我们第一次应该在哪层楼往下扔鸡蛋呢？先让我们假设第一次是在第y层楼扔的鸡蛋， 如果第一个鸡蛋在第一次扔就碎了，我们就只剩下一个鸡蛋，要用它准确地找出N， 只能从第一层向上，一层一层的往上测试，直到它摔坏为止，答案就出来了。 由于第一个鸡蛋在第y层就摔破了， 所以最坏的情况是第二个鸡蛋要把第1到第y-1层的楼都测试一遍，最后得出结果， 噢，原来鸡蛋在第y-1层才能摔破(或是在第y-1层仍没摔破，答案就是第y层。) 这样一来测试次数是1+(y-1)=x，即第一次测试要在第x层。OK， 那如果第一次测试鸡蛋没摔破呢，那N肯定要比x大，要继续往上找，需要在哪一层扔呢？ 我们可以模仿前面的操作，如果第一个鸡蛋在第二次测试中摔破了， 那么第二个鸡蛋的测试次数就只剩下x-2次了(第一个鸡蛋已经用了2次)。 这样一来，第二次扔鸡蛋的楼层和第一次扔鸡蛋的楼层之间就隔着x-2层。 我们再回过头来看一看，第一次扔鸡蛋的楼层在第x层，第1层到第x层间共x层； 第1次扔鸡蛋的楼层到第2次扔鸡蛋的楼层间共有x-1层(包含第2次扔鸡蛋的那一层)， 同理继续往下，我们可以得出，第2次扔鸡蛋的楼层到第3次扔鸡蛋的楼层间共有x-2层， ……最后把这些互不包含的区间数加起来，应该大于等于总共的楼层数量100，即

得出答案是14。

即我先用第1个鸡蛋在以下序列表示的楼层数不断地向上测试，直到它摔破。 再用第2个鸡蛋从上一个没摔破的序列数的下一层开始，向上测试， 即可保证在最坏情况下也只需要测试14次，就能用2个鸡蛋找出从哪一层开始， 往下扔鸡蛋，鸡蛋就会摔破。

比如，我第1个鸡蛋是在第77层摔破的，那么我第2个鸡蛋就从第70层开始，向上测试， 第二个鸡蛋最多只需要测试7次(70,71,72,73,74,75,76)，加上第1个鸡蛋测试的 7次(14,27,39,50,60,69,77)，最坏情况只需要测试14次即可得出答案。

这个问题还有一个泛化的版本，即d层楼，e个鸡蛋，然后设计方案找出N， 使最坏情况下测试的次数最少。这个要用动态规划(DP)来解。 

f[d][e]表示d 层楼，e个鸡蛋时，最坏情况下的测试次数，则：

f[d][e]=min{max(f[d-i][e]+1，f[i-1][e-1]+1)}，i=1,2,...,d;

f[k][1]=k，0