※ 引述《bleed1979 (十三)》之铭言：
: ※ [本文转录自 Soft_Job 看板 #1JI2zrVk ]
: 作者: bleed1979 (十三) 看板: Soft_Job
: 标题: [讨论] Google面试问题
: 时间: Sat Apr 12 02:07:46 2014
: 问题：
: 假设你有两颗蛋，然后有一栋100层楼高的大楼。
: 而蛋的特性有的可能很坚固，坚固到从一百层楼跌下都没事，
: 有的可能很脆弱，一楼就可以摔破。
: 现在你只知道这这两颗蛋是完全相同的，
: 你想要知道蛋最高从哪一层楼摔下来不会摔破。
: 问题是：你要摔几次才能计算出来？
: （如果你低于高度摔下蛋，蛋就没事，如果高于那个楼层，蛋就完蛋）
: 在这过程你可以摔破蛋。
1)
先建立一个大家应该看得出来的前提
假设第一颗蛋摔破了，而且目前知道第L层不会破，第R层会破
那第二颗蛋就只能从L+1开始一直试到R-1，最坏情况要再试R-L-1次
2)
这题其实可以反过来想，假如你可以摔k次，可以判断出几层楼呢
以10次为例，假设最多只能摔10次
那我第一次不能在11楼以上摔，因为假设我在11楼摔破了
之后我就必须要从1试到10，最坏还要再试10次，加上第一次就超过10次
所以第一次最好是在10楼摔，假设摔破了再从1试到9最坏1+9=10次
而假设第一次没破，那我下一次不能在20楼以上摔
因为如果破了，就必需从11试到19最坏共9次，加上前两次又超过10次
所以第二次最好是在19楼摔，假设摔破了再从11试到18最坏共2+8=10次
依此类推，若没破的话第三次可以在19+8=27楼摔，第四次在27+7=34楼摔
第10次就会在55楼摔。
假如到这都还没破，楼高又超过55，就无法保证在10次内回答出来
因此我们可以归纳出，如果有k次可以用，楼高k(k+1)/2以内可以回答
对于100层楼，我们知道13次不够用，因为13*14/2 < 100
而14*15/2 >= 100，所以最少的次数是14次
对于n层楼，最少次数就是 k(k-1)/2 < n <= k(k+1)/2 的整数解
要求出closed form的话，可以化成 4k^2-4k+1 < 8n+1 <= 4k^2+4k+1
所以 (2k-1)^2 < 8n+1 <= (2k+1)^2
2k-1 < sqrt(8n+1) <= 2k+1
k-1 < (sqrt(8n+1)-1)/2 <= k
故 k = ceiling((sqrt(8n+1)-1)/2)