LeetCode 887 - Super Egg Drop
2 Egg Puzzle | PROGRAMMING INTERVIEWS
You are given 2 identical eggs such that eggs always break if dropped from floors above a particular floor of a 100-storey building. You need to find that particular floor in minimum number of egg droppings.
If we want optimal results, we should divide the building such that for every additional drop, remaining max drop decreases by 1. If our starting floor for first egg is 'k', there are 2 cases:
The egg breaks: In this case, total number of drops will be 1 + (k-1) i.e. k as we have to drop from each floor from 1 to (k-1).
The egg doesn't break: In this case, we are remaining with (100-k) floors and for optimal performance, max number of drops should be k. Also we verified that the egg doesn't break till k floors, so we need to check floors (k+1) to 100. If we choose ith floor for 2nd drop of first egg again and egg breaks here, then max droppings needed = 1 + (i-k) (1 for kth floor in first attempt and (i-k) for (k+1)st to ith floor)
k = 1 + (i-k)
i = 2k - 1
k + (k-1) + (k-2) ... + 1 = 100
How to solve for generalized case?
egg breaks: then we have (k-1) floors and 1 less egg.
egg doesn't break: then we have (100-k) floors and same number of eggs.
maxdrop(F, E) = for k from 1..F minimum of
1 + MAX(
maxdrop(F-k, E), //if egg doesn't break
maxdrop(k-1, E-1) // if egg breaks
)
http://netsmell.com/post/a-interesting-interview-question.html
100层楼扔两个鸡蛋问题
Related: Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing.
Read full article from 2 Egg Puzzle | PROGRAMMING INTERVIEWS
2 Egg Puzzle | PROGRAMMING INTERVIEWS
You are given 2 identical eggs such that eggs always break if dropped from floors above a particular floor of a 100-storey building. You need to find that particular floor in minimum number of egg droppings.
If we want optimal results, we should divide the building such that for every additional drop, remaining max drop decreases by 1. If our starting floor for first egg is 'k', there are 2 cases:
The egg breaks: In this case, total number of drops will be 1 + (k-1) i.e. k as we have to drop from each floor from 1 to (k-1).
The egg doesn't break: In this case, we are remaining with (100-k) floors and for optimal performance, max number of drops should be k. Also we verified that the egg doesn't break till k floors, so we need to check floors (k+1) to 100. If we choose ith floor for 2nd drop of first egg again and egg breaks here, then max droppings needed = 1 + (i-k) (1 for kth floor in first attempt and (i-k) for (k+1)st to ith floor)
k = 1 + (i-k)
i = 2k - 1
k + (k-1) + (k-2) ... + 1 = 100
How to solve for generalized case?
egg breaks: then we have (k-1) floors and 1 less egg.
egg doesn't break: then we have (100-k) floors and same number of eggs.
maxdrop(F, E) = for k from 1..F minimum of
1 + MAX(
maxdrop(F-k, E), //if egg doesn't break
maxdrop(k-1, E-1) // if egg breaks
)
http://netsmell.com/post/a-interesting-interview-question.html
x + (x-1) + (x-2) + ... + 1 >= 100 (x+1)*x/2 >= 100
得出答案是14。
即我先用第1个鸡蛋在以下序列表示的楼层数不断地向上测试，直到它摔破。 再用第2个鸡蛋从上一个没摔破的序列数的下一层开始，向上测试， 即可保证在最坏情况下也只需要测试14次，就能用2个鸡蛋找出从哪一层开始， 往下扔鸡蛋，鸡蛋就会摔破。
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100
比如，我第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的解法，感兴趣的话也可以看看以下链接： 在第12章有比较详细的介绍。
100层楼扔两个鸡蛋问题
有两个软硬程度相同的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，需要用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。在有两个鸡蛋的情况下最少需要几次测试，才能得到安全落下的最高楼层？
第一次测试所在的楼层高度为k. 如果第一次测试第一枚鸡蛋破碎，则向下还有k-1层楼和k-1次机会， 一层一层的试，k次一定能完成目标寻找目标。
如果第一次测试，第一枚鸡蛋没有破碎，则我们现在只有k-1次测试机会了，而且知道k楼及其以下都是安全的了。我们消耗了一次测试机会，但是一次就测试了k层楼。
然后只有k-1次机会了，第二次测试，我们可以在k层的基础上再增加k-1层了，注意，这个时候由于我们只有k-1次机会，所以这次只能再增加k-1层，以保证测试的时候第一枚鸡蛋破碎的情况下仍然能完成任务。
然后只有k-1次机会了，第二次测试，我们可以在k层的基础上再增加k-1层了，注意，这个时候由于我们只有k-1次机会，所以这次只能再增加k-1层，以保证测试的时候第一枚鸡蛋破碎的情况下仍然能完成任务。
重复上述过程，直到最后一次机会，我们总共测试的楼层数为：
根据题目要求楼层数为100,因此:
计算机方式-动态规划解答:
假设f[n]表示从n层楼找到摔鸡蛋不碎安全位置的最少判断次数。假设第一个鸡蛋第一次从第k层扔下，如果碎了，就剩一个鸡蛋，为确定下面楼层中的安全位置，必须从第一层挨着试，还需要k-1次；如果不碎的话，上面还有n-k层，剩下两个鸡蛋，还需要f[n-k]次（子问题，实体n层楼的上n-k层需要的最少判断次数和实体n-k层楼需要的最少判断次数其实是一样的）。因此，最坏情况下还需要判断max(k-1,f[n-k])次。
状态转移方程：f[k] = min{ 1+max(k-1,f[n-k]) | k=1..n }
初始条件: f[0]=0（或f[1]=1）
现在推广成n层楼，m个鸡蛋：
还是动态规划。假设f[n,m]表示n层楼、m个鸡蛋时找到摔鸡蛋不碎的最少判断次数。则一个鸡蛋从第k层扔下，如果碎了，还剩m-1个鸡蛋，为确定下面楼层中的安全位置，还需要f[k-1,m-1]次（子问题）；不碎的话，上面还有n-k层，还需要f[n-k,m]次（子问题，实体n层楼的上n-k层需要的最少判断次数和实体n-k层楼需要的最少判断次数其实是一样的）。
还是动态规划。假设f[n,m]表示n层楼、m个鸡蛋时找到摔鸡蛋不碎的最少判断次数。则一个鸡蛋从第k层扔下，如果碎了，还剩m-1个鸡蛋，为确定下面楼层中的安全位置，还需要f[k-1,m-1]次（子问题）；不碎的话，上面还有n-k层，还需要f[n-k,m]次（子问题，实体n层楼的上n-k层需要的最少判断次数和实体n-k层楼需要的最少判断次数其实是一样的）。
状态转移方程：f[n,m] = min{ 1+max(f[k-1,m-1], f[n-k,m]) | k＝1..n }
初始条件：f[k,0]=0（或f[k,1]=k），对所有k
问题扩展: 如果我们有三个鸡蛋, 如何在100层楼内找到最高安全楼层数?
思路同前面一样，第一次测试，不能太高也能太矮，必须恰到好处，也就是第一枚鸡蛋如果破碎，剩余k-1次机会能将剩余楼层给测试完。
由上面结论，k-1次机会最多可以测试k(k-1)/2层楼，所以第一次在[k(k-1)/2]+1层楼，第一次如果第一枚鸡蛋不碎，第二次在此基础上增加[(k-1)(k-2)/2]+1层楼，于是，三个鸡蛋k次机会总共测试楼层数为:
由上面结论，k-1次机会最多可以测试k(k-1)/2层楼，所以第一次在[k(k-1)/2]+1层楼，第一次如果第一枚鸡蛋不碎，第二次在此基础上增加[(k-1)(k-2)/2]+1层楼，于是，三个鸡蛋k次机会总共测试楼层数为:
Related: Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing.
Read full article from 2 Egg Puzzle | PROGRAMMING INTERVIEWS
