【每日一道智力题】之高楼扔只因蛋

港控/mmm° 2024-03-29 16:14 85阅读 0赞

**目录**

### 前言： ###

### 题目： ###

### 解析： ###

### 总结： ###

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

> 博客主页：[张栩睿的博客主页][Link 1]
> 
> 欢迎关注：点赞+收藏+留言
> 
> 系列专栏：[c语言学习][c]
> 
>  **家人们写博客真的很花时间的，你们的点赞和关注对我真的很重要，希望各位路过的朋友们能多多点赞并关注我，我会随时互关的，欢迎你们的私信提问，也期待你们的转发！**
> 
>  **希望大家*****关注我，*****你们将会看到更多精彩的内容！！！**

## 前言： ##

我是纯路人，这个标题单纯是为了让大家和坤坤一起好好学习！

## 题目： ##

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

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

> 首先要说明的是这道题你要是一上来就说出正确答案，那说明你的智商不是超过160就是你做过这题。
> 
> 所以建议你循序渐进的回答，一上来就说最优解可能结果不会让你和面试官满意。

## 解析：(正经解答） ##

**1.暴力法**

举个栗子，最笨的测试方法，是什么样的呢？把其中一个鸡蛋，从第1层开始往下扔。如果在第1层没碎，换到第2层扔；如果在第2层没碎，换到第3层扔.......如果第59层没碎，换到第60层扔；如果第60层碎了，说明不会摔碎的临界点是第59层。

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

**2. 二分法**

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

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

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

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

**3.均匀法**

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

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

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

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

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

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

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

**4.最优解法**

最优解法是反向思考的经典：如果最优解法在最坏情况下需要扔X次，那第一次在第几层扔最好呢？

答案是：从X层扔

假设最优的尝试次数的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层。

那么如果没有摔碎，第二次你只剩下x-1次机会，按照上面的说法，你第二次尝试的位置必然是X+（X-1）；因为这个样子的话，最坏的情况也会是x次找到，因为会从x+1开始找，找到2\*X-1的位置，此时最坏也是2+x+1-2\*x-1=x。

以此类推我们可得：

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 。

**下面是我个人的理解：**

这个似乎更像是优化版的均匀法，因为我们在均匀以后，不管在哪个区间，找最坏的情况都是x种，而均匀法让你第二次尝试不超过10，但是第一次的位置无法保证（最多要9次，最好一次），他所在的楼层区间的最坏情况都不太一样。而最优解法由于每多一次尝试，楼层间隔就-1，最终使得第一次与第二次的和（既每个区间的最差情况）都是完全均匀的。

## 总结： ##

今天的每日一道智力题让我们学会了许多方法，如：暴力枚举法，二分法，均匀法，逆向思维法。最优解的核心思路是逆向思考，因为即使理解了需要两次的和均匀也很难得到第一次要在哪层楼扔。一旦理解了这种方法，多少层楼你都不会怕啦。这就是今天的每日一题，希望大佬们可以点赞收藏！您的支持是我创造的动力！最后，其实我是真爱粉!

[Link 1]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482