把猫扔出窗外

您可以很容易地为N层和M类cats的一般情况编写一个小的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 .

与谷歌的结果一致 萨克萨 (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)计算,但我已经有点困了。

编辑
哦,是的, I remember where I saw this problem before .

根据 a recent episode of Radiolab (about "Falling") 一只猫在9楼达到了极限速度。在那之后,它会放松并且不太可能受伤。从30岁以上摔下来的猫完全没有受伤。最危险的楼层是5楼到9楼。

想象你和一只猫在一幢高楼里。这只猫能从一个低层的窗户掉下来,但如果从高的地板上摔下来,它会死的。用最少的尝试次数,你怎么能找出猫能存活的最长落差呢?

解决这个问题的最佳策略是,使用物理定律,首先调查假设为真的可能性。

如果你这样做的话,你就会意识到猫的生存机会实际上是增加了离地面的距离。当然,假设你把它从一个更高的建筑扔出去,比如马石油大厦,而不是一座更高的山,比如珠穆朗玛峰。

编辑:
实际上,您会看到一个未完成的骆驼分布。
首先,猫死亡的概率是低的(非常低的海拔),然后它变得更高(低海拔),然后再低(高海拔),然后再高(非常高海拔)。

我第一次在史蒂文·斯基纳的书里读到这个问题 算法设计手册 (练习8.15)。它遵循了关于动态编程的一章,但是 你不需要知道动态编程来证明策略的精确界限。 . 首先是问题陈述,然后是下面的解决方案。

鸡蛋从足够高的地方掉下来就碎了。如果是一栋n层楼,必须有一层楼F,这样鸡蛋就可以从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)的运行时间是多少?

只有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蛋

提出的两个鸡蛋的算法可以很容易地扩展到K鸡蛋。以固定间隔投下每个鸡蛋,这应被视为n的第k根的幂次。例如,对于n=1000和k=3,用第一个鸡蛋搜索100层的间隔,用第二个鸡蛋搜索10层,用最后一个鸡蛋搜索1层。

同样,我们可以证明没有一种算法更快 Θ(n**(1/k)) 从k=2证明中得出。

精确解

我们通过优化第一个鸡蛋落在哪里(地板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

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

你可以用数学的方法来处理它,但这是关于数学的好事情…在正确的假设下,0可以等于1(对于0的大值)。

从实际出发,你可以得到“相似的猫”,但你不能得到“相同的猫”。

你可以试着根据经验来确定答案,但我认为有足够的统计差异,答案在统计上毫无意义。

你可以试着用“同一只猫”,但那是行不通的,因为在第一次下降后,它不再是同一只猫了。(同样地,一个人不能两次踏入同一条河)

或者,你可以汇总猫的健康状况,每隔一段非常近的时间采样,然后找到猫“大部分活着”的高度(而不是“公主新娘”的“大部分死去”)。平均来说,这些猫会活下来(直到最后一次休息)。

我想我已经偏离了最初的意图,但是如果你走的是经验路线,我会投票决定从尽可能高的地方开始,并随着高度的降低继续把猫扔下去,直到它们统计上存活下来。然后再对活着的猫进行测试。

我用了一种稍有不同的方法来产生一种溶液。

我首先计算出可以覆盖的最大楼层 X 猫和 Y 使用以下方法进行猜测。

从1楼开始,不断增加猜测次数,同时跟踪检查的楼层,猜测检查了哪些楼层,每层还有多少只猫。
重复这个直到 Y 时代。

这个 非常 计算给定答案的效率低下的代码,但对少数猫/地板仍然有用。

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 遵循一个 combination 分段模式。

2只猫:
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的正确解。
对于任何想要检查一些不那么琐碎的东西的人,它给出(1000 000,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). 

我不能在上面阅读谷歌的blogspot(多亏了Worksblogwall),但我不认为直接的二进制风格的搜索是最好的。原因是二进制搜索是基于这样一个概念,即您要查找的答案在列表中的任何索引索引处都有相同的机会。然而,在这种情况下,情况并非如此。在这种情况下,答案接近范围一端的概率比另一端更高。我不知道如何在搜索中考虑到这一点,但这是一个有趣的想法。

所有这些关于猫的疯狂讨论……这只是一个用最小猜测(猫的数量)来猜测数字的问题。也不需要人为地(错误地)将无穷定义为解决方案的一部分。变量应该命名为上限或max try或类似的名称。 然而,问题的定义(猫的东西)有一些严重的问题,人们对动物残暴的潜能做出了反应,而且在现实生活中也存在这样一个问题的许多方面,例如空气阻力、重力是加速度,以及其他此类问题的现实生活参数。所以,也许应该以完全不同的方式提出这个问题。