扔鸡蛋问题

问题

仅给出两个鸡蛋, 尝试在 100 层的建筑物中抛出鸡蛋,在最坏的情况下找出鸡蛋能承受的最大楼层。

解题

  1. 尝试从第一层开始测试,最坏 100 次;
  2. 尝试从中间层(50)开始测试,如果碎了,再拿出第二个鸡蛋从第一次层开始测试,合计 51 次;如果没碎,第一个鸡蛋捡起来, 从 75层开始测试,然后往复下去

思路大致如上,100 层很难算, 如果总层数只有 0,1,2,3,4… 层,最坏需要多少次基本上可以手算出来, 结果如下

层数 最坏测试数
0 0
1 1
2 2
3 2
4 3
5 3

然后,要在 6 层楼房找出最大承受高度,
1. 第一枚鸡蛋可以从第一层抛出,如果碎了,最大承受楼层 0, 没碎,意味着我还有两个完整的鸡蛋可以在剩下 5 层中寻找结果,五层,见上表,最少需要 3 次,合计意味最坏 4 次
2. 第一枚鸡蛋从第二层抛出,如果碎了,另一枚鸡蛋从第一层开始扔,直到碎了为止,最坏 2 次, 没碎,意味着我还有两个完整的鸡蛋可以在剩下 4 层中寻找结果,四层,见上表,最少需要 3 次,合计最坏 4 次
3. 第一枚鸡蛋从第三层抛出…
4. 第一枚鸡蛋从第四层抛出…
5. 第一枚鸡蛋从第五层抛出…
6. 第一枚鸡蛋从第六层抛出…
7. 第一枚鸡蛋从第七层抛出…
8. 第一枚鸡蛋从第八层抛出, 合计最坏 8 次

其实结果已经出来了,6 层 楼中最少测试数即上述八种可能中最优的一个
f{n} = min{ (max{(1), f{n-1})), (max{(2), f{n-2})), (max((3), f{n-3})), …}

cpp 代码

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部