两个大理石和一个100层的建筑

Question

其中一个经典的编程面试问题......

给你两个大理石,并告诉他们从某个高度下降时会破裂(如果从那个高度以下掉落,可能不会受到伤害).然后你被带到一座100层高的建筑物(大概高于一定的高度),并要求找到最高的楼层,你可以尽可能高效地将大理石从大地上掉下来.

额外信息

• 你必须找到正确的楼层(不是可能的范围)
• 大理石都保证在同一层楼打破
• 假设您需要零时间更换地板 - 只计算大理石滴的数量
• 假设正确的楼层随机分布在建筑物中

Answer 1

这里有趣的是你如何以尽可能少的跌落来做到这一点.如果破土动工是第49层,那么去50楼并放弃第一层将是灾难性的,导致我们不得不做50滴.我们应该将第一块大理石放在地板n处,其中n是所需的最大滴量.如果大理石在地板n处破裂,我们可能必须在此之后进行n-1滴.如果大理石没有破裂,我们会上升到2n-1楼,如果它在这里破裂,我们必须在最坏的情况下将第二块大理石放下n-2次.我们继续这样直到100楼,试图在3n-2,4n-3 ......
和n +(n-1)+(n-2)+ ...... 1 <= 100 n = 14时打破它
是否需要最大滴数

Answer 2

" 破解编码面试(第5版) "一书中的问题6.5涵盖了这个问题,解决方案总结如下:

观察:

无论我们如何删除Marble1,Marble2都必须进行线性搜索.例如,如果Marble1在10楼和15楼之间断裂,我们必须检查Marble2之间的每个楼层

该方法:

第一次尝试:假设我们从10楼掉落大理石,然后是20号,......

• 在第一次大理石破碎(第10层),然后我们总共最多10滴.
• 如果第一个大理石在最后一滴(100楼)上断裂,那么我们总共最多有19滴(楼层1到100,然后是91到99).
• 这很不错,但我们所考虑的只是最糟糕的情况.我们应该做一些"负载平衡"来使这两个案例更加均衡.

目标: 创建一个用于删除Marble1的系统,以便所需的最多滴数是一致的,无论Marble1是在第一滴还是最后一滴上断开.

1. 一个完美的负载平衡系统将是一个大理石1滴+大理石滴2总是相同的,无论Marble1在哪里破碎.
2. 对于那种情况,由于每一滴Marble1需要多一步,因此Marble2允许少一步.
3. 因此,我们必须每次将Marble2可能需要的步骤减少一滴.例如,如果Marble1掉落在20楼,然后是30楼,则Marble2可能需要9步.当我们再次丢弃Marble1时,我们必须将Marble2的潜在步骤减少到8.例如,我们必须将Marble1放在39楼.
4. 因此,我们知道,Marble1必须从X楼开始,然后上升X-1楼,然后是X-2,......,直到它达到100.
5. 求解X +(X-1)+(X-2)+ ... + 1 = 100. X(X + 1)/ 2 = 100 - > X = 14

我们去14楼,然后是27,然后是39,......这最多需要14步.

代码和扩展:

• 对于代码实现,您可以在这里查看.

• 对于N大理石,M地板的扩展,请查看第12章:鸡蛋和地板的难题.