学步园

前几天帮忙电话面试，问了这道经典的题目。当然，我第一次看是摔2个鸡蛋，第二次看是摔2个XBox，到我这里改成摔PS3了……与时俱进。

题目的原文是：现在有100层楼，已知PS3（XBox，鸡蛋……等等）从其中某层开始，摔下来后就会损坏。现在给你2台PS3，那么最少摔几次就肯定可以确定这个层数？

这里面当然有一些隐含的规则，比如说必须在N-1层摔过正常在N层摔过损坏才能得到结论，比如说摔坏后这个PS3就无法继续验证了，比如说2台都摔坏而得不出结论时就Game Over，等等。

被问的很多人一开始有点摸不着头脑，所以还需要举一个例子。比如说，我先用第一个PS3来确认一个大范围，把他从50层摔下去。如果损坏，那么拿第二个PS3从第1层开始逐层摔，直到找到那个N-1层正常N层损坏的那个N。如果正常，那么再从75层摔下去……这样2分。这就是一种策略。

比较聪明的受问者这个时候开始有反应了。这样一来的话，最坏的情况就是N为50或者49。为了得到结论，必须第一个PS3从50层摔下去损坏后，第二个PS3从1层摔到49层才能得出结论。总共需要50次，太多了。而实际上，因为摔下去正常的PS3完全可以继续用来做下一次验证，所以完全没有必要一开始从50层开始验证。

有人给的方案是先从10层，正常就20层，等等……直到损坏。那么当第一台PS3损坏时，范围已经缩小到类似11层到20层这样10层的小范围内，此时再用第二台PS3从11层摔起。这种方案的最坏情况是N为100或者99。此时第一台必须摔10次，第二台必须摔9次才能确认，总共需要19次。

标准的回答是先从14层摔，正常就27层，然后依次39，50，60，69，77，84，90，95，99，100层。如果14层损坏，那么用第二个PS3从1层摔到13层，最多总共13次，加上第一个PS3的1次，最多一共14次可以得到结果。如果27层损坏，那么从15层摔倒26层，最多总共12次，加上第一个PS3的2次，最多一共14次可以得到结果……等等。最终这个方案在任何情况下都能保证14次验证后就能得到结果。

本来原来的题目到这里就结束了。但是实际上，这里面还有很多东西。

首先就是，这个方案只是说明了，存在一种策略使得最多14次就能找到答案N，如何证明这14次是最少的？其次，这个方案是如何想到的？再次，如果说，因为Sony最近的降价我可以再给你一台PS3做实验，那么答案变成多少呢？

#剩下明天再写

#最近一段时间脑子比较木，答案一开始算成了15，实在是不好意思啊。感谢hua大力提醒！

当那个10层为单位开始摔的方案提出来后，可能很快就有人反应出来，整个验证的方案的骨架已经搭起来了。就是先用第一台PS3来确认一个区间，然后用第二台PS3来具体确定层数。而且，由于第一台每多摔一次，就意味着第二台必须少摔一次才能让总共摔的最多次数持平，这样一来，第一台摔的楼层一定是L，L+(L-1)，L+(L-1)+(L-2)……这样的序列，而第二台验证的层数也相应的为L-1，L-2……。这样就能保证总共最多摔L次就可以知道结果。显然，当第一台摔到第L次的时候，其应该从L(L+1)/2层摔。那么求一下L(L+1)/2>100的最小的L，答案就是14了。而且非但有了答案，也顺便把方案都给出来了。

不过如何证明这样的14一定是最小的呢？如果说13不满足L(L+1)/2>100的条件的话，那只能说按照上述的方案13次不可能，怎么能够证明不存在一个方案，在任何情况下最多摔13次就可以找到答案N呢？

如果只有一台PS3，那么怎么办呢？此时候没有任何办法，老老实实的从第一层摔吧。那么可以知道，对于一台PS3，其最多验证次数F等于其验证层数。换句话说，如果给一台PS3F次摔的指标，那么最多能验证连续的F层。

好了，现在回到问题，有两台PS3供选择。显然，如果假定最后摔了L次的话，那么第一台和第二台PS3分别摔的次数只能是（L,0)，(L-1,1)……这样的数对。而由归纳，第二台PS3在摔F次的时候最多只能验证F层，因此第一台摔L-F次后必须把答案确定在F层的一个区间内才行。如此一来，前面阐述的那个方案，不仅仅是最优的，而且是必然的。

所以，经过归纳可知，如果给两台PS3F次摔的指标，那么最多能验证连续的1+2+…+F = F(F+1)/2层。

依次类推，如果给三台PS3同样F次摔的指标，那么最多能验证连续的1+3+6+……+F(F+1)/2 = F(F+1)(F+2)/6层。

这样算下去，即便有再多的PS3，也能用一个公式来套住。

这个应该算一个覆盖问题，估计华校或者小学奥数班里面会有类似的题目。到底应该怎么去思考，本身就不是固定的事情。对于天才，或许自由一点能够找到更巧妙的方法。不过，我更相信大多数人只需要一种通用的，稳定的，能够解决问题的方法……

#最近忙的一个Bug，其实也不能算Bug，属于那种看上去完全摸不着头脑的那种。最后还是从头开始一点一点抠出少许希望来了。既然没有那种一眼找到症结的天才，沿着一条固定而稳定的路走也

///////////////////////////////////
该题也可以通过编程的方式，动态规划求解，但是太浪费时间，像上面的那种推理的方式，真是牛！