高层扔鸡蛋问题 - 算法及其优化_2个鸡蛋,100层楼,实际实验策略

基本问题：2个鸡蛋，100层楼

先看生活版的问题

问题描述

一栋高楼共有100层，鸡蛋从某个楼层（和此楼层以上高度）掉下来恰好会碎。现在小明手中有2个鸡蛋，他需要怎样才能尽快找出这个临界的楼层？（即在最坏情况下小明需要最少需要多少次才能找到答案）

问题分析

假如小明手中只有一个鸡蛋，那么方法必然只能是从第1层一层一层往上实验，直到临界楼层。最坏情况：100层是临界楼层，那么小明一共要尝试100次才能得到答案。

大家可能会想到用二分法来解决，那么我们第一个鸡蛋在100/2=50层的位置扔下。假如碎了，那么第二个鸡蛋必须只能从第1层一直试到49层，在最坏情况下(答案为49层时)，小明共要尝试50次才能得到答案；假如没碎，那么可以用第一个鸡蛋接着在第75层尝试，循环往复直到试出答案。于是可知，用二分法，最坏情况为50次。

那么用三分法呢？第一个鸡蛋扔在33层，最坏情况是（答案为32层时），小明需要1+32=33次才能得到答案。如果是分成10份呢？第一个鸡蛋扔在10层，然后20层…知道100层，最坏情况(答案为99层时)，小明共需要扔10(第一个鸡蛋)+9(第二个鸡蛋)=19次

当然也不是分的越细越好，比如说先分成100/5=20份的话。第一次在5层扔，第二次在10层扔，…，一直扔到95层还没碎，那么就已经试了19次了。

那么小明到底应该怎样扔呢？

数学解释

假设在最坏情况下，小明需要扔 x 次才可以测出临界楼层。小明首先在第 i 层扔出了鸡蛋，有两种情况：

• 鸡蛋碎了，那么小明的第二个鸡蛋只能从第1层一层层往上直到 i-1层 来测试，于是小明共尝试 1+i-1 = i 次，即 i=x
• 鸡蛋没碎，那么小明还剩下x-1次测试机会，于是第二次尝试楼层只能高出第i层 x-2 层（包括第二次尝试楼层）。

同理继续往下，可知若第二次没碎，第三次的楼层只能高出第二次楼层 x-3 层。于是得到方程：
$$x+(x-1)+(x-2)+...+1\ge 100$$
解得 x=14 ，即小明第一次在14层扔，若没碎，则在27层扔…。若一直都没碎，小明扔的楼层序列为：14,27,39,50,60,69,77,84,90,95,99,100。在最坏情况下(答案为13层时)，小明共需尝试14次。

问题升级：2个鸡蛋，n层楼

问题描述

楼层从100层变为"虚无缥缈"的n层楼，小明还是拥有两个鸡蛋，问小明最少需要多少次才可以测得临界楼层。

算法分析

设 f(n) 为n层的楼栋所需的最