在一个已排序的列表中搜索饱和值的最佳方法

Question

在一个已排序的列表中搜索饱和值的最佳方法

algorithmmathsearch

7

来自Math Battle的一个问题。我在其中一次工作面试中也被问到了这个问题。

"一只猴子有两个椰子，在M层楼的阳台上扔椰子玩。猴子想知道椰子破裂的最低楼层。至少需要多少次尝试才能确定这个事实？ "

条件：如果一个椰子破了，你不能再使用它。你只剩下另一个椰子。

我能想到的可能方法/策略是：

二分法，找到椰子破裂的楼层后，从最后一个找到的二分法较低的索引开始向上计数。
窗口/较小楼层集合的片段，并在窗口/片段内使用二分法（但不利的是，这将需要一种自己的切片算法）

想知道是否还有其他方法可以做到这一点。

- AB Kolan

5个回答

8

二分查找不是答案，因为您只有一次机会去高估。二分查找需要 log m 次最大高估。

这是一个两阶段的方法。第一步是用相对较大的步长迭代楼层。在第一个椰子破裂后，第二阶段是从上一个安全楼层之后开始尝试每个楼层。

大步长大约为 sqrt(m)，但在早期更大，在后期更小，因为如果第一个椰子早期破裂，您可以在第二阶段中承受更多的迭代。

StepSize = (minimum s such that s * (s + 1) / 2 >= m)
CurrentFloor = 0

While no coconuts broken {
    CurrentFloor += StepSize
    StepSize -= 1

    Drop coconut from CurrentFloor
}

CurrentFloor -= StepSize + 1

While one remains coconut unbroken {
    CurrentFloor += 1
    Drop remaining coconut from CurrentFloor
}

// CurrentFloor is now set to the lowest floor that will break the coconut, 
// using no more total drops than the original value of StepSize

- recursive

2

我知道的最佳解决方案是2*sqrt(n)。从sqrt(n), 2*sqrt(n),...一直到n（或者到第一个椰子摔碎为止），在这些楼层中扔下第一个椰子。然后从上次已知的“安全”点开始，每次向上增加一层扔下第二个椰子，直到它破碎为止。这两个步骤最多需要sqrt(n)次扔。

注：您可以改进O(sqrt(n))内的常数，详见recursive的评论。我认为第一步应该在sqrt(2*n)左右，并随着每次扔掉递减1，以便最后一步（如果破碎高度实际上是n）恰好为1。细节由读者自行解决 :)

- Rafał Dowgird

2

由于这是一道面试题，考虑以下几点：

昂贵的操作是猴子上下楼梯，而不是扔椰子。从这个角度考虑，“线性”方法实际上是N²。
椰子落下时所受到的能量大致与落下高度成正比。如果在所有落下中都吸收了一定量的能量并打破了外壳......

- wowest

2

令我惊讶的是，有多少人直接关注他们认为包含在其中的编程问题，而不考虑包装器的有趣特性。 - Sarah Mei

1

这是一道很难的面试题，我花了好几天时间才解决。

我认为尝试的次数应该是楼层数的平方根的1.5倍。（例如100层和2个鸡蛋需要15次）

我们希望最小化每次尝试的大小和尝试的次数，同时使用它们来覆盖所有可能的楼层。在这种情况下，平方根是一个很好的起点，但我们会改变每次尝试的大小并围绕平方根进行平均。这样我们就可以兼顾两者：将每次尝试的大小均匀分布在平方根周围可以给我们带来最好的结果。对于100层和2个鸡蛋，这是15、14、13、12、11、10、9、8、7、6，总共10次。这相当于1.5倍的10。

- Krish

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brian R. Bondy · Accepted Answer

此类面试问题旨在考察您的思维方式。因此，我可能会提到一个O(N^0.5)的解决方案，但我也会给出以下讨论...

由于椰子随着时间的推移可能会出现内部裂纹，因此结果可能不如O(N^0.5)解决方案那样一致。尽管O(N^0.5)的解决方案很高效，但并不完全可靠。

我建议使用线性O(N)的解决方案来测试第一个椰子，然后用第二个椰子验证结果。其中N是建筑物楼层数。因此，对于第一个椰子，您可以尝试第1层，然后是第2层，然后是第3层，...

假设两个椰子的结构完全相同，并以完全相同的角度掉落，则可以将第二个椰子直接扔在第一个椰子破碎的地板上。将这个椰子的破碎地板称为B。

对于第二个椰子，您无需在1..B-1上进行测试，因为您已经知道第一个椰子没有在B-1、B-2、... 1层破碎。所以你只需要在B层上尝试它。

如果第二个椰子在B层破裂，那么您就知道B是问题所在的楼层。如果它没有破裂，那么您可以推断出椰子随着时间的推移而出现内部裂纹和劣化，测试本身就存在缺陷。您需要更多的椰子。

考虑到建筑物的规模相当有限，使用O(N)解决方案可以提高解决方案的额外信心。

正如 @Rafał Dowgird 所提到的，解决方案还取决于所讨论的猴子是非洲猴还是欧洲猴。众所周知，非洲猴投掷力度更大。因此，只能准确地将破碎的楼层B与偏差+/-2层联系起来。

为了确保猴子不会因为爬楼梯而累，最好将绳子系在第一个椰子上。这样，您就不需要为第一个椰子做1+2+..+B = B*(B+1)/2次楼梯运动。您只需要做恰好B次楼梯运动。

看起来楼梯的数量与这个问题无关，但如果猴子一开始就累了，我们可能永远无法得出解决方案。这为停机问题提供了新的考虑。

我们还假设建筑物位于地球上，重力加速度为9.8m/s^2。我们还假设不存在引力波。