Two marbles and a 100 story building那些经典的编程面试问题之一... 您将获得两把弹珠，并告诉它们，当它们从某个高度跌落时，它们会破裂(如果从该高度以下跌落，可能不会受到任何损坏)。 然后，您被带到一幢100层高的建筑物(可能高于特定高度)，并被要求找到可以抛下大理石的最高楼层，而又不会使其尽可能地破裂。 额外信息
有趣的是如何以最少的滴水量做到这一点。如果破损的地板是第49层，则进入50层并掉下第一层将是灾难性的，导致我们不得不进行50滴。我们应该将第一个大理石放在n楼，其中n是所需的最大跌落量。如果大理石在第n层破裂，那之后我们可能不得不使n-1滴。如果大理石没有破裂，我们会升至2n-1楼；如果大理石在此处破裂，则在最坏的情况下我们必须掉落第二块大理石n-2次。我们继续这样直到100楼，并尝试在3n-2、4n-3 ....打破它。 《破解编码面谈(第5本书)》的问题6.5中涵盖了此问题，其解决方案总结如下： 观察：
无论我们如何删除Marble1，Marble2必须进行线性搜索。例如，如果大理石1 该方法： 第一次尝试：假设我们从10楼放下大理石，然后从20楼放…
目标：创建一个用于放置Marble1的系统，以使所需的最大放置次数保持一致，而不管Marble1是在第一个放置动作还是在最后一个放置动作中断。 不论Marble1中断在哪里，Marble2始终相同。 少一步。 每次下降。例如，如果将Marble1放在第20层，然后放在第30层，则Marble2为 可能需要采取9个步骤。当我们再次放下Marble1时，必须将潜在的Marble2步骤减少到仅8。例如，我们必须在39楼放下Marble1。 直到达到100。 我们先去14楼，然后到27楼，再到39楼，…最多需要14步。 代码和扩展名：
将第一个大理石放到10、20、30等楼，直到其破裂，然后跳回最后一个已知的好地板，并开始从那里一次将大理石放到一个地板上。最糟糕的情况是99作为魔术地板，您总是可以在19滴或更少的时间内找到它。 当它们从相同高度掉落时，它们各自会断裂，或者它们是否不同？ 如果它们相同，我去50楼，放下第一块大理石。如果还没有破裂，我会去第75楼并做同样的事情，只要它不破裂，我就会继续增加剩余的50％。当它确实破裂时，我回到比以前更高的位置(因此，如果它在第75层破裂了，我会回到第51层)，然后放下第二块大理石并一次向上移动一层直到它破裂为止，在那一点上，我知道我可以从最高的地板掉下来，而大理石没有破裂。 可能不是最好的答案，我很想知道其他人如何回答。 如果您想要一个可以得到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)$$ 我认为真正的问题是您想要答案的准确性如何。因为您的效率将真正取决于此。 如果您想在大理石上达到100％的精度，我会同意贾斯汀的观点，那么一旦第一个大理石破裂，您就必须一次从上一个已知的"好"层上爬一层，直到找出哪一层是获胜者，冠军。"甚至可能会抛出一些统计数据，并从25楼而不是50楼开始，因此最糟糕的情况是24而不是49。 如果您的回答可以是上下限，也可以是上下两个，那么可能会有一些优化。 其次，上下楼梯会影响您的效率吗？在这种情况下，每次上下都一定要扔掉两个弹子，然后捡起两个弹子。 我个人不太喜欢这类难题，我更喜欢面试中的实际编程练习。 就是说，首先要取决于我是否能确定它们是否从我摔落的地板上摔坏了。我想我可以。 我会去第二层，放下第一块大理石。如果破裂，我会尝试一楼。如果那破了，我会知道那不是地板。 如果第一层没有中断，我会去4层并从那里掉下来。如果那摔坏了，我会回去拿另一个大理石，然后掉到三楼，不管摔不坏，我都知道那是极限。 如果两者均未损坏，我将同时获得两者，并执行相同的过程，这次从6层开始。 这样一来，我可以跳过其他所有楼层，直到大理石破裂为止。 如果大理石早点破损，这将是优化的...我想可能有一个最佳数量的地板，我可以跳过以最大程度地跳过每一步...但是，如果一个破损，我将不得不单独检查每个地板从第一层到最后一个已知层的上方...如果我跳过太多层，那当然会很痛苦(很抱歉，现在不打算找出最佳解决方案)。 理想情况下，我需要一整袋大理石，然后可以使用二进制搜索算法，将每一滴落地的地板数分成一半...但是，那不是问题，不是吗？ 从3楼放下第一块大理石。如果破裂，您知道它是第1层或第2层，因此请从第2层掉下另一块大理石。如果没有破裂，您会发现第2层是最高的。如果确实破损，您会发现1楼最高。 2滴。 如果从3楼跌落并没有破坏大理石，请从6楼跌落。如果摔落，则知道4或5楼最高。从地板5放下第二块大理石。如果它没有破裂，您会发现5最高。如果是这样，则第4层是最高的。 4滴。 继续。 3层-最多2滴 6层-最多4滴 9层-最多6滴 12层-最多8滴 等等 3层楼-最多2层掉落 因此，对于99层的建筑物，您最多可以掉落66滴。那是最大的。您的落差可能会少于此。哦，对于100层建筑来说，最大值也是66。如果间隔层为98或97，则只需要66滴。如果间隔层为100，则需要34滴。 即使您说没关系，这也可能需要最少的步行时间，并且您不必知道建筑物的高度。
问题的一部分是如何定义效率。总是有少于x个液滴的解决方案更"有效"，还是有一个很好的机会在y
仅用7个大理石就可以做得更好。
因此，按照投票结果，说大理石至少在49楼断裂。
可以想象这是在k的排序集中进行二进制搜索，每次尝试我们将解空间减半。对于100层，我们需要log2 100 = 6.644(7次尝试)。使用7个大理石，我们可以确定大理石是最多可破裂至128层的最小地板。
我要做的第一件事是使用简单的死算法，该算法从第1层开始，一次将大理石降到一层，直到达到100或大理石破裂。
然后我问为什么我要花时间优化它，直到有人能证明这将是一个问题。当一个简单得多的算法可以解决问题时，太多的时间让人们全神贯注于寻找完美的复杂算法。换句话说，只有在需要时才进行优化。
看看您是否是可以从mole鼠山上爬山的人之一，这可能是一个棘手的问题。
|
