把猫扔出窗户

一尘不染

把猫扔出窗户

algorithm

想象一下，您在猫的高楼大厦中。这只猫可以从低矮的窗户掉下来，但从高处摔下来会死。您如何用最少的尝试次数找出猫可以存活的最长下落？

显然，如果您只有一只猫，则只能进行线性搜索。首先从一楼扔猫。如果它仍然存在，请从第二个开始扔掉。最终，从地板f掉下来的猫会死。然后，您知道f-1楼是最大安全楼。

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

通常，对于有2只猫的n层建筑物，什么是最佳策略，哪一种是最坏情况的复杂性？ n层和m只猫怎么办？

假设所有猫都是同等的：它们都将存活或死于从给定窗户掉落的猫。同样，每一次尝试都是独立的：如果一只猫摔倒幸存下来，那就完全没有伤害了。

这不是家庭作业，尽管我可能已经解决了一次学校作业。今天，这只是一个异想天开的问题，我不记得了。如果有人知道此问题或解决方案算法的名称，则奖励积分。

阅读 250

2020-07-28

共1个答案

一尘不染

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

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

2020-07-28