我采用了稍微不同的方法来解决问题。
我首先通过以下方法计算使用 x 只猫和 y 次猜测可以覆盖的最大楼层数。
从第一层开始，不断增加猜测次数，同时跟踪检查过的楼层、它们被检查的猜测次数以及每个楼层剩余的猫的数量。
重复此过程最多 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)
对于两只猫，可以在x次猜测中确定的最大楼层数为：
1、3、6、10、15、21、28...
对于三只猫：
1、3、7、14、25、41、63...
对于四只猫：
1、3、7、15、30、56、98...
经过广泛的研究（主要涉及将数字序列输入OEIS），我注意到的最大楼层遵循组合分段模式。
对于两只猫：
n < 2：2^n - 1
n >= 2：C(n, 1) + C(n, 2)
对于三只猫：
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 的正确解答。
对于任何希望检查不太平凡的内容，它给出了 (1 000 000, 5) = 43。
这运行时间为 O(n)，其中 n 是问题的答案（猫越多越好）。
但是我相信某个数学水平更高的人可以简化分段公式以在 O(1) 中计算。
