小编典典

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

algorithm

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

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

额外信息

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

阅读 260

收藏
2020-07-28

共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 处打破它
是所需的最大滴数

2020-07-28