There is a building of 100 floors. If an egg drops from the Nth floor or above, it will break. If it‘s dropped from any floor below, it will not break. You‘re given 2 eggs. Find N, while minimizing the number of drops for the worst case.
次数 阶数 如果破了最坏情况
1 x x-1
2 y y-x
3 z z-y+1
. . .
. . .
x-1 = y-x = z-y+1 ,每次的最坏情况应该是一样的。
次数 阶数 如果破了最坏情况
1 x x-1
2 2x-1 x-1
3 3x-3 x-1
. . .
. . .
n nx-n(n-1)/2 x-1
令 n = x-1,则此时nx-n(n-1)/2>=100,因为如果小于100,那么第n次没有破的情况下,已经丢了n次,还得从nx-n(n-1)/2+1次开始丢到100,看是哪一次破的,此时已经丢了n次,即x-1次了,那么最终的结果将大于x-1次
因此得到不等式 (x-1)x-(x-1)(x-2)/2>=100 得到 x>=13.5
又因为x要尽量小,因此x = 14
Cracking the Coding Interview 6.5,布布扣,bubuko.com
Cracking the Coding Interview 6.5
原文:http://www.cnblogs.com/johnsblog/p/3924069.html