主题：【原创】由一个简单的面试题想起的 -- 东方射日

有一个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＝１５层时，第一个包裹试验第４、８、１１、１３、１４、１５层，这样平均尝试次数为６７／１５次。如果采用固定步长４，平均尝试次数为６９／１５次

但是还是不能以数学语言给出这解答

• 这不是原因，注意前提是每层摔坏的几率相同