把猫扔出窗外

想象一下你和一只猫在一栋高楼里。这只猫可以从低楼层的窗户上摔下来，但是如果从高楼层摔下来，它就会死掉。你怎样才能用最少的尝试次数来计算出猫能够存活的最长下落时间呢？

显然，如果你只有一只猫，那么你只能线性搜索。先把猫从一楼扔下去。如果它还活着，就从第二节开始扔。最终，猫被从地板上扔下来后，就会死去。然后你就知道 f-1楼层是最安全的楼层。

但如果你养了不止一只猫呢？现在可以尝试某种对数搜索。假设这栋楼有100层，你有两只一模一样的猫。如果你把第一只猫从50层扔出去，它死了，那么你只需要直线搜索50层。如果你选择一个较低的楼层作为你的第一次尝试，你可以做得更好。假设你选择一次解决20层楼的问题，而第一层致命楼层是50英镑。在这种情况下，你的第一只猫会在从20层到40层的飞行中存活下来，然后在60层死去。你只需要逐层检查41到49层。这总共是12次尝试，这比您尝试使用二进制消除所需的50次要好得多。

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

假设所有的猫都是等价的: 它们都会从一个给定的窗口掉下来而死亡或者幸存。此外，每一次尝试都是独立的: 如果一只猫从高处坠落幸存下来，它完全没有受到伤害。

这不是家庭作业，虽然我可能已经解决了一次学校作业。这只是今天突然冒出来的一个古怪的问题，我不记得解决方法了。如果有人知道这个问题的名字或者解决算法，就会得到额外的分数。

15449 次浏览
小开

根据 最近的一集 Radiolab (关于“堕落”)台的报道，一只猫到了9楼的终端速度。在那之后，它就会放松，受伤的可能性也会降低。有完全没有受伤的猫从30楼以上摔下来。最危险的楼层是5楼到9楼。

小开
最佳答案

您可以很容易地为 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)的谷歌结果一致。

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)计算，但我已经有点困了。

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

小开

所有这些关于猫的疯狂言论。.这只是一个最小猜测的数字问题(猫的数量)。也没有必要人为地(不正确地)将无穷大定义为解的一部分。变量应该被命名为上限或者 max-try 或者类似的名字。 问题的定义(猫的事情)有一些严重的问题，虽然人们回应动物虐待的潜在可能性，以及这样一个问题在现实生活中提出的许多方面，例如空气阻力，重力是加速度，以及其他这样的现实生活参数的问题。所以也许应该用完全不同的方式来问。

小开

想象一下你和一只猫在一栋高楼里。这只猫可以从低楼层的窗户上摔下来，但是如果从高楼层摔下来，它就会死掉。你怎样才能用最少的尝试次数来计算出猫能够存活的最长下落时间呢？

解决这个问题的最佳策略是利用物理定律，首先调查你的假设成立的可能性。

如果你这样做了，你就会意识到，猫的生存机会实际上增加了更高的距离地面。当然，前提是你把它从更高的建筑上扔下来，比如双子塔，而不是从更高的山上扔下来，比如珠穆朗玛峰。

编辑:
事实上，你会看到一个未完成的骆驼分配。
首先，猫死亡的概率是低(非常低的高度) ，然后它得到更高(低的高度) ，然后再低(高的高度) ，然后再高(非常高的高度)。

猫的死亡概率随地面高度的变化如下图所示:
(完成3，因为未完成骆驼分配)

alt text

更新:
一只猫的终端速度是100公里/小时(60英里/小时)[ = 27.7米/秒 = 25.4码/秒]。
人类的终端速度是210公里/小时(130英里/小时)

终端速度来源:
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


小开

这不是假设你在用“同一只猫”吗？

你可以用数学的方法来处理它，但这是数学的好处... ... 如果假设正确，0可以等于1(对于大的值为0)。

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

你可以试着通过经验来确定答案，但是我认为会有足够多的统计差异，使得答案在统计上毫无意义。

你可以尝试使用“同一只猫”，但这不会工作，因为，在第一滴之后，它不再是同一只猫。(同样，一个人永远不能两次踏入同一条河流)

或者，你可以聚合猫的健康状况，以非常密切的间隔进行取样，找到猫“大部分还活着”的高度(与《公主新娘》中的“大部分死亡”相反)。平均来说，这些猫会生存下来(直到最后一次休息)。

我认为我已经偏离了最初的意图，但如果你走的是实证路线，我赞成从尽可能高的地方开始，随着高度的降低继续下降，直到它们在统计上存活下来。然后再对幸存的猫进行测试以确定。

小开

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

我开始工作的最大楼层，可以覆盖使用 X猫和 嘿猜测使用以下方法。

从1层开始，不断增加猜测的次数，同时记录检查的楼层，猜测他们被检查，以及每层还剩下多少只猫。
将这个步骤重复到 嘿次。

这个 非常低效的代码计算给定的答案，但仍然有用的小数量的猫/楼层。

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遵循 密码分段模式。

两只猫:
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的正确解。
对于希望检查不那么琐碎的内容的任何人，它给出(1000000,5) = 43。

这在 O (n)中运行，其中 n 是问题的答案(猫越多越好)。
然而，我相信一个数学水平更高的人可以简化分段公式来计算 O (1)。

小开 
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).
小开

我第一次读到这个问题是在 Steven Skiena 的 算法设计手册(练习8.15)中。接下来的一章是关于动态编程的，但是是 你不需要知道动态编程来证明策略的精确界限。首先是问题陈述，然后是下面的解决方案。

鸡蛋从足够高的地方掉下来时会破裂。给定一个 n 层的建筑，必须有一个这样的楼层，即鸡蛋从楼层 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)的动态程序的运行时间是多少？

只有一个鸡蛋

从第一层开始将鸡蛋从每一层放下，会发现在(最坏的情况下) n 个操作中的关键层。

没有更快的算法了。在任何算法中的任何时候，让 g 从已经看到的最高楼层不要打破。该算法在任何较高的层 h > g + 1之前必须检验层 g + 1，否则，如果鸡蛋从层 h 破碎，则不能区分 f = g + 1和 f = h。

两个鸡蛋

首先，让我们考虑 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 个蛋。以恒定的间隔放置每个鸡蛋，这应该被看作是 n 的 kth 根的幂。例如，对于 n = 1000和 k = 3，搜索第一个鸡蛋的100层楼，第二个鸡蛋的10层楼，最后一个鸡蛋的1层楼。

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

完全正确

我们假设我们知道较小参数的最优解，通过优化第一个鸡蛋落在哪里(地板 g)来推导递归。如果蛋破了，我们就让 G-1楼下的人去探索 K-1蛋。如果卵子存活下来，我们在上面的 n-g 层用 K 卵子探索。魔鬼为我们选择了最坏的。因此对于 k > 1，递归

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

提交答案