扔猫窗外 [英] Throwing cats out of windows

问题描述

想象一下，你是在一个高层建筑与猫。猫能存活下降了低故事的窗口，但如果从高楼层抛出就会死亡。你怎么能弄清楚，猫的存活时间最长下降，使用次数最少的尝试？

Imagine you're in a tall building with a cat. The cat can survive a fall out of a low story window, but will die if thrown from a high floor. How can you figure out the longest drop that the cat can survive, using the least number of attempts?

显然，如果你只有一只猫，那你只能搜索线性。第一掷从一楼的猫。如果它生存，从第二个扔了吧。最后，从地板F被抛出后，猫就会死。那么你知道，地板F-1是安全的最高楼。

Obviously, if you only have one cat, then you can only search linearly. First throw the cat from the first floor. If it survives, throw it from the second. Eventually, after being thrown from floor f, the cat will die. You then know that floor f-1 was the maximal safe floor.

但如果你有一个以上的猫吗？现在，您可以尝试某种对数搜索。比方说，在构建有100个楼层，你有两个相同的猫。如果抛出的第一个猫了50楼的，它死了，那么你只需要线性搜索50层。如果你选择了你的第一次尝试一个较低的楼层，你可以做的更好。比方说，你选择解决问题20层楼的时间和第一致命的楼是50号。在这种情况下，你的第一猫会生存下来，从20楼和40航班从地板60临死之前你必须通过49单独检查地板41。这是一个共12次尝试，这比你需要有你试图使用二进制取消了50好多了。

But what if you have more than one cat? You can now try some sort of logarithmic search. Let's say that the build has 100 floors and you have two identical cats. If you throw the first cat out of the 50th floor and it dies, then you only have to search 50 floors linearly. You can do even better if you choose a lower floor for your first attempt. Let's say that you choose to tackle the problem 20 floors at a time and that the first fatal floor is #50. In that case, your first cat will survive flights from floors 20 and 40 before dying from floor 60. You just have to check floors 41 through 49 individually. That's a total of 12 attempts, which is much better than the 50 you would need had you attempted to use binary elimination.

一般情况下，什么是最好的策略，它的最坏情况的复杂性，对于n层楼房有2只猫？那么对于n层和M猫？

假设所有的猫是相同的：他们都将生存或下降死于一个给定的窗口。此外，每一次尝试都是独立：如果猫生存的下降，这是完全无恙

Assume that all cats are equivalent: they will all survive or die from a fall from a given window. Also, every attempt is independent: if a cat survives a fall, it is completely unharmed.

这是不是功课，虽然我可能已经解决了学校分配一次。这只是今天突然出现在我的脑海一个异想天开的问题，我不记得了解决方案。如果有人知道的求解算法的这个问题，或者这个名字的奖励积分。

This isn't homework, although I may have solved it for school assignment once. It's just a whimsical problem that popped into my head today and I don't remember the solution. Bonus points if anyone knows the name of this problem or of the solution algorithm.

推荐答案

您可以轻松地写一点DP（动态规划）的n个楼层和M猫一般情况下。

You can easily write a little DP (dynamic programming) for the general case of n floors and m cats.

主要公式， A [N] [M] = MIN（MAX（一[K - 1] [M - 1]，A [N - k]的[M]）+ 1） ：在1..1 每个K，应该是不言自明的：

The main formula, a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n, should be self-explanatory:

• 如果第一猫是从k个楼层抛出死了，我们现在有 K - 1 地板检查（均低于 K ）和米 - 1 猫（ A [K - 1] [M - 1] ） 。
• 如果猫生存，有是 N - 氏/ code>离开地板（上述 K所有楼层），仍然 M 猫。
• 在两个最坏的情况下，应选择的，因此最高。
• + 1 来自我们刚刚使用的一种尝试（无论是否猫已存活与否）的事实。
• 我们想尽一切可能的楼层找到最好的结果，因此分（F（K））：对于k在1..1

• If first cat is thrown from k-th floor and dies, we now have k - 1 floors to check (all below k) and m - 1 cats (a[k - 1][m - 1]).
• If cat survives, there're n - k floors left (all floors above k) and still m cats.
• The worst case of two should be chosen, hence max.
• + 1 comes from the fact that we've just used one attempt (regardless of whether cat has survived or not).
• We try every possible floor to find the best result, hence min(f(k)) : for k in 1..n.

据同意谷歌结果从拉夫Saxena先生的链接（100，2）。

It agrees with Google result from Gaurav Saxena's link for (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 在另一个数组。

You can easily find strategy (how to throw first cat), if you save best k in another array.

还有一个更快的解决方案，不涉及为O（n ^ 3）计算，但我有点困了。

There's also a faster solution, not involving O(n^3) computations, but I'm a bit sleepy already.

修改
噢，我记得在那里我看到了这个问题之前。

edit
Oh yeah, I remember where I saw this problem before.

这篇关于扔猫窗外的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！