算法第四版扔鸡蛋问题

太过爱你忘了你带给我的痛 2022-06-07 06:28 230阅读 0赞

本题来源于算法第四版1.4.25、1.4.26。

同时好像记得看过的腾讯面经里也问到过类似题目，因此觉得有必要仔细做一下。

题目如下：

> 一幢 100 层的大楼，给你两枚鸡蛋。假设，在第 n 层扔下鸡蛋，鸡蛋不碎，那么从第 n-1 层扔鸡蛋，鸡蛋也不会碎。两个鸡蛋一模一样，不碎的话可以扔无数次。目标是利用这两个鸡蛋找出临界楼层 t , 使得鸡蛋从 t 层扔下不会碎， 从 t+1 层扔下会碎。

> 现要求回答， 最少需要多少次尝试， 才能保证在最坏的情况下，找到楼层 t ， 且需要给出尝试的策略。

题目详解：

> 拿到题目最先考虑到的应该是二分法，但发现二分不不好用，理由如下：

*  如果初始你有1个鸡蛋，你并不敢直接二分从50层楼开始扔，因为万一碎了就没鸡蛋了。因此你只能够从第一层开始一层一层扔。此时的鸡蛋数量并不足以让你去做策略，说明楼层t = 尝试次数t

*  当我有两个鸡蛋，我第一个鸡蛋可以从50层开始扔，如果没碎，我可以继续二分，将它从25层开始扔；但如果碎了，那么我剩下的一个鸡蛋便同第一种情况一样，只能从第一层开始一层一层扔，此时最坏的情况是楼层数t = 49，那么我共需要50次尝试。可见，当我有两个鸡蛋时，我只能对一个鸡蛋采取二分策略，剩下的一个鸡蛋只能老老实实的从头扔。

*  鸡蛋更多时二分策略也是如此。

> 由此可见，对于扔鸡蛋，由于存在鸡蛋碎的问题，二分策略并不是好的策略。
> 
> 但通过二分法我们能够发现两种鸡蛋的特性，第一个鸡蛋适合大胆尝试，在楼层间跳跃前进，因为我希望通过它获得一个尽可能小的楼层区间，而剩下的一个鸡蛋则应采取保守策略，一层层楼前进，最终找到临界楼层t

*  1.数学反推

>  *  题目要求的策略可以保证在最坏情况下至多需要扔x次鸡蛋就可以找出临界楼层
>  *  此时可以将问题转化为：如果只允许扔x次鸡蛋能确定的最高的楼层是多少。
>  *  问题进而转化为：第一次最高能扔多少层？答案为x层，因为如果第一次就碎掉，那么考虑到最坏情况即楼层t = x - 1，那么我们第一次最高只能扔x - 1层
>  *  而由于第一次从x层扔下时， 我们已经用掉了一次尝试机会， 此时只能再尝试x - 1次。 这样我们可以第二次尝试的楼层数可以向上增加x - 1层， 即为 x + (x-1)。
>  *  而第三次就只能为 x-3, 第四次就只能为 x-4, …….., 最后一次为1。
>  *  此时我们可以得出，如果只能尝试x次， 我们能检测的最高楼层为 x+(x - 1)+(x - 2)+(x - 3)+......1 = (x\*(x + 1)) / 2。

> 此时答案就出 则有
> 
> > x\*(x+1)/2 >=100, 解出来 x >= 14

*  2.动态规划

*   *  现在考虑动态规划解法， 根据上面的分析，其实可以发现， 第一次尝试的楼层， 会对最终的结果产生直接的影响。 现在 设 f(m, n) 为m个鸡蛋， n层楼时， 在最坏情况下的最少尝试次数。 如果第一次尝试从x层楼开始， 则f(m, n) = 1 + max(f(m - 1, n - 1), f(m, n - x))
     *  f(m - 1, n - 1)为第一次鸡蛋被摔碎
     *  f(m, n - x)为第一次鸡蛋没碎

> > 编写程序求解
> > 
> >     #include <iostream>
> >     using namespace std;
> >     #define max(a, b) ((a > b) ? a : b)
> >     //throw egg
> >     class ThrowEgg
> >     {
> >     	int eggs;
> >     	int floors;
> >     	int table[3][101];
> >     public:
> >     	ThrowEgg();
> >     	void result();
> >     };
> >     ThrowEgg::ThrowEgg()
> >     {
> >     	eggs = 2;
> >     	floors = 100;
> >     	int table[3][101] = {0,0};
> >     }
> >     
> >     
> >     void ThrowEgg::result()
> >     {
> >     	
> >     	for (int i = 0; i <= eggs; i++)
> >     	{
> >     		table[i][0] = 0;
> >     		table[i][1] = 1;
> >     	}
> >     	for (int j = 0; j <= floors; j++)
> >     		table[1][j] = j;
> >     	for(int i = 2; i <= eggs; i++)
> >         {
> >     		for (int j = 2; j <= floors; j++) 
> >     		{
> >     			table[i][j] = 100000;  
> >                 for (int floorTriedFirst = 1; floorTriedFirst <= j; floorTriedFirst++) 
> >     			{
> >     				int res = 1 + max(table[i-1][floorTriedFirst-1], table[i][j-floorTriedFirst]);  
> >     				if(res < table[i][j])
> >     				{
> >     					table[i][j] = res;
> >                     }
> >     			}
> >     		}
> >     	}
> >     }
> >     
> >     void main()
> >     {
> >     	ThrowEgg ex1;
> >     	ex1.result();
> >     }
> > 
> >   
> >

*x*\+(*x*−1)\+(*x*−2)\+(*x*−3)....\+1=(*x*∗(*x*\+1))/blog参考：[http://blog.csdn.net/lengxiao1993/article/details/52551492][http_blog.csdn.net_lengxiao1993_article_details_52551492]

[http_blog.csdn.net_lengxiao1993_article_details_52551492]: http://blog.csdn.net/lengxiao1993/article/details/52551492