把猫扔出窗外
想象一下，你正在一座带猫的高层build筑里。 猫可以从低矮的窗户里摔下来，但是如果从高处落下，它将会死亡。 如何用最less的尝试次数找出猫能够存活的最长时间？
显然，如果你只有一只猫，那么你只能线性search。 先从一楼扔掉猫。 如果它幸存下来，从第二个扔掉。 最后，从地板f扔掉后，猫会死亡。 然后你知道f-1楼是最大的安全楼层。
但是如果你有一只以上的猫呢？ 你现在可以尝试某种对数search。 假设这个build筑有100层，你有两个相同的猫。 如果你把第一只猫从第50层扔出去，那么你只需要线性search50层。 如果您首次尝试select较低的楼层，则可以做得更好。 假设您select一次处理20个楼层的问题，而第一个致命楼层是＃50。 在那种情况下，你的第一只猫在从第60层死亡之前将从第20层和第40层的飞行中幸存下来。你只需要单独检查第41层到第49层。 总共有12次尝试，比你试图使用二进制消除时需要的50次要好得多。
一般来说，最好的策略是什么，对于有两只猫的n层build筑来说，这是最糟糕的复杂性？ 那么n层和m猫呢？
假设所有的猫都是相同的：它们都会从某个窗口的落下中生存或死亡。 而且，每一次尝试都是独立的，如果一只猫幸免于难，完全没有受到伤害。
这不是家庭作业，虽然我可能一旦解决了它的学校作业。 这只是一个突发奇想的问题，我今天突然想起，我不记得解决scheme。 如果有人知道这个问题或解决schemealgorithm的名称，奖励点。
你可以很容易的写一点DP（dynamic规划），用于n层和m猫的一般情况。
a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n主公式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猫。 - 应select最差的两个，因此
max。 -
+ 1来自我们刚刚使用过一次（不pipe猫是否存活）的事实。 - 我们尝试每个可能的楼层来find最好的结果，因此
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]);
你可以很容易地find策略（如何扔第一只猫），如果你保存在另一个arrays中最好的k 。
还有一个更快的解决scheme，不涉及O（n ^ 3）计算，但我已经有点困了。
编辑
哦，是的， 我记得以前我看到过这个问题 。
根据Radiolab最近一集（关于“坠落”） ，一只猫在9楼达到终点速度。 之后，它放松，不太可能受到伤害。 30日以后有完全没有受伤的猫。 风险最高的楼层是第5到第9。
想象一下，你正在一座带猫的高层build筑里。 猫可以从低矮的窗户里摔下来，但是如果从高处落下，它将会死亡。 如何用最less的尝试次数找出猫能够存活的最长时间？
解决这个问题的最好的策略是使用物理定律来调查你的假设是否真的可能性。
如果你愿意的话，你会意识到猫的生存机会实际上增加了与地面的距离。 当然，假设你从一个更高的build筑物，如双子塔，而不是像珠穆朗玛峰那样的更高的山上扔掉它。
编辑：
其实，你会看到一个未完成的骆驼发行。
首先，猫死亡的可能性很低（非常低的海拔），然后它变得更高（低海拔），然后再降低（更高的海拔），然后再更高（非常高的海拔）。
作为地面高度的函数，猫死亡概率的图如下所示：
（在3点结束，因为未完成的骆驼分配）
更新：
猫的终点速度是100公里/小时（60英里/小时）[= 27.7米/秒= 25.4码/秒]。
人的terminal速度是210 km / h（130mph）。[= 75m / s = 68.58码/ s]
terminal速度来源：
http://en.wikipedia.org/wiki/Cat_righting_reflex
积分：
Goooooogle
我需要稍后validation：
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov/WWW/K-12/airplane/termv.html
我首先在Steven Skiena的algorithmdevise手册 （习题8.15）中读到这个问题。 它遵循了关于dynamic编程的一章，但是您不需要知道dynamic编程来certificate策略的精确界限 。 首先是问题陈述，然后是下面的解决scheme。
鸡蛋从足够高的高度落下时会断裂。 给定一个n层的build筑物，必须有一个f层的地板，以便鸡蛋从f层落下，但从f-1层落下的鸡蛋仍然存在。 （如果鸡蛋从任何一层打破，我们会说f = 1。如果鸡蛋从任何一层都存活下来，我们会说f = n + 1）。
你寻求find关键的楼层。 你可以执行的唯一操作是从某个楼层放下一个鸡蛋，看看会发生什么。 你从k个蛋开始，尽可能less地尝试去掉蛋。 破碎的蛋不能重复使用（完整的蛋可以）。 设E（k，n）是总是足够的鸡蛋的最小数量。
- certificateE（1，n）= n。
- certificate
E(k,n) = Θ(n**(1/k))。- findE（k，n）的recursion。 E（k，n）的dynamic程序运行时间是多less？
只有一个鸡蛋
从第一层开始往下掉鸡蛋会发现在（最坏的情况下）n操作的关键楼层。
没有更快的algorithm。 在任何时候，在任何algorithm中，让鸡蛋所在的最高层不要破坏。 该algorithm必须在任何更高层次之前testingg + 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开始在每个楼层放下第二个蛋。 当第二个鸡蛋破碎时，我们已经find了关键的地板。 我们在每次最多的时候丢弃每个蛋，所以这个algorithm采用最差的2r操作，即Θ（sqrt（n））。
当n不是一个完美的正方形时，取r = ceil(sqrt(n)) ∈ Θ(sqrt(n)) 。 该algorithm保持Θ（sqrt（n））。
certificate任何algorithm至less需要sqrt（n）时间。 假设有一个更快的algorithm。 考虑从第一个鸡蛋下落的地板的顺序（只要不破坏）。 由于它less于sqrt（n），所以必须有至lessn / sqrt（n）的间隔，即sqrt（n）。 当f在这个区间内时，algorithm将不得不用第二个蛋来研究它，并且必须逐层地回顾1-蛋的情况。 矛盾。
k蛋
提出的2个蛋的algorithm可以容易地扩展到k个蛋。 每个鸡蛋以不变的间隔下落，这应该被视为n的第k根。 例如，对于n = 1000和k = 3，search100个楼层的第一个蛋，10个第二个蛋和1个最后一个蛋的search间隔。
类似地，我们可以通过从k = 2certificate中导出来certificate没有algorithm更快Θ(n**(1/k)) 。
确切的解决scheme
我们通过优化将第一个鸡蛋放在哪里（g）来推断重现，假定我们知道较小参数的最优解。 如果鸡蛋破碎，我们有1层以下的g-1鸡蛋。 如果鸡蛋存活下来，我们有上面的地板用k个鸡蛋探索。 魔鬼为我们select最糟糕的。 因此对于k> 1的复发
E(k,n) = min(max(E(k,ng), E(k-1,g))) minimised over g in 1..n
这不假设你使用“同一只猫”？
你可以用math的方法来处理，但这是math的好处……在正确的假设下，0可以等于1（对于0的大数值）。
从实际的angular度来看，你可以得到“类似的猫”，但你不能得到“同一只猫”。
你可以尝试根据经验来确定答案，但我认为会有足够的统计差异，答案在统计上是毫无意义的。
你可以尝试使用“同一只猫”，但那不行，因为在第一滴之后，它不再是同一只猫。 （类似于一个人可能不会两次进入同一条河）
或者，您可以将猫的健康状况，非常接近的时间间隔进行采样，并find猫“大部分活着”的高度（与“公主新娘”中的“大部分死亡”相反）。 猫会平均存活（直到最后一个时间间隔）。
我认为我已经偏离了原来的意图，但是如果你走的是经验路线，我会select尽可能高的起点，并随着身高的下降继续放下猫，直到它们在统计上生存下来。 然后重新testing幸存的猫，以确保。
我采取了一个稍微不同的方法来产生一个解决scheme
我开始通过使用以下方法来计算可以使用x猫和y猜测覆盖的最大楼层。
从1楼开始，不断增加猜测次数，同时跟踪检查楼层，猜测他们被检查，每层楼剩下多less猫。
重复这个y次。
这个非常低效的代码来计算给定的答案，但仍然有用的less数猫/地板。
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中input数字序列），我注意到x的最大楼层采用分段模式。
对于2只猫：
n <2：2 ^ n – 1
n> = 2：C（n，1）+ C（n，2）
对于3只猫：
n <3：2 ^ n – 1
（n，1）+ C（n，2）+ C（n，3）
对于4只猫：
n <4：2 ^ n – 1
（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的正确解。
对于那些希望检查一些不那么琐碎的东西的人来说，它给出了（100 000，5）= 43。
这在O（n）中运行，其中n是问题的答案（越多的猫越好）。
不过，我相信一个更高层次的math家可以简化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).
我不能读这个谷歌blogspot（感谢作品blogwall），但我不认为一个直接的二进制样式search将是最好的。 原因在于二分查找是基于这样的概念，即您所查找的答案在列表中的任何索引索引处具有相等的机会。 但在这种情况下，这是不正确的。 在这种情况下，答案会比另一个更接近范围的一端。 我不知道如何将这些因素纳入search，但这是一个有趣的想法。
所有这些疯狂的谈论猫..这只是一个猜测最小的猜测（猫的数量）的数字问题。 应该不需要人为地（并且不正确地）将无穷大定义为解决scheme的一部分。 该variables应该被命名为上限或最大尝试或一些这样的。 问题的定义（猫的东西）虽然有一些严重的问题，人们对动物的残酷行为做出反应，而且在现实生活中遇到的这样一个问题，比如空气阻力，重力加速度，以及其他这样的现实生活参数的问题。 所以也许应该以完全不同的方式提出。
我的解决scheme与Nikita Rybak给出的解决scheme略有不同。 主要区别在于我的公式是在两个维度上进行search，而不仅仅是“楼层”维度。 我相信尼基塔正在做什么，但我看不到细节。
在2只猫的情况下，公式没有区别，但是对于更多的猫，答案可能不同。 [Nikita，因为你有代码，你是否介意运用替代公式来看看结果是否相同 – 如果是，那么可能有一个最优性的certificate – 在这种情况下，你的公式是正确的，比矿。]
更新 ：添加了源代码和一些示例结果。
