You are given eggs, and you have access to a building with floors from to .Each egg is identical in function, and if an egg breaks, you cannot drop it again.You know that there exists a floor with such that any egg dropped at a floor higher than will break, and any egg dropped at or below floor will not break.Each move, you may take an egg (if you have an unbroken one) and drop it from any floor (with ).Your goal is to know with certainty what the value of is.What is the minimum number of moves that you need to know with certainty what is, regardless of the initial value of ?
100 层楼 2 个玻璃球
起因是窥室友手机屏, 看到他群里有人问一个经典问题.
两个一模一样的玻璃球, 两个玻璃球如果从一定高度掉落到地上会被摔碎, 如果在这个高度以下往下扔怎么都不会碎, 现在已知这个恰巧摔碎的高度范围在 1 层楼到 100 层楼之间, 如何用最少的试验次数, 用这两个玻璃球测试出玻璃球恰好摔碎的楼高呢?
题目的意思是只要玻璃球不碎, 那么它是不会受到损伤的, 即临界层数 (最低摔碎楼层) 不变. 给定一个策略 , 表示临界层数为 时, 该策略需要测试的次数, 则最少测试次数是指 .
当只剩 1 个球时, 只能一层一层往上测试. 第 1 个球的任务是减少第 2 个球所需测试的次数. 直观上讲, 第 1 个球测试点的间隔要越来越小, 这样第 2 个球所需测试次数少, 才能保证总次数一定.
记最少测试次数为 , 即最优策略的最坏测试次数为 . 若第 1 个球第 次测试 (之前都没碎) 在 层下落
没碎, 则 次测试时, 问题归结为求 层楼的最少试验次数. 摔碎, 则第 2 个球要在 次内在 层楼中完成测试. 而第 2 个球 次最多只能在 层楼中定位临界层数.
因此 2 个球 次测试最多可以在 层楼中定位临界层数. 最小测试次数即 . 策略并不唯一, 例如令 , 其中 .
层楼 个玻璃球
一个很自然的问题是, 若有 个玻璃球, 求在 层楼中定位临界层数需要的最少测试次数. 类似上题, 考虑 个球 次测试最多能在 层楼中定位临界层数. 若第 1 个球第 1 次测试在 层下落
没碎, 则剩下 个球, 次机会, 至多还可以在上面的 层楼中定位临界层数. 摔碎, 则剩下 个球, 次机会, 至多还可以在下面的 层楼中定位临界层数.
因此
边界条件 , 或者说 , .
这个形式让人很自然地想起了 (广义) 组合数的递推式
所以要想办法把递推式中的 1 去掉. First attempt 是记 , 但是这样边界条件不对. 尝试 边界条件也不对. 记 , 则
这次边界条件对了, , , for . 易知
于是 个球 层楼, 最少测试次数是 .
class Solution:
def superEggDrop(self, k: int, N: int) -> int:
def f_k(m):
# if f(k, m) >= N, return True; else False
result = 0
c = 1
for x in range(1, k+1):
c = c * (m-x+1) / x # combinatorial number C_m^x
result += c # f(x, m)
if result >= N:
return True
return False
# binary search
left, right = 1, N
while left < right:
mid = (left + right) // 2
if f_k(mid):
right = mid
else:
left = mid + 1
return left
算法时间复杂度 , 空间复杂度 .
No comments:
Post a Comment