- 发帖可能变空内容，邪门暂不知所以然
- 『稷下学宫』新认证方式，24年网站打算和努力目标
主题：【原创】由一个简单的面试题想起的 -- 东方射日
家园 【原创】由一个简单的面试题想起的 有一个N层的货架，你需要知道特定包裹在该货架上的最大＇安全高度，即从M（１＜＝M＜＝N）层摔下，包裹不会摔坏。
前段时间换工作，经历几个面试，有一题是这样的：
有一个N层的货架，你需要知道特定包裹在该货架上的最大＇安全高度，即从M（１＜＝M＜＝N）层摔下，包裹不会摔坏。
给你一个试验包裹，如何以最快的方式找到M？
－－－－我当时就是一愣，自演言语说从一层开始一层层往上试。那么还有什么更好的方法吗？面试的人打断我,别想太多，那就是唯一的方法。
他接着问,如果给你两个试验包裹，如何以最快的方式找到M？给出你的解答！
我首先想到的是两层两层地试第一个包裹，不过马上自己否定了，仔细想了下，在白板上写：
第一个包裹取步长为s向上试，直到摔坏为止，试验次数为 ：
t1 = INT[(M-1)/S]+1 (INT指取整)
第二个包裹在第一个包裹确定的区域内一层层向上试，直到摔坏为止，则最后一次没有摔坏的那层就是M。共试验：
t2 = M-MOD[(M-1)/S]*S
当时就想到，从常识上，Ｍ越大，应该选用的Ｓ就应该越大，也是应该存在阀值使ｆ（Ｓ，Ｍ）＝（ｔ１＋ｔ２）＝ｆ（Ｓ＋１，Ｍ），算出Ｓ＝（ｓｑｒｔ（４Ｍ－１）－１）／２，计算中忽略了取整和取摸运算子。
不过我仔细再一想，不对啊，我们事前并不知道Ｍ，只知道Ｎ，如果我们假设每层包裹摔坏的机会相当，最优解就是使总测试平均值最小的步长S值：
{SGM（M=1,N）[t1 + t2 ]} / N (SGM: 求和运算子)
解上式 得S＝f(N)
我只做到这一步，至于求和和算最小值我也不会. 还好，对方说＂Good enough＂
回来后仔细想拉想这题，觉的学问还不只这些，自己又提出以下问题:
前面我们一直是想找出试验第一个包裹使平均试验次数最少的最优解步长S，并且这里我们忽略了我们又有另一个假定在里面，就是假定Ｓ是一个定值能使解最优。但是如果采用变化步长，是否有更优的结果呢?
比如我们采用递增步长，直觉上觉得菲波那契级数或者其他的递增级数可能有更好的结果。但是自己数学能力实在不够，无法证明和计算。
河水深了，什么大鱼都有。就抛个砖等大鱼来吧。
======
又仔细想了，应该采用递减步长，即第一个包裹试验步长为剩下层数的sqrt(N) ＋1/2。
例如N＝１５层时，第一个包裹试验第４、８、１１、１３、１４、１５层，这样平均尝试次数为６７／１５次。如果采用固定步长４，平均尝试次数为６９／１５次
但是还是不能以数学语言给出这解答
关键词(Tags): #数学，
本帖一共被 1 帖 引用 (帖内工具实现)家园 EMC现在状况到底如何？ 感觉EMC也是一直亏损，
但是日子过得倒是很滋润。
家园 这是今年EMC的笔试题，看来老贴子里净是宝贝啊 。。。
家园 如果确实是包裹云云，则是个实践问题，就每个摆一层， 从下往上。
家园 【原创】把摔蛋进行到底 摔包裹更有意义。。。
楼下有了论文链结，那个论文又是定理又是引理的，似乎太长了点。来一个短的。。。
前提，或者说，假设，那个论文给的够详细了，不再重复。这里只是指出一点：
设M1<M2,那么，事件｛包裹在M1摔坏｝包含了事件｛包裹在M2摔坏｝。或者，事件｛包裹在M2不摔坏｝包含了事件｛包裹在M1不摔坏｝。记P(M1)为事件｛包裹在M1摔坏｝的概率，P(M2)为事件｛包裹在M2摔坏｝的概率，那么事件｛包裹在M2摔坏|包裹在M1不摔坏｝的概率是P(M2)－P(M1)。
设包裹1的实验序列是｛M(1),M(2),...M<(K)｝，不失一般性，可假设M(K)=N。因如果M(K)<N，总可以将包裹2的最后一次实验转移到包裹1，从而M(K+1)=N。
设包裹在1,2,...,N层摔坏的概率分别是P(1),P(2),...,P(N)。为记号简单，补充M(0)=0,P(0)=0.
１。极大极小解
包裹1的实验序列是｛M(1),M(2),...M<(K)｝，
f(M)=MIN(包裹1的最大次数＋包裹2的最大次数)
=MIN(K+MAX(M(j)-M(j-1)-1){j从1到K})
对于固定K，当序列｛M(1),M(2),...M<(K)｝步长不均时，MAX(M(j)-M(j-1)-1){j从1到K})将变大，所以极小解只在那些等步长序列中达到（忽略取整因素）。
序列｛M(1),M(2),...M<(K)｝等步长时，
f(M)=MIN(K+N/K-1)
上式在K=N/K，或K=sqrt(N)时，有极小值，
f(M)=2*sqrt(N)-1。
可做推广，3个包裹时，极值函数是
f()=MIN(K+J+N/(K*J)-2),对K、J求极值。
在K＝J＝N/(K*J)，或K＝J＝N^(1/3)时，
f()=3*N^(1/3)-2
再推广，Ｌ个包裹时，f()=Ｌ*N^(1/Ｌ)-Ｌ＋１。
打字困难，概率极小的情形待续。。。。。
家园 还琢磨呢？ m个蛋，最坏情况下扔n次，所能涵盖的楼层为f(m,n)
1. 当m=1, f(m,n)=n
2. 当m>n, f(m,n)=f(n,n)
3. 当n>=m>1,f(m,n)=f(m-1,n-1)+f(m,n-1)+1
于是,显然地,m个蛋，s层楼，最坏情况下需要扔
min{n;f(m,n)>=s}次。
举个例子，2个蛋，f(2,n)=f(1,n-1)+f(2,n-1)+1=n+f(2,n-1)=n+...+1
4个蛋，
f(4,1)=f(1,1)=1
f(4,2)=f(2,2)=f(1,1)+f(2,1)+1=f(1,1)+f(1,1)+1=3
f(4,3)=f(3,3)=f(2,2)+f(3,2)+1=f(2,2)*2+1=7
f(4,4)=f(3,3)+f(4,3)+1=15
f(4,5)=f(3,4)+f(4,4)+1=f(2,3)+f(3,3)+16=6+7+16=29
f(4,6)=f(3,5)+f(4,5)+1=f(2,4)+f(3,4)+f(3,4)+f(4,4)+3=10+13+13+15+3=54
就是说，4个蛋，20层楼，最坏需要扔5次。50层楼，需要6次。
家园 【原创】把摔蛋进行到底(续) １的极大极小解相当于毫无经验的新手的情况，属于摸着石头过河。
实际上，某一类包裹在哪一层摔坏，有一个先验概率。比如说，包裹是尼龙绳，一万米高空摔下，没事，直接放到最高层（第Ｎ层）就行了。如果包裹是瓷器，直接放到地板上。
一般地，有0=P(0)<=P(1)<=P(2)<=...<=P(N)<=1
２。概率极小解
根据最开头的说明，包裹１的平均概率次数是：
SUM(j*(P(M(j))-P(M(j-1)))){j从1到K}
记
Aj={包裹１在M(j-1)层没有摔坏，在M(j)层摔坏时，包裹２的平均概率次数｝
那么，Aj=SUM(j*(P(j)-P(j-1))){j从M(j-1)+1到M(j)-1）}
包裹２的总的概率次数是对j相加：
SUM((P(M(j))-P(M(j-1)))*Aj){j从1到K}
极值函数就是包裹１、包裹２的概率次数相加：
f(M)=SUM(j*(P(M(j))-P(M(j-1)))){j从1到K}
+SUM((P(M(j))-P(M(j-1)))*Aj){j从1到K}
其中Aj=SUM(j*(P(j)-P(j-1))){j从M(j-1)+1到M(j)-1）}
问题就是，求使得f(M)取极小值的那个序列Ｍ。函数定了，剩下就是程序求解了。
上面的式子有两种极端情况：
１。0=P(0)=P(1)=P(2)=...=P(N)，f(M)=0,相当于包裹是尼龙绳，直接放到最高层，不用摔，平均概率次数是0。
２。1=P(1)=P(2)=...=P(N),相当于包裹是瓷器。当M(1)=1时，f(M)=１。（包裹１在第一层摔坏，包裹２就在地板上了）
家园 【原创】把摔蛋进行到底(续)－更正。加尾巴。。。 上面概率极小解的平均概率次数公式中，少了尾巴。。。
包裹１的平均概率次数不应该是：
SUM(j*(P(M(j))-P(M(j-1)))){j从1到K}
而应该是：
SUM(j*(P(M(j))-P(M(j-1)))){j从1到K}+K*(1-P(N))
前边SUM中的是摔坏的概率贡献，而最后的尾巴项K*(1-P(N))是摔不坏的概率贡献。
同样，
Aj：{包裹１在M(j-1)层没有摔坏，在M(j)层摔坏时，包裹２的平均概率次数｝
也应该加上尾巴项，应该是
Aj=SUM(j*(P(j)-P(j-1))){j从M(j-1)+1到M(j)-1）}
+(M(j)-M(j-1)-1)*(1-P(M(j)-1))
这样，极值函数就是
f(M)=SUM(j*(P(M(j))-P(M(j-1)))){j从1到K}+K*(1-P(N))
+SUM((P(M(j))-P(M(j-1)))*Aj){j从1到K}
其中
Aj=SUM(j*(P(j)-P(j-1))){j从M(j-1)+1到M(j)-1）}
+(M(j)-M(j-1)-1)*(1-P(M(j)-1))
最后的特例：
0=P(0)=P(1)=P(2)=...=P(N)，f(M)=１,相当于包裹是尼龙绳，还是需要在最高层摔一次的。。。。。
家园 这个式子不对 f(M)=MIN(包裹1的最大次数＋包裹2的最大次数)=MIN(K+MAX(M(j)-M(j-1)-1){j从1到K})
因为包裹2的最大次数依赖于包裹1的执行情况，比如说方法链接出处，最大次数大约是Sqrt[2N]。
F(N,P)≈A(P)N^B(P)，这里的B(P)=1/P，A(P)=P/(P+1)(P!)^(1/P)是等概率平均最小次数，我相信这种方法得到的最大次数也是最小最大次数。
家园 【文摘】有篇论文 http://ite.pubs.informs.org/Vol4No1/Sniedovich/
家园 Google面试题 这道题似乎源于ＧＯＯＧＬＥ的一道面试题：
有两个鸡蛋，１００级台阶，从台阶上往下掉蛋，怎么样用最少步找出从哪一个台阶开始蛋开始破。
我的答案是：
13 25 36 47 57 65 73 80 85 90 94 97 99 100
平均步数＝ 10.3
最坏 ＝ 14 （在１００级或１００级也摔不破）
方法：
f(n) = min(f(n,x)), x in [1,n]
f(n,x) = 1 + [x/(n+1)] * [ (x-1)/2 + (x-1)/x ] + [1-x/(n+1)] * f(n-x);
是典型的动态算法。
家园 del 家园 从台阶上往下掉 难道不是一阶一阶往下掉的末?
如果是那样
从第一百阶直接往下滚不就OK了?
家园 另一种思路 假设开始步长是 L，那么下一次步长应该是 L-1。因为你已经试过一次。
第一次如果破了：
f(n) = 1 + f(L-1);
第二次才破：
f(n) = 1 + f(L-1);
第三次才破：
f(n) = 1 + 1 + f(L-2);
所以：（当步长减到１时，你应该刚好走到终点）
L + (L-1) + .. + 1 = n - 1 （最后一步）
n=(L+1)*L/2 + 1
当n=100, L=13 （约等于）
补充：参照“走南闯北”给出的论文，我意识到这个结论是对最坏情况的（Ｌ＝１４)。平均情况还是得用上面的动态算法。