- 程序有所改变。发帖如还有问题请报告
- 【征集】西西河的经济学，及清流措施，需要主动参与者，『稷下学宫』新认证方式，24年网站打算和努力目标
主题：【原创】由一个简单的面试题想起的 -- 东方射日
家园 要澄清一下问题阿 问的到底是什么,是很关键的。到底是要期望次数最小，还是要最坏情况下(worst case)次数最小？如果是前者，不给出概率分布是没法做的。楼下很多假设平均概率，虽然很合理，但属于自己擅自加的条件了。考虑到东方射日很可能是面试的计算机职位，又考虑到很多类似的问题也是要求最坏情况下最优解（比如１２个砝码其中一个与其它不同，要求用一个天平把它找出来），我觉得后者的可能比较大。
如果确实是要找最坏情况下最优解，那么用动态规划是很简单的。
假设f(x)代表x次试验最坏情况下最多能覆盖的楼层数。那么
f(0)=1
f(n)=n+f(n-1)
递归式的解释是这样的。在允许n次试验时，第一次试验在n+1楼层。分情况讨论。假如摔坏，那么1<=M<=n,剩下的一个好包裹能保证在最坏情况下用n-1次试验找到M。假如不坏，那么n+1<=M<=N,两个包裹还都是好的，根据递归假设，用n-1次试验还能覆盖f(n-1)个楼层，所以N-(n+1)+1=f(n-1), N=n+f(n-1)。
所以f(n)=n(n+1)/2+1。
验算一下。f(3)=3(3+1)/2+1=7。方法是，第一次试４。假如破，剩下一个从２往上试（因为根据前提条件，1<=M<=N,所以第一层一定是安全的，从楼下东方射日回复三力思看，我怀疑这个前提条件是不是给错了？不过这个没多大关系，0<=M<=N答案也差不多。）最坏情况下一直到3都不破，又试验了２次，共３次。假如在４不破，4<=M<=7,第二次试验6。假如在６破了，第三次试验５；假如在６不破，第三次试验７。
家园 概率极小，与极大极小可能有不同解 包裹1的试验序列是M(1),M(2),...M(K).M(i)<M(i+1).
如果包裹1在M(j)摔坏,包裹2的试验序列从M(j-1)+1开始向上逐层试验.
假设包裹在第i层摔坏的概率是P(i),P(i)<P(i+1).对每一个试验序列M(1),M(2),...M(K),包裹1+包裹2的试验的概率次数就定了.设这个次数为f(M)(在概率序列P一定的情况下,次数只跟序列M有关.应该用程序计算这个f吧).概率极小解是,给定N,给定概率序列P(1),P(2),...P(N)。在所有可能的序列Ｍ中，找出使得f(M)最小的那个Ｍ。（俺这个算解吗？好象至少把问题问清楚了。。。。）
极大极小解类似，也是对序列Ｍ求解，只是不用概率序列P的假设了。
家园 楼主能不能说说是哪个公司的面试？ 家园 不太懂高等数学， 胡思乱想一下，第一个应该从第二层起 理由是就是第一层不安全，你也只能放在第一层。
家园 第一层不行还有第０层－－地面嘛
家园 想了一下，这个问题可能可以用动态规划 假设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时可以递归计算出最优解
家园 表达式里的几个关键小错误。附解 F(N,P)=Min{(L-1)*(1+F(L-1,P-1))/N+(1+F(N-L,P))*(N-L)/N} 你的表达式里缺了三个1，最后一个非常重要。（其实现在这个表达式也不全对，L=1，N时不成立，但是这不影响下面的分析，因为N很大时我们相信最小值不会在L=1或N时取到）
显然有F(N,P+1)<=F(N,P)…………………………………(1)
只考虑N>>1的情况。用归纳法证明F(N,P)∽A(P)N^B(P)，B(P)<=1，并求出A(P)，B(P)。
P=1时命题成立。现在假设F(N,P)∽A(P)N^B(P)成立，计算F(N,P+1)。可以合理地假设取到最小值的那个L满足1<<L<<N………………………(2)
把(1+F(L-1,P-1))*(L-1)/N+(1+F(N-L,P))*(N-L)/N对L/N展开，并考虑条件(1)，得
(1+F(L-1,P-1))*(L-1)/N+(1+F(N-L,P))*(N-L)/N
≈F(N,P+1)+1-L(F(N,P+1)+NF'(N,P+1))/N+A(P)/N*L^(B(P)+1)+无穷小量。
对L求导得到最小值，按定义这个最小值就是F(N,P+1)，也就是说
1-L(F(N,P+1)+NF'(N,P+1))/N+A(P)/N*L^(B(P)+1)的最小值必须是零。由此可以得到
F(N,P+1)+NF'(N,P+1)≈c*N^(B(P)/(1+B(P))，因此F(N,P+1)≈A(P+1)N^B(P+1)，
这里的B(P)=1/P，A(P)=P/(P+1)(P!)^(1/P)
当P趋于无穷大时A(P)≈(P-1)/e+Log[2πP]/(2e)。
L(P)∽N^(1-1/P)*P/(P!)^(1/P)
愿意的话可以进一步算得
F(N,P)=P/(P+1)(P!)^(1/P)*N^(1/P)+C(P)+o(1)
C(1)=1/2，C(P)=(P-2)/2，P>1
L(P)∽N^(1-1/P)*P/P!^(1/P)+D(P)+o(D(P))
D(P)=-N^(1-2/P)*P(P-1)/(P!)^(2/P)/2
可以把它们组合成更紧凑的形式L(P)∽E*(N-E/2*N^(1-1/P))^(1-1/P)
E=P/P!^(1/P)
实际值与近似值的差
P=2 F(N,2)-(Sqrt[8N/9]-4/3/Sqrt[N])
P=3 F(N,3)-((81N/32)^(1/3)+1/2)
P=4 F(N,4)-((6144N/625)^(1/4)+1)
F(N，2)的进一步估计
F(N，2)≈(8N/9)^(1/2)-4/3/Sqrt[N]+Abs[Cos[πSqrt[2N]]]/(π(Sqrt[π N]-5))，最后一项分母里的常数不是太靠得住。
“量子化”条件：当Sqrt(2N)=n+1/2时估计式(8N/9)^(1/2)-4/3/Sqrt[N]的精确度特别高，此时L=n，当
Sqrt(2N)=n时精确度最差，此时L=n-1/2。
点：F(N,2)-(Sqrt[8N/9]-4/3/Sqrt[N])
红线：Abs[Cos[πSqrt[2N]]]/(π(Sqrt[π N]-5))
F(N，P)里总是有一些振荡现象，这是因为近似计算时总假设N，L为实数，但实际上它们只能是整
数。猜想这些振荡可以用Abs[Cos[πP(N/P!)^(1/P)+Pπ/2]]/N^(1/P)来很好地逼近。比较麻烦的是
F(N，P)的振荡会遗传给F(N，P+1)。这会使得寻找参数的难度变大。
家园 [花]都是牛人呀！ 家园 你的直觉很准嘛，最佳方案真是需要递减步长。 家园 汗～～～我第一直觉是采用递增步长啊！后来仔细想才发现用递减步长！ 思路缓慢啊～～
现在再整理一下思路，当然是递减步长。
首先层数为N时，我们第一步长为S=sqrt(N)，在尝试后，问题简化为层数为N-S的问题了。
就很容易得到上述答案。
看来数学不好是不行。这样的问题我就是无法用数学语言说清楚！