※ 引述《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) --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.243.123.89 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1398152375.A.C05.html ※ 编辑: johnathan717 (111.243.123.89), 04/22/2014 15:43:03