漫画：有趣的扔鸡蛋问题

逃离我推掉我的手 2022-04-24 08:16 237阅读 0赞

> 本文转载自程序员小灰

![1240][]

![1240 1][]

**—————  第二天  —————**

![1240 2][]

![1240 3][]

![1240 4][]

**题目：扔鸡蛋问题**

有**2**个鸡蛋，从**100**层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。

**问：如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？**

![1240 5][]

举个栗子，最笨的测试方法是什么样呢？

把其中一个鸡蛋从第1层开始往下扔。

如果在第1层没碎，换到第2层扔

如果在第2层没碎，换到第3层扔

…

如果第59层没碎，换到第60层扔

如果第60层碎了，说明不会摔碎的临界点是第59层

在最坏情况下，这个方法需要扔100次。

![1240 6][]

![1240 7][]

**方法一：二分法**

采用类似于二分查找的方法，把鸡蛋从一半楼层（50层）往下扔。

如果第一枚鸡蛋在50层碎了，第二枚鸡蛋就从第1层开始扔，一层一层增长，一直扔到第49层。

如果第一枚鸡蛋在50层没碎了，则继续使用二分法，在剩余楼层的一半（75层）往下扔…

这个方法在最坏情况下，需要尝试50次。

![1240 8][]

![1240 9][]

![1240 10][]

![1240 11][]

**方法二：平方根法**

如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数尽可能均衡呢？

很简单，做一个平方根运算，100的平方根是10。

因此，我们尝试每10层扔一次，第一次从10层扔，第二次从20层扔，第三次从30层…一直扔到100层。

这样的最好情况是在第10层碎掉，尝试次数为 1 + 9 = 10次。

最坏的情况是在第100层碎掉，尝试次数为 10 + 9 = 19次。

![1240 12][]

不过，这里有一个小小的优化点，我们可以从15层开始扔，接下来从25层、35层扔…一直到95层。

这样最坏情况是在第95层碎掉，尝试次数为 9 + 9 = 18次。

![1240 13][]

![1240 14][]

![1240 15][]

————————————

![1240 16][]

![1240 17][]

![1240 18][]

![1240 19][]

![1240 20][]

![1240 21][]

![1240 22][]

![1240 23][]

![1240 24][]

![1240 25][]

![1240 26][]

假设最优的尝试次数的x次，为什么第一次扔就要选择第x层呢？

这里的解释会有些烧脑，请小伙伴们坐稳扶好：

**假设第一次扔在第x+1层：**

如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x层。

这样一来，我们总共尝试了x+1次，和假设尝试x次相悖。由此可见，第一次扔的楼层必须小于x+1层。

**假设第一次扔在第x-1层：**

如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-2层。

这样一来，我们总共尝试了x-2+1 = x-1次，虽然没有超出假设次数，但似乎有些过于保守。

**假设第一次扔在第x层：**

如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-1层。

这样一来，我们总共尝试了x-1+1 = x次，刚刚好没有超出假设次数。

**因此，要想尽量楼层跨度大一些，又要保证不超过假设的尝试次数x，那么第一次扔鸡蛋的最优选择就是第x层。**

![1240 27][]

![1240 28][]

![1240 29][]

![1240 30][]

![1240 31][]

![1240 32][]

![1240 33][]

**方法三：解方程法**

**x + (x-1) + (x-2) + … + 1 = 100**

这个方程式不难理解：

左边的多项式是各次扔鸡蛋的楼层跨度之和。由于假设尝试x次，所以这个多项式共有x项。

右边是总的楼层数100。

下面我们来解这个方程：

x + (x-1) + (x-2) + … + 1 = 100  转化为

(x+1)\*x/2 = 100

最终x向上取整，得到 **x = 14**

因此，最优解在最坏情况的尝试次数是**14次**，第一次扔鸡蛋的楼层也是**14层**。

最后，让我们把第一个鸡蛋没碎的情况下，所尝试的楼层数完整列举出来：

**14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100**

举个栗子验证下：

假如鸡蛋不会碎的临界点是65层，那么第一个鸡蛋扔出的楼层是14，27，50，60，69。这时候啪的一声碎了。

第二个鸡蛋继续，从61层开始，61，62，63，64，65，66，啪的一声碎了。

因此得到不会碎的临界点65层，总尝试次数是 6 + 6 = 12 < 14 。

![1240 34][]

![1240 35][]

![image][]

![1240 36][]

![1240 37][]

![1240 38][]

隔壁寝室一块打羽毛球的同学在tplink二面中曾遇到过这道题，不过屏幕前的同学们不用担心，相必看到这里的同学应该彻底明白这道题是怎么一回事了。

更多关于本文的**吐槽和讨论，评论中**见哦\*\*~\*\*

—————END—————

--------------------

扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：公众号后台回复“**csdn**”即可免费领取【csdn】和【百度文库】下载服务；公众号后台回复“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**  
![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240 39]

**推荐阅读**  
[【腾讯面试题】微信抢红包算法：源码+图+视频][Link 1]

[1240]: /images/20220217/e58ce1fb432e49c0a56d10adad318072.png
[1240 1]: /images/20220217/9b0aaf313e144cac909397e100e97598.png
[1240 2]: /images/20220217/66d96dbdfa3b450bb5704818d6008bd7.png
[1240 3]: /images/20220217/a2319505b44d432aa39c111b34a3be99.png
[1240 4]: /images/20220217/cb47bcfc82924a7a84e335ac907748df.png
[1240 5]: /images/20220217/ea67b0cccc464962868c736b57846fea.png
[1240 6]: /images/20220217/8476c6750afb421395aa2900d5fe8a8d.png
[1240 7]: /images/20220217/12c6465e6948462c8fb761aced78aa08.png
[1240 8]: /images/20220217/3fab4a517d2348af846d0bf5e4b358ef.png
[1240 9]: /images/20220217/b1e411fffa464b21a8e369b704f8deca.png
[1240 10]: /images/20220217/c85519bf959f476fa97f82b999f91f8f.png
[1240 11]: /images/20220217/0d37ff82d6ce440ca03313135be6f08c.png
[1240 12]: /images/20220217/df9ee0b60a1b4d01afc7bc010738191d.png
[1240 13]: /images/20220217/af1827fe1ca64eb480aee060c5e47649.png
[1240 14]: /images/20220217/c9cc099e4580438282077c6634e6553d.png
[1240 15]: /images/20220217/7de79d3efb9c48dc8208e769c5334417.png
[1240 16]: /images/20220217/bd680f9425b741e490aa463539e70e6d.png
[1240 17]: /images/20220217/4389049ff752466f9a04cce3a5187bf9.png
[1240 18]: /images/20220217/eaa176710a9743bcafbb90a4437e8a88.png
[1240 19]: /images/20220217/3e5a17f36f2241c4940148d8c452325b.png
[1240 20]: /images/20220217/ac8d0e7f51cb48208b7814cc5c98a6eb.png
[1240 21]: /images/20220217/2b1595db51934e5ea1d54f420596e83b.png
[1240 22]: /images/20220217/306b00b3d1ae4ef5809a94cd4ae20c5f.png
[1240 23]: /images/20220217/e67fe053ebf947779811ab44d340d295.png
[1240 24]: /images/20220217/385aef61b279476a8dc378b3e974f070.png
[1240 25]: /images/20220217/a987e7dadfdc45618f6e88872e8280b2.png
[1240 26]: /images/20220217/d678798ac53342d095cff63513e37bde.png
[1240 27]: /images/20220217/f3417c693ba84a7ca86e427829d8b8af.png
[1240 28]: /images/20220217/8e42f45f564c4fe6ac232ece8c4ae251.png
[1240 29]: /images/20220217/999e28ac95934d64a4d8cfc1cc21b664.png
[1240 30]: /images/20220217/bde542766380415da54a88a273cc874b.png
[1240 31]: /images/20220217/1ed3fb6e20ba403f856972f3240dbd5a.png
[1240 32]: /images/20220217/764d865c457e42c19790b4d7e022895d.png
[1240 33]: /images/20220217/9ab16adae1f449c4911dc5c9b68c4e3c.png
[1240 34]: /images/20220217/28d1f60d6fdb4a7e844e46b615318d68.png
[1240 35]: /images/20220217/1d55814f45514e97b06ff6afa23d9ec6.png
[image]: /images/20220217/dc0120103b1a48ed8ba574abf29ad157.png
[1240 36]: /images/20220217/a2a0d12e33cb46eca56e55a4eb24e8d7.png
[1240 37]: /images/20220217/f50981f2190f4ef58ffd2df91432fa8f.png
[1240 38]: /images/20220217/c1e63efabcf14056b0486a0129cd9cac.png
[1240 39]: /images/20220217/9fb977b0544142a58778870353ce9275.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247484559&idx=1&sn=d2ac7c048366e11b8e8c135b1e472a7d&chksm=eb51277bdc26ae6d61354ba98f0a648f691db0cda6d379d97128212d5224bd36826b88849642&scene=21#wechat_redirect