39

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

给你两颗弹珠，并告诉它们从某个特定高度掉落时会破裂（如果从该高度以下掉落，可能不会受到损坏）。然后你被带到一栋 100 层的建筑物（大概高于特定高度），并被要求找到你可以在不破坏大理石的情况下掉落的最高楼层。

额外信息

  • 您必须找到正确的楼层（不是可能的范围）
  • 弹珠都保证在同一楼层破裂
  • 假设您更换地板的时间为零——仅计算大理石滴的数量
  • 假设正确的楼层随机分布在建筑物中
4

10 回答 10

54

这里有趣的事情是你如何以尽可能少的滴数做到这一点。如果突破层是第 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处打破它是否需要最大滴数

于 2008-08-09T02:45:43.070 回答
15

这个问题在《 Cracking the Coding Interview (5th) 》一书中的问题 6.5 中有介绍，解决方案总结如下：

观察：

无论我们如何删除 Marble1，Marble2 都必须进行线性搜索。例如，如果 Marble1 在 10 层和 15 层之间断裂，我们必须用 Marble2 检查中间的每一层

该方法：

第一次尝试：假设我们从 10 楼掉落大理石，然后从 20 楼……</p>

  • 在第一滴（10 楼）的第一个 Marble 破裂中，我们最多总共有 10 滴。
  • 如果第一个 Marble 在最后一滴（100 层）破裂，那么我们最多总共有 19 滴（1 到 100 层，然后是 91 到 99 层）。
  • 这很好，但我们所考虑的只是绝对最坏的情况。我们应该做一些“负载平衡”以使这两种情况更加均匀。

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

  1. 一个完美的负载平衡系统将是一个 Marble1 的 Drops of Marble2 + Drops of Marble2 始终相同的系统，无论 Marble1 在哪里损坏。
  2. 在这种情况下，由于 Marble1 的每一滴都会多走一步，因此 Marble2 可以少走一步。
  3. 因此，我们必须每次将 Marble2 可能需要的步骤数减少一​​滴。例如，如果 Marble1 掉落在 20 楼然后是 30 楼，则 Marble2 可能需要走 9 步。当我们再次放下 Marble1 时，我们必须将可能的 Marble2 步骤减少到只有 8 个。例如，我们必须在 39 楼放下 Marble1。
  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 步。

代码和扩展：

于 2014-01-15T09:32:13.247 回答
2

它们在从相同高度掉落时都会断裂，还是它们不同？

如果它们相同，我会去 50 楼丢下第一个弹珠。如果它没有破裂，我会去 75 楼做同样的事情，只要它没有破裂，我就会继续上升 50% 的剩余空间。当它真的破裂时，我会回到比之前高的地方（所以如果它在 75 楼破裂，我会回到 51 楼）并放下第二块大理石并一次向上移动一层直到它破裂，在这一点上，我知道我可以从没有大理石破损的最高楼层跌落。

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

于 2008-08-09T02:29:48.110 回答
2

我认为真正的问题是你想要答案有多准确。因为您的效率将真正取决于此。

如果你想要 100% 的弹珠准确率，我会同意贾斯汀的观点，那么一旦第一个弹珠破裂，你就必须从最后一个已知的“好”楼层一次上一层，直到你找出哪一层是赢家。” 甚至可以输入一些统计数据并从 25 楼而不是 50 楼开始，这样最坏的情况是 24 楼而不是 49 楼。

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

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

于 2008-08-09T02:40:56.653 回答
2

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

于 2008-08-09T14:46:21.137 回答
1

我个人不是很喜欢这样的谜题，我更喜欢面试中的实际编程练习。

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

我会上二楼，丢下第一块大理石。如果它坏了我会尝试一楼。如果它坏了，我会知道它没有地板。

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

如果两个都没有坏，我会去拿两个，做同样的过程，这次从 6 楼开始。

这样，我可以跳过每隔一层，直到我得到一个打破的大理石。

如果大理石早早破裂，这将进行优化......我想可能有一个最佳数量的楼层我可以跳过以获得最大的每次跳过......但是如果一个打破，我将不得不单独检查每一层从最后一个已知楼层上方的一楼......如果我跳过太多楼层当然会很痛苦（对不起，现在不打算找出最佳解决方案）。

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

于 2008-08-09T02:37:41.760 回答
1

如果您想要一个可以为您提供 N 层结果的通用解决方案（在您的情况下为 N=100），那么您只需求解二次方程$x^2+x-2\cdot(N-1)=0$和结果是正根的上限。

这是：

$$f(N)=天花板\bigg(\frac{-1+\sqrt{1+4\cdot2\cdot(N-1))}}{2}\bigg)$$

于 2019-03-27T10:48:17.580 回答
0

从 3 楼掉落第一块大理石。如果它坏了，你知道它是 1 楼或 2 楼，所以从 2 楼扔下另一个大理石。如果它没有坏，你发现 2 楼是最高的。如果它确实坏了，你会发现 1 楼是最高的。2滴。

如果从 3 楼掉下来没有破坏大理石，从 6 楼掉下来。如果它坏了，你知道 4 楼或 5 楼是最高的。从 5 楼丢下第二颗弹珠。如果它没有碎，你会发现 5 是最高的。如果是这样，4楼是最高的。4滴。

继续。

3 层 - 最多 2 滴

6 层 - 最多 4 滴

9 层 - 最多 6 滴

12 层 - 最多 8 滴

等等

3x 楼层 - 最多 2x 掉落

因此，对于一栋 99 层的建筑物，您最多可以有 66 滴。这是最大值。你的滴数可能会比这少。哦，66 也是 100 层建筑的最大值。如果休息地板是 98 或 97 楼，你只需要 66 滴。如果休息地板是 100，你会使用 34 滴。

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

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

于 2008-08-09T06:50:10.300 回答
-1

只需 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 层的最低楼层。

于 2014-07-20T14:34:34.373 回答
-3

我要做的第一件事是使用从 1 楼开始的死简单算法，一次将大理石掉落一层，直到达到 100 或大理石破裂。

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

这可能是一个棘手的问题，看看你是否是那些能从鼹鼠山上造出一座山的人之一。

于 2008-09-25T15:42:09.657 回答