algorithm - 把猫扔出窗外

Question

想象一下，你和一只猫在一座高楼里。猫可以从低层窗户掉下来幸存下来，但如果从高地板上摔下来就会死。你怎么能用最少的尝试次数计算出猫可以存活的最长跌落？

显然，如果你只有一只猫，那么你只能线性搜索。先把猫从一楼扔出去。如果它幸存下来，从第二个扔掉它。最终，从 f 楼被扔下后，猫会死去。然后您就知道 f-1 层是最大安全层。

但是如果你有不止一只猫怎么办？您现在可以尝试某种对数搜索。假设该建筑有 100 层，而您有两只相同的猫。如果你把第一只猫扔出 50 层而它死了，那么你只需要线性搜索 50 层。如果您第一次尝试选择较低的楼层，您可以做得更好。假设您选择一次解决 20 个楼层的问题，而第一个致命楼层是 #50。在这种情况下，您的第一只猫将在 20 层和 40 层的飞行中幸存下来，然后从 60 层死亡。您只需分别检查 41 到 49 层。总共尝试了 12 次，这比尝试使用二元消除时需要的 50 次要好得多。

一般来说，对于有 2 只猫的 n 层建筑，最好的策略和最坏情况的复杂性是什么？n 层楼和 m 只猫呢？

假设所有的猫都是等价的：它们都会因从给定的窗户掉下来而存活或死亡。此外，每一次尝试都是独立的：如果一只猫从跌倒中幸存下来，它就完全没有受伤。

这不是家庭作业，尽管我可能曾经为学校作业解决过它。这只是今天突然出现在我脑海中的一个异想天开的问题，我不记得解决方案了。如果有人知道这个问题的名称或解决方案算法的名称，则可以加分。

Answer 1

根据Radiolab 最近的一集（关于“坠落”），一只猫在 9 楼达到了极限速度。之后，它会放松并且不太可能受伤。从 30 日以上跌落后，有完全没有受伤的猫。最危险的楼层是 5 到 9 楼。

Answer 2

您可以轻松地为 n 层和 m 猫的一般情况编写一点 DP（动态编程）。

主要公式a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n应该是不言自明的：

• 如果第一只猫从第 k 层被扔出去并死了，我们现在有k - 1楼层要检查（全部在下面k）和m - 1猫（a[k - 1][m - 1]）。
• 如果猫幸存下来，n - k剩下的楼层（上面的所有楼层k）仍然是m猫。
• 应该选择两个最坏的情况，因此max.
• + 1来自于我们只使用了一次尝试的事实（不管猫是否幸存下来）。
• 我们尝试所有可能的楼层以找到最佳结果，因此min(f(k)) : for k in 1..n.

它与来自Gaurav Saxena的 (100, 2) 链接的Google 结果一致。

int n = 100; // number of floors
int m = 20; // number of cats
int INFINITY = 1000000;

int[][] a = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
    // no cats - no game
    a[i][0] = INFINITY;
}

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        // i floors, j cats
        a[i][j] = INFINITY;

        for (int k = 1; k <= i; ++k) {
            // try throw first cat from k-th floor
            int result = Math.max(a[k - 1][j - 1], a[i - k][j]) + 1;
            a[i][j] = Math.min(a[i][j], result);
        }
    }
}

System.out.println(a[n][m]);

k如果您最好保存在另一个数组中 ，您可以轻松找到策略（如何扔第一只猫） 。

还有一个更快的解决方案，不涉及 O(n^3) 计算，但我已经有点困了。

编辑
哦，是的，我记得我以前在哪里看到过这个问题。

Answer 3

想象一下，你和一只猫在一座高楼里。猫可以从低层窗户掉下来幸存下来，但如果从高地板上摔下来就会死。你怎么能用最少的尝试次数计算出猫可以存活的最长跌落？

解决这个问题的最佳策略是使用物理定律首先调查你的假设为真的概率。

如果你这样做了，你就会意识到猫的生存机会实际上会随着离地距离的增加而增加。当然，假设您是从更高的建筑物（例如双子塔）而不是更高的山峰（例如珠穆朗玛峰）上扔掉它。

编辑：
实际上，你会看到一个未完成的骆驼分布。
首先，猫死亡的概率很低（非常低海拔），然后它变得更高（低海拔），然后再次降低（更高海拔），然后再次更高（非常高海拔）。

猫死亡概率与地面高度的函数关系图如下所示：（
在 3 处完成，因为未完成的骆驼分布）

更新：
猫的最终速度为 100 公里/小时（60 英里/小时）[=27.7m/s = 25.4 码/s]。
人类终端速度为 210 公里/小时（130 英里/小时）。[=75m/s = 68.58 码/s]

终端速度来源：
http

://en.wikipedia.org/wiki/Cat_righting_reflex 来源 ：
Goooooogle

我需要稍后验证：
http ://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov /WWW/K-12/airplane/termv.html

Answer 4

我首先在 Steven Skiena 的算法设计手册（练习 8.15）中阅读了这个问题。紧随其后的是关于动态规划的一章，但您无需了解动态规划即可证明策略的精确界限。首先是问题陈述，然后是下面的解决方案。

鸡蛋从足够高的高度掉落时会破裂。给定一个 n 层的建筑物，必须有一个楼层 f 使得从楼层 f 掉下来的鸡蛋会破裂，但是从楼层 f-1 掉下来的鸡蛋会存活下来。（如果鸡蛋从任何楼层破裂，我们会说 f = 1。如果鸡蛋从任何楼层幸存下来，我们会说 f = n+1）。

你试图找到临界楼层 f。您可以执行的唯一操作是将鸡蛋从某个地板上掉下来，看看会发生什么。你从 k 个鸡蛋开始，并尽可能少地丢鸡蛋。破碎的鸡蛋不能重复使用（完整的鸡蛋可以）。令 E(k,n) 是始终足够的最小蛋粪数。

1. 证明 E(1,n) = n。
2. 表明E(k,n) = Θ(n**(1/k)).
3. 找到 E(k,n) 的递归。动态程序找到 E(k,n) 的运行时间是多少？

---

只有1个鸡蛋

从第一层开始从每层楼放下鸡蛋会在（最坏的）n 次操作中找到关键层。

没有更快的算法。在任何算法中的任何时候，让 g 看到鸡蛋不会从最高楼层破裂。该算法必须在任何更高的楼层 h > g+1 之前测试楼层 g+1，否则如果鸡蛋要从楼层 h 打破，它就无法区分 f=g+1 和 f=h。

2个蛋

首先，让我们考虑 k=2 个鸡蛋的情况，此时 n = r**2 是一个完美的正方形。这是一个需要 O(sqrt(n)) 时间的策略。首先以 r 层为增量丢下第一个鸡蛋。当第一个鸡蛋破裂时，比如说在地板上ar，我们知道关键地板 f 必须是(a-1)r < f <= ar。然后，我们从 开始从每层楼放下第二个鸡蛋(a-1)r。当第二个鸡蛋破裂时，我们已经找到了关键的地板。我们最多 r 次丢下每个鸡蛋，所以这个算法最坏情况下需要 2r 次操作，即 Θ(sqrt(n))。

当 n 不是完全平方时，取 r = ceil(sqrt(n)) ∈ Θ(sqrt(n))。该算法仍然是 Θ(sqrt(n))。

证明任何算法至少需要 sqrt(n) 时间。假设有一个更快的算法。考虑它掉落第一个鸡蛋的楼层顺序（只要它不破裂）。由于它下降的次数少于 sqrt(n)，因此必须有一个至少为 n/sqrt(n) 的间隔，即 sqrt(n)。当 f 在这个区间内时，算法将不得不用第二个鸡蛋来研究它，并且必须逐层地回顾 1 个鸡蛋的情况。矛盾。

k个鸡蛋

针对 2 个鸡蛋提出的算法可以很容易地扩展到 k 个鸡蛋。以恒定的间隔放下每个鸡蛋，这应该是 n 的第 k 次根的幂。例如，对于 n=1000 和 k=3，搜索第一个蛋的间隔为 100 层，第二个蛋为 10 个，最后一个蛋为 1 个。

类似地，我们可以通过从 k=2 证明中归纳来证明没有算法更快Θ(n**(1/k))。

确切的解决方案

我们通过优化放置第一个鸡蛋的位置（地板 g）来推断递归，假设我们知道较小参数的最佳解决方案。如果鸡蛋破裂，我们将在下面的 g-1 楼层用 k-1 个鸡蛋进行探索。如果鸡蛋幸存下来，我们在上面有 ng 层可以用 k 个鸡蛋进行探索。魔鬼为我们选择了最坏的。因此，对于 k>1，递归

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n

Answer 5

这不是假设您使用的是“同一只猫”吗？

你可以用数学方法来处理它，但这是数学的好处……在正确的假设下，0 可以等于 1（对于 0 的大值）。

从实际的角度来看，你可以得到“相似的猫”，但你不能得到“同一只猫”。

您可以尝试凭经验确定答案，但我认为会有足够的统计差异，以至于答案在统计上毫无意义。

您可以尝试使用“同一只猫”，但这不起作用，因为在第一滴之后，它不再是同一只猫。（同理，不能两次踏入同一条河流）

或者，您可以汇总猫的健康状况，以非常接近的间隔进行采样，并找到猫“大部分还活着”的高度（与“公主新娘”中的“大部分死亡”相反）。平均而言，猫会存活下来（直到最后一个间隔）。

我想我已经偏离了最初的意图，但如果你走的是经验主义路线，我投票赞成从尽可能高的起点开始，随着高度的降低继续丢弃猫，直到它们在统计上存活下来。然后重新测试幸存的猫以确定。

Answer 6

我采用了一种稍微不同的方法来产生解决方案。

我首先使用以下方法计算使用x猫和y猜测可以覆盖的最大楼层。

从 1 层开始，不断增加猜测的数量，同时跟踪检查的楼层、哪些猜测他们被检查了以及每个楼层还剩下多少只猫。
重复此操作最多y次。

这种计算给定答案的效率非常低的代码，但对于少量的猫/地板仍然有用。

Python代码：

def next_step(x, guess):
  next_x = []
  for y in x:
    if y[0] == guess:
      if y[1] != 1:
        next_x.append((guess+1, y[1] - 1))
    next_x.append(y)
    if y[0] == guess:
      next_x.append((guess+1, y[1]))
  return next_x

x = [(1, TOTAL_NUM_CATS)]
current_floor = 1
while len(x) <= TOTAL_NUM_FLOORS:
  x = next_step(x, current_floor)
  current_floor += 1
  print len(x)

对于 2 只猫，在 x 次猜测中可以识别的最大楼层为：1、3、6、10、15、21、28
...

对于 3 只猫：
1、3、7、14、25、41、63...

4 只猫：
1、3、7、15、30、56、98...

经过广泛的研究（主要涉及在OEIS中输入数字序列），我注意到x的最大楼层遵循组合分段模式。

对于 2 只猫：
n < 2 : 2^n - 1
n >= 2 : C(n, 1) + C(n, 2)

对于 3 只猫：
n < 3 : 2^n - 1
n >= 3 : C(n, 1) + C(n, 2) + C(n, 3)

对于 4 只猫：
n < 4 : 2^n - 1
n >= 4 : C(n, 1) + C(n, 2) + C(n, 3) + C(n, 4)

从这里开始，我采用了简单递增 n 的简单方法，直到通过所需的楼层数。

Python代码：

def find_smallest(floors, eggs):
  maximum_floors = 0
  n = 0
  while maximum_floors < floors:
    maximum_floors = 0
    n += 1
    if n < eggs:
      maximum_floors = 2**n - 1
    else:
      count = 0
      for x in xrange(1, eggs+1):
        maximum_floors += combination(n, x)
  print n

这给出了 (100, 2) = 14 的正确解。
对于任何希望检查不那么琐碎的东西的人，它给出 (1 000 000, 5) = 43。

这在 O(n) 中运行，其中 n 是问题的答案（猫越多越好）。
但是我确信具有更高数学水平的人可以简化分段公式以在 O(1) 中计算。

Answer 7

O(m*(n^(1/m))) algorithm.

Let 'x' be the maximum number of attempts needed.  

m = 1 => linear => x=n

m = 2:  
Let the floors be split into 'k' partitions. The first cat is thrown at the end of each partition (max 'k' times). 
When it dies, the second cat is used to go up from the beginning of this partition.   
x = k + n/k.   
Minimize x by diff wrt k and setting = 0, to get k = n^(1/2) and x = 2 * n^(1/2).

m = 3:  
x = k + 2*(y^(1/2)), where y = n/k  
diff wrt x and set = 0, to get k = n^(1/3) and x = 3 * n^(1/3)

for general m:  
x = m * n^(1/m). 

Answer 8

所有这些关于猫的疯狂讨论......这只是猜测最小猜测的数字问题（猫的数量）。也不应该需要人为（和错误地）将无穷大定义为解决方案的一部分。该变量应该被命名为上限或最大尝试或类似的名称。问题定义（猫的事情）虽然有一些严重的问题，人们对虐待动物的可能性以及现实生活中提出的此类问题的许多方面做出反应，例如空气阻力、重力是加速度以及其他此类现实生活中的参数的问题。所以也许应该以完全不同的方式提出问题。