algorithm - 两块大理石和一座100层的建筑

那些经典的编程面试问题之一...

您将获得两把弹珠，并告诉它们从某个高度掉落时它们会破裂(如果从该高度以下掉落，可能不会受到任何损坏)。然后，您被带到一幢100层高的建筑物(可能高于特定高度)，并被要求找到可以抛下大理石的最高楼层，而又不会使其尽可能地破裂。

额外信息

您必须找到正确的楼层(不可能的范围)

大理石都保证在同一楼层破裂

假设您更换地板的时间为零-只有大理石滴的数量才算

假设正确的楼层随机分布在建筑物中

最佳答案

有趣的是，如何以最少的滴水量做到这一点。如果破损的地板是第49层，则进入50层并掉下第一层将是灾难性的，导致我们不得不进行50滴。我们应该将第一个大理石放在n楼，其中n是所需的最大跌落量。如果大理石在第n层破裂，则此后我们可能必须使n-1滴落。如果大理石没有破裂，我们会升至2n-1楼；如果大理石在此处破裂，则在最坏的情况下我们必须掉落第二块大理石n-2次。我们继续这样直到100楼，并尝试在3n-2、4n-3 ...打破它。
和n +(n-1)+(n-2)+ ... 1 n = 14是否需要最大滴数