磨剑（6）易碎的玻璃杯

Tags: iq

——————— 好几年前写的东西了，朝花夕拾。

题目

有一栋100层高楼,从某一层开始扔下的玻璃杯刚好摔坏,现有两个玻璃杯,最少几次能找到那一层？

首先我要对题目的表述提点意见。这是一个很有歧义的表述方式，容易误导人向概率的方向去思考。
比如说，我可以回答“最少一次能找到那一层”。我就拿个杯子，从一楼起一层一层的摔。从概率上讲，有可能在一楼就碎了。这不也合题意么。
我觉得题目可以这样表述：

有一栋100层高楼,已知存在一个特殊的楼层，低于这层，摔玻璃杯不会碎；从这一层起往上，摔玻璃杯一定会碎。现在有两个玻璃杯，请设计一种策略，确保一定能在N次内找到这个特殊楼层，并且尽量让N最小。

解答

先随意的考虑几种情况，打开思路：
  1. 一层一层的从下往上摔，这也是一种策略，完全碰运气。可能在第1层就破了，也可能到100层才破。这个策略的N就等于100。
  2. 隔一层摔一下，1，3，5，7…99，假设在7层层破了，我们拿另一个杯子回第6层试一下。这也能找到那个特殊层，并且比第一种优秀，只需要51次就OK了。
  3. 二分法试试。先在第50层摔，如果碎了，我们面对50层楼和一个杯子，只能一层一层往上试了，与第2种方式没有优势。如果没碎，我们倒可以换75层去试试看。
如果第一只杯子破了，第二只就只能一层一层的试，直到破为止。通过这几种尝试，可见关键在于第一只杯子怎么利用。
上面第三种思路给我们一个灵感，从第A层开始摔，至少能保证100-A次内找到特殊层。

根据这个思路，解答如下：
    假设我们有一种最优策略，使得N次内总能找到特殊层。
    第一次选在A层摔，破了，说明特殊层在1到A之间，用剩下的那只杯子，至少能在A-2次内找出特殊层。
    由于A是最优解，那我们可以最大化的利用第一次的跨度，使得A=N+1。
    下一个尝试点应该是A+(N)=(N+1)+(N)。为什么？
    如果这层发现第一个杯子摔碎了，就需要用第二个杯子一层一层试。从A到A+N，中间共N-1层楼，只需要N-2次就可以试出来。由于我们已经甩过两次杯子了，所以N-2正好是我们能够做的尝试次数。
    同理，第三次选的楼层应该是(N+1)+(N)+(N-1)，……可以看出,这是一个等差数列，那么第n次选择的楼层应该是,
    (N+1)+(N)+(N-1)+…+(N+2-n) = n(2N+3-n)/2

    另外，最后一次尝试如果小于99，是不可能完成任务的。
    所以我们又有，当n=N时，n(2N+3-n)/2 >= 99,由此可推出：N>=13
对于13，导出我们的序列为：
14,27,39,50,60,69,77,84,90,95,99,
共有11个尝试点，不难验证，这是可行的。

其实后面还可以推出102，104，即13次尝试，一定能从104层楼中找出那个特殊层。
100层楼没有用尽这个策略的所有“能量”，所以对尝试点的选择还可以有一些变化，
比如，每个尝试点都可以往前平移，只要保证第13个尝试点大于等于99。