两颗弹珠和一座 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

该问题在《书》中的问题 6.5 中有介绍。破解编码面试（第五）”，解决方案总结如下：

观察：

无论我们如何删除 Marble1，Marble2 都必须进行线性搜索。例如，如果大理石1在第10层至15层之间断裂，我们必须用大理石进行检查之间的每个楼层2

---

该方法：

第一次尝试： 假设我们从 10 楼掉落一颗弹珠，然后是 20 楼……

• 在第一个弹珠在第一次掉落时破裂（第 10 层）时，我们总共最多掉落 10 次。
• 如果第一个大理石在最后一个滴（100楼）上断裂，那么我们最多有19滴（地板1至100，然后是91至99）。
• 这很好，但我们考虑的只是绝对最坏的情况。我们应该做一些“负载平衡”，以使这两种情况更加甚至更高。

目标： 创建一个用于掉落 Marble1 的系统，以便无论 Marble1 在第一次掉落还是最后一次掉落时破裂，所需的最多掉落次数都是一致的。

1. 一个完美的负载平衡系统将是一个大理石1 +滴的大理石滴始终是相同的，无论大理石1中断。
2. 为此，由于每滴大理石1都采取了一步，因此允许Marble2少了一步。
3. 因此，我们必须每次将Marble2可能要求的步骤数量减少一次。例如，如果将大理石1放在20楼，然后将30楼掉落，则可能需要9步。当我们再次放下 Marble1 时，我们必须将 Marble2 的潜在步数减少到只有 8 个。例如，我们必须在 39 层掉落 Marble1。
4. 因此，我们知道，大理石1必须从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章：鸡蛋和地板的谜题 .

Answer 3

它们从同一高度掉落时都会破裂，还是不同？

如果它们相同，我就去 50 层并放下第一颗弹珠。如果它没有坏掉，我就去75层，做同样的事情，只要它不坏掉，我就继续上升剩下的50%。当它破裂时，我会回到比之前更高的地方（所以如果它在 75 楼破裂，我会回到 51 楼），然后放下第二个弹珠，一次向上移动一层，直到它破裂为止，那时我知道我可以从最高的楼层跌落而不会损坏大理石。

可能不是最好的答案，我很好奇其他人如何回答。

Answer 4

在第 10、20、30 层等处掉落第一颗弹珠。直到它破裂然后跳回最后一个已知的 好的 地板并开始从那里一次一层地扔弹珠。最坏的情况是 99 是魔法地板，你总是可以在 19 滴或更少的时间内找到它。

Answer 5

我个人不太喜欢此类难题，我更喜欢面试中的实际编程练习。

也就是说，首先取决于我是否可以从我将它们扔到的地板上判断它们是否损坏。我假设我可以。

我会爬到二楼，放下第一颗弹珠。如果坏了我会尝试一楼。如果它坏了我就会知道那不是地板。

如果第一个没有破裂，我会去四楼并从那里掉下来。如果它坏了，我会回去拿另一块大理石，然后掉到三楼，无论坏与否，我都会知道哪个是极限。

如果两者都没有损坏，我会去拿两个，并执行相同的过程，这次从 6 楼开始。

这样，我就可以跳过每一层楼，直到找到一个破碎的弹珠。

如果大理石提前破裂，这将得到优化......我想我可能有一个最佳的楼层数可以跳过，以便每次跳过都能获得最大的收益......但如果有一个坏了，我就必须从最后一个已知楼层上方的第一层开始单独检查每一层......如果我跳过太多楼层，这当然会很痛苦（抱歉，现在不打算找出最佳解决方案）。

理想情况下，我想要一整袋弹珠，然后我可以使用二分搜索算法，并将每次掉落的楼层数分成两半......但那不是问题，不是吗？

Answer 6

我觉得 真实的 问题是你想要答案有多准确。因为你的效率实际上取决于此。

如果您想在大理石上100％准确性，我将同意贾斯汀的观点，那么一旦第一个大理石打破了您必须一次从最后一个已知的“好”地板上升到1层，直到您发现哪个地板是哪个地板获胜者，冠军。”甚至可以投入一些统计数据，然后从25楼而不是50楼开始，以便最坏的情况是24而不是49。

如果你的答案可以加减一两层，那么可能会有一些优化。

其次，上下楼梯是否会影响你的效率？在这种情况下，每次上/下行程时，务必放下两个弹珠并捡起两个弹珠。

Answer 7

从三楼掉落第一块弹珠。如果它碎了，你就知道它是 1 楼或 2 楼，所以从 2 楼扔下另一个弹珠。如果没有损坏，您会发现 2 楼是最高的。如果它确实损坏了，您会发现 1 楼是最高的。2 滴。

如果从 3 楼跌落没有破坏大理石，则从 6 楼跌落。如果它坏了，你就知道 4 或 5 楼是最高的。从 5 楼掉落第二颗弹珠。如果它没有崩溃，你就会发现 5 是最高的。如果是，则 4 楼是最高的。4 滴。

继续。

3 层 - 最多 2 次掉落

6 层 - 最多 4 次掉落

9 层 - 最多 6 次掉落

12 层 - 最多 8 次掉落

ETC。

3x 层 - 最多 2x 掉落

因此，对于 99 层的建筑，最多有 66 个跌落点。这是最大值。你的掉落量可能会比这个少。哦，66 也是 100 层建筑的最大值。如果休息楼层是 98 或 97 层，则只需要 66 次掉落。如果断裂地板为 100，则需要使用 34 滴。

即使你说没关系，但这可能需要最少的步行量，而且你不必知道建筑物有多高。

部分问题在于如何定义效率。总是在少于 x 滴的时间内找到解决方案是否更“有效”，或者是否有很好的机会在 y 滴中找到解决方案，其中 y < x，但需要注意的是，您可能有超过 x 滴的解决方案？ ？

Answer 8

只需 7 个弹珠就可以做得更好。

因此，根据投票结果，假设大理石至少在 49 层破裂。

1. 50 楼 -> 休息（答案在 1 到 50 之间（含））
2. 25楼 -> 不会破坏（26到50）
3. 37 楼 -> 不会破裂（38 至 50）
4. 43 楼 -> 不会损坏（44 到 50）
5. 46 楼 -> 不会损坏（47 到 50）
6. 48 楼 -> 不会损坏（49 或 50）
7. 49层 -> 破裂（49层，这一步实际上是需要的，因为它可能是大理石破裂的最低楼层是在50层）

这可以想象为在排序集中对某个 k 进行二分搜索，每次尝试都会将解决方案空间减半。对于 100 层楼，我们需要 log2 100 = 6.644（7 次尝试）。有了 7 个弹珠，我们就可以确定弹珠能拆成 128 层楼的最低楼层是多少。

Answer 9

我要做的第一件事是使用极其简单的算法，从第 1 层开始，一次将弹珠掉落一层，直到达到 100 或弹珠破裂。

然后我会问为什么我应该花时间优化它，直到有人可以证明这将是一个问题。很多时候，当一个更简单的算法可以解决问题时，人们却全神贯注于寻找完美的复杂算法。换句话说，在需要之前不要进行优化。

这可能是一个棘手的问题，看看你是否是那些能小题大作的人之一。