把猫扔出窗外

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) ：对于 1 中的每个 k ..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 码/秒]。
人类终端速度为 210 km/h (130mph)。[=75m/s = 68.58 码/s]

终端速度来源：
http://en.wikipedia.org/wiki/Cat_righting_reflex

学分：
谷歌

我需要稍后验证：
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 (a-1)r (a-1)r (a-1)r (a-1)r (a-1)r (a-1)r (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 层）来推导递归，假设我们知道较小参数的最优解。如果鸡蛋破裂，我们可以用 k-1 鸡蛋探索下面的 g-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

所有这些关于猫的疯狂谈论……这只是一个最小猜测（猫的数量）的数字问题。也不应该需要人为地（并且错误地）定义无穷大作为解决方案的一部分。该变量应该被命名为 upper-bound 或 max-try 等。
不过，问题定义（猫的事情）存在一些严重的问题，人们对虐待动物的可能性以及现实生活中提出的此类问题的许多方面做出反应，例如空气阻力、重力是加速度以及其他此类现实生活参数的问题。所以也许应该以完全不同的方式提出这个问题。