主题:【原创】由一个简单的面试题想起的 -- 东方射日
共:💬43 🌺18 新:
假设F(N,P)代表用P个包裹在最佳方案下的平均测试数
则显然
F(N,1)=(1+2+...+N)/N=(N+1)/2
如果包裹数大于层数则
F(N,P)=F(N,N)
F(2,2)=2
P大于1时
假设第一次包裹放在L层
F(N,P)=L/N*F(L-1,P-1)+F(N-L,P)*(N-L)/N
第一项代表第一次试验摔坏的情况,第二项代表未摔坏的情况
显然选取L使得上式最小时为最优
这样P=2时可以递归计算出最优解
- 相关回复 上下关系8
🙂楼主能不能说说是哪个公司的面试? octane99 字0 2007-03-02 23:17:12
🙂不太懂高等数学, 胡思乱想一下,第一个应该从第二层起 三力思 字48 2007-02-28 11:00:53
🙂第一层不行还有第0层--地面嘛 东方射日 字0 2007-02-28 11:23:55
🙂想了一下,这个问题可能可以用动态规划
🙂表达式里的几个关键小错误。附解 4 大洋芋 字2275 2007-03-02 19:32:38
🙂佩服的五体投地 泰让 字99 2007-03-06 09:25:06
🙂我搞糊涂了,不就是一个二元函数的极值吗? octane99 字169 2007-03-02 23:08:13
🙂看来我忽略了一个条件,越高摔坏的概率越高, octane99 字64 2007-03-02 23:16:37