# 7. 高楼扔鸡蛋
描述：有一栋 100 层 高的建筑，给你 2 个相同的鸡蛋。已知鸡蛋从某一特定楼层或更高的楼层扔下 会碎，低于此楼层扔下 不会碎。请 设计一个策略，确定这个 临界楼层，要求 最坏情况下的扔鸡蛋次数最少。
# 分析问题
- 核心目标：在最坏情况下，尽可能 减少扔鸡蛋的次数，确定鸡蛋会碎的最小楼层。
- 基本约束：
- 两个鸡蛋：意味着我们无法像二分查找一样随意尝试高楼层（因为如果第一个鸡蛋碎了，第二个鸡蛋只能逐层检查）。
- 最坏情况：要求策略在 任何情况下，最大扔鸡蛋次数尽可能少。
- 临界点：
- 如果鸡蛋在某层 碎了，那么它的 安全楼层 只能在这层以下。
- 如果鸡蛋 没有碎，那么它的 临界楼层 只能在这层以上。
# 朴素解法
# 1. 线性遍历法（最差 99 次）
从 1 层开始，每层递增 1 层 进行尝试，直到鸡蛋碎掉。
- 最坏情况：如果临界楼层是 100 层，需要扔 99 次。
- 缺点：效率太低。
# 2. 二分法（理论上可行，但风险大）
每次从 中间楼层 进行尝试，例如先尝试 50 层：
- 如果碎了，说明临界楼层在 1~49 之间，接下来只能 逐层测试（因为只剩一个鸡蛋）。
- 如果没碎，继续测试 51~100 层。
- 最坏情况：如果鸡蛋在高层碎了，第二个鸡蛋需要 逐层遍历，导致 最多 50 次扔蛋。
- 缺点：二分查找适用于 无损耗测试，但这里鸡蛋有限，直接二分并不是最优解。
# 最优策略：梯度递减法（数学优化）
# 思路
- 由于 只有 2 个鸡蛋，我们不能一次跳跃太多层，否则第一个鸡蛋碎了，第二个鸡蛋需要 一层一层试，导致次数过多。
- 目标：减少最坏情况下的扔蛋次数。
- 梯度递减策略：
- 第一次从 某一层 X 开始扔，如果碎了，直接逐层检查 1 到 X-1 层；
- 如果 没碎，下一次 减少 1 层的跳跃步长，即从 X + (X-1) 层扔，以此类推；
- 这样保证即使第一个鸡蛋碎了，剩下的楼层数也不会太多，可以快速检查。
# 具体计算
设鸡蛋的扔法为：
- 第一次扔 X 层
- 第二次扔 X + (X-1) 层
- 第三次扔 X + (X-1) + (X-2) 层
- …
- 直到 累加的总和 ≥ 100
即： [ X + (X-1) + (X-2) + ... + 1 \geq 100 ] 这是一个 等差数列求和： [ \frac{X(X+1)}{2} \geq 100 ] 解得： [ X \approx 14 ] 即 第一步应从 14 层开始，然后 下一次递增 13 层，再递增 12 层，直到找到临界点。
# 最优解步骤
- 第一步从 14 层开始扔
- 碎了 → 说明临界点在 1~13 层，改为 逐层遍历（最多 13 次）。
- 没碎 → 继续往上跳 13 层（即 14+13=27 层）。
- 第二步从 27 层扔
- 碎了 → 说明临界点在 15~26 层，改为 逐层遍历（最多 12 次）。
- 没碎 → 继续往上跳 12 层（即 27+12=39 层）。
- 重复此过程，直到找到临界点。
- 最坏情况下的扔鸡蛋次数为 14 次。
# 最终结论
- 最少需要 14 次扔鸡蛋，即可 保证在最坏情况下找到临界楼层。
- 核心策略：
- 第一颗鸡蛋用来筛选大致范围，采用递减步长策略。
- 第二颗鸡蛋用于精准查找，在较小范围内逐层检查。
# 相关面试题
- 如果鸡蛋数量增加到 3 个，该如何优化？
- 如果是 1000 层高楼，而鸡蛋仍然是 2 个，该策略如何调整？
- 如果允许鸡蛋被摔碎后还能继续使用，该问题如何简化？
这道题是 经典的动态规划 + 数学推导 题目，考察 最优搜索策略、等差数列求和、最坏情况优化，非常适合面试中测试 逻辑思维与算法设计能力。
