- 程序有所改变。发帖如还有问题请报告
- 【征集】西西河的经济学，及清流措施，需要主动参与者，『稷下学宫』新认证方式，24年网站打算和努力目标
主题：【原创】由一个简单的面试题想起的 -- 东方射日
共:💬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 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