算术

在网上多次看见相似的题目，有人给出了正确的答案，但没能够合理的说明为什么结果是最优的。所以我也出来伸展一下。题目如下：

你在一幢100层的办公楼里上班，现在给你两台Xbox，要求你用尽可能少的实验，确定把Xbox扔下而摔不坏的最高楼层。比方说，从30层丢下来没问题，但从31层丢下来就坏了，那么30层就是最高楼层。假设只要没超过这个最高楼层，Xbox摔几次都不会坏。允许把两台xbox都砸烂的情况下，最少要做多少次实验(把Xbox从楼上摔下多少次)才能保证找到这个最高楼层？请给出实验的方案。

基本的思路是：首先，把第一台Xbox每间隔几层楼摔一次，以推断出大致的范围。然后，用第二个Xbox从这个范围内最低的楼层开始实验，只要没摔坏就上一层楼再摔，直到找出第一个能将其摔坏的楼层。关键的问题是如何决定第一台Xbox实验的间隔。

假设第一个间隔是f_0，那么如果摔不坏的最高楼层位于[1, f_0-1]之间的话，我们最坏情况下需要f_0次实验才能确定。类似的，对于f_1，如果摔不坏的最高楼层位于[f_0+1, f_0+f_1-1]之间的话，我们最坏情况下需要1+f_1次试验。之所以要加1是因为已经在f_0楼做过了一次试验了。一般的，最坏情况的实验次数可以定义为f_i+i。

显然如果假设最少我们需要M次试验，每一个间隔应该满足下面的要求：
f_0≤M,
f_1≤M-1,
f_2≤M-2,
...
f_i≤M-i, i=M-1

而且至少有一个f_k=M-k，不然M就不是最小的实验次数了。我们可以注意到，对于一个特定的M，无论我们怎么分配间隔，只要符合上面的两个条件，最坏情况的实验此数是相同的。

在满足以上条件的情况下，如果要求
f_0=M,
f_1=M-1,
f_2=M-2,
...
f_i=M-i, i=M-1

可以看出，经过不超过M次试验，我们最多能处理的楼高为∑f_k。这个其实就是个等差数列，所以对于M次试验，楼层不能高于M(M+1)/2层。M=13时，能够处理91层的楼，M=14时，能够处理105层的楼。显然我们只要14次试验就能处理这栋100层的楼。

不过因为我们能够处理105层的楼，而这栋楼只有100层，我们的能力有所富余。因而有些f_k可以小于M-k，而不一定非要等于。所以最后的我们可以有多种不同的方案，只要这些0≤f_k≤14-k，并且∑f_k=100。

到此这个题目算是完成了，还有三点说明：

• 解题的过程中我假设不知道是否从最高层扔下会导致Xbox摔坏。如果已知一定会摔坏的话，只要将楼高减1即可用同样的方法解出。
• 常见的另一种思路使用动态规划，实际上就是对归纳法的一种模拟。已知层高位1,2,...,n时的最优方案，求层高为n+1时的最优方案。只是这种方法很难手工给出答案。
• 这道题所关注的是如何减少最坏情况下的试验次数。如果是对平均情况下的试验次数进行优化，基本思路相同。