把猫扔出窗外

Question

想象一下,你在一座有猫的高楼里.这只猫可以在低矮的故事窗口中摔下来,但如果从高楼层抛出,它就会死亡.你怎么能用最少的尝试数来计算猫可以存活的最长时间？

显然,如果你只有一只猫,那么你只能线性搜索.先从一楼扔猫.如果它存活下来,从第二个扔掉它.最终,从地板f抛出后,猫会死.然后你知道楼层f-1是最大的安全楼层.

但是,如果你有一只以上的猫怎么办？您现在可以尝试某种对数搜索.让我们说这个版本有100层,你有两个相同的猫.如果你将第一只猫从50楼扔出去并且死亡,那么你只需要线性搜索50个楼层.如果您为第一次尝试选择较低楼层,则可以做得更好.假设您选择一次解决20个楼层的问题,并且第一个致命楼层是#50.在这种情况下,你的第一只猫将在从60楼死亡之前从20楼和40楼的飞行中幸存下来.你只需要分别检查楼层41到49.这总共有12次尝试,这比你试图使用二进制消除所需的50次要好得多.

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

假设所有猫都是等同的:它们都将从给定窗口的摔倒中幸存或死亡.此外,每一次尝试都是独立的:如果一只猫在跌倒时幸存下来,它就完全没有受到伤害.

这不是家庭作业,虽然我可能已经解决了一次学校作业.这只是一个异想天开的问题,今天突然出现在我脑海中,我不记得解决方案了.如果有人知道此问题的名称或解决方案算法的加分点.

Answer 1

根据Radiolab最近的一集(关于"Falling"),一只猫在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)的谷歌结果.

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.7米/秒= 25.4码/秒].
人体终端速度为210 km/h(130mph).[= 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-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个最后一个蛋.

类似地,我们可以?(n**(1/k))通过从k = 2证明中引入来证明没有算法更快.

准确的解决方案

我们通过优化下降第一个鸡蛋(地板g)的位置来推断复发,假设我们知道较小参数的最佳解决方案.如果鸡蛋破裂,我们在下面的g-1楼层用k-1鸡蛋进行探索.如果鸡蛋存活,我们在上面的地板上用k蛋进行探索.魔鬼为我们选择了最坏的.因此,对于k> 1的复发

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