来源：高通面试题
题目：有一栋100层的楼，和2个坚硬的鸡蛋，从楼上扔下鸡蛋，鸡蛋会在大于某一层刚好开始碎，在最坏情况下，最少要扔多少次，才能一定找出这个临界楼层？
错误思路：二分法，100-50-25-12-6-3-1 但是这样不同的临界楼层，扔的次数都是不一样，最多高达50次（但是实际上有更少的次数）
如临界楼层为49，第一个鸡蛋在50层碎了，之后第二颗鸡蛋为了找到临界楼层只能一层层地从一层向上找，直到49层。
正确思路：：
首先要理解题目，
其一：无论临界楼层在100层的哪一层，我保证最多扔多少次？
其二：两个鸡蛋的作用，第一个鸡蛋用来分段，第二个鸡蛋用于逐层扫描，以找到临界楼层
那么在最坏的情况下，第一个鸡蛋向下分的段越大，会导致最后的结果也就越大（如二分法的50次）
因此我们不妨有一个聪明的做法就是第一个鸡蛋给予可扫描的段+已经扔的次数是固定的 这样无论临界层在哪，第一个鸡蛋给予可扫描的段+已经扔的次数=总扔的次数 都是差不多的。具体做法：每多试一次第一个鸡蛋，第二个鸡蛋需要扫描的范围就减少一层。
如第一个鸡蛋先扔第14层：
假设碎了，那么第二个鸡蛋逐层扫描，最坏是14层
假设没碎，那么第一个鸡蛋就放在27层（14+13层），即使在14-27扫描，最坏也是14次，之后这样依次递减 这样无论临界楼层在哪一层 最坏都是14次
那第一个鸡蛋的14层是怎么确定的呢？我们可以知道之后段的范围是不断递减的，所以我们希望之后递减到1的时候能超过100层了，因此要计算 1+2+3+4+...+n >= 100,得到n最小为14
Top comments (0)