动态最优化经典面试题

最近看到了一条史前的算法面试题,觉得挺有意思的,虽然网上已经有了很多完善的答案,但是我还是想自己整理一遍,强化印象,同时也和大家分享一下这道12年的Google题目:

一幢 200 层的大楼,给你两个鸡蛋。如果在第 n 层扔下鸡蛋,鸡蛋不碎,那么从第 n-1 层扔鸡蛋,都不碎。这两只鸡蛋一模一样,不碎的话可以扔无数次。最高从哪层楼扔下时鸡蛋不会碎?

先形象的理解一下这道题目,假设第一个蛋我们放在了i层,有两种case,碎或者不碎。
先看简单的结果,
case1:如果碎了,为了求出层数,那么我接下来的那颗蛋需要从第1层开始尝试i-1次,因为我们不允许冒第二次碎的风险了,这很好理解。
case2:如果没碎,我们得知一条新的信息,那就是我们要求的目标层在i层之上,但是我们依旧不知道是哪一层,假设是m层(m>i),那么同样的,和第i层一样,面临2个case,碎或者不碎。

这时候,我们的前提是在最恶劣的情况下,保证我们的每次的风险都尽可能的小,至少要少于上一次的风险。

我们可以让新的m的高度为i+i-1,其中,i是第一次我们放的层数,i-1是我们选择的风险若于第一次风险的层数高度,类推下去:i+i-1+i-2+i-3+…+1=200,得到i=20,就是我们第一次应该放的位置,同理第二次如果没有碎应该放的就是39…

我个人对这道题目的理解中,其实就为了平分风险,让每次碎的高度都相等,也就是i-1 = m-i-1+1==>m=2i-1

这边的python代码网上也有很多,这边我罗列一个我写的,可能和别人的不一样,实现效率也可能较慢,建议大家在网上搜完善版本的,仅供大家熟悉上述的描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
#n为层数,m为蛋数,f函数为求最优层数
def f(n, m):
#如果是0层的,返回最优层数为0
if n == 0:
return 0
#如果只有一个鸡蛋,必须要从最低层开始试,所以为当前最安全层n
if m == 1:
return n
#这边我们来看,f(i - 1, m - 1)是如果i层碎了,我们需要计算i-1层下的情况,同时减少一颗蛋;
#f(n - i, m)是i层没碎,那相当于安全层从0变成了n,要计算的就是相当于有 f(n, m)变成了 f(n - i, m)
#最后在最大化风险下找出其中风险最小的层数即可
best_floor = min([max([f(i - 1, m - 1), f(n - i, m)]) for i in range(1, n + 1)] + 1)
return best_floor

结果:

1
2
In [74]:print(f(100, 2))
14

这边f(200,2)实在没跑出来,时间太久了,所以跑了100,2的结果,迭代次数超多,具体我没有算过,建议优化一下计算的代码再执行。

最后谢谢大家阅读。

打赏的大佬可以联系我,赠送超赞的算法资料