扔鸡蛋问题

发表于 | 分类于 | | 阅读次数:

一、问题描述

两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。（参见[两个鸡蛋–一道Google面试题]）

最早在公众号上遇到过，后来腾讯笔试好像也遇到过发现这个题还是很经典的。

二、解题思路

1、数学方法

一种想法是第一个鸡蛋折半搜索，如100层的楼，先从50层扔下去，如果碎了则第二个鸡蛋在1~49层楼中自底向上线性搜索；如果没碎则第一个鸡蛋再从75层扔。如果这次碎了则第二个鸡蛋在51~74层楼中自底向上线性搜索；如果还没碎则第一个鸡蛋再从88层扔，依此类推。这种方法不是最优，因为最坏情况下安全位置恰好是49层，需要尝试50次。

基于这个最坏的情况进行改进

  • 那么我假设最坏情况下会尝试x次。
  • 则第一个鸡蛋第一次从第x层扔（不管碎没碎，还有x-1次尝试机会）。
    • 如果碎了，则第二个鸡蛋在1～x-1层中线性搜索，最多x-1次；
    • 如果没碎，则第一个鸡蛋第二次从x+(x-1)层扔（现在还剩x-2次尝试机会）。
  • 第二次尝试也是一样。
    • 如果这次碎了，则第二个鸡蛋在x+1～x+(x-1)-1层中线性搜索，最多x-2次；
    • 如果还没碎第一个鸡蛋再从x+(x-1)+(x-2)层扔。
  • 依此类推。x次尝试所能确定的最高楼层数为x+(x-1)+(x-2)+…+1=x(x+1)/2。

如果楼层为100的话，只要保证x(x+1)/2>=100即可，即x>=14，最少进行14次。

具体地说，100层的楼，第一次从14层开始扔。碎了好说，从第1层开始试。不碎的话还有13次机会，再从14+13=27层开始扔。依此类推，各次尝试的楼层依次为

1
2
3
4
5
6
14
27 = 14 + 13
39 = 27 + 12 
... 
99 = 95 + 4
100

2、DP

上面的解法更直观便于理解，但是从动态规划的角度可以更抽象的描述这个问题。

假设f[n]表示从n层楼找到摔鸡蛋不碎安全位置的最少判断次数。假设第一个鸡蛋第一次从第i层扔下，如果碎了，就剩一个鸡蛋，为确定下面楼层中的安全位置，必须从第一层挨着试，还需要i-1次；如果不碎的话，上面还有n-i层，剩下两个鸡蛋，还需要f[n-i]次（子问题，实体n层楼的上n-i层需要的最少判断次数和实体n-i层楼需要的最少判断次数其实是一样的）。因此，最坏情况下还需要判断max(i-1,f[n-i])次。

1
2
3
状态转移方程：f[n]=min{1+max(i-1,f[n-i]) | i=1..n} 

初始条件: f[0]=0, 或f[1]=1

根据状态转移方程可以写出程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static int f(int n, int[] dp){
	if(n<2){
		return n;
	}
	if(dp[n]>0){
		return dp[n];
	}
	int min=Integer.MAX_VALUE;
	for(int i=1; i<=n; i++){
		min=Math.min(min, 1+Math.max(i-1, f(n-i, dp)));
	}
	dp[n]=min;
	return min;
}

public static int eggThrow(int n){
	int[] dp=new int[n+1];
	return f(n, dp);
}

输入100的话输出和上面一样也是14。

3、扩展

现在把问题进行扩展，n层楼，m个鸡蛋。那么DP就是一个二维的数组了

假设f[n,m]表示n层楼、m个鸡蛋时找到摔鸡蛋不碎的最少判断次数。则一个鸡蛋从第i层扔下，如果碎了，还剩m-1个鸡蛋，为确定下面楼层中的安全位置，还需要f[i-1,m-1]次（子问题）；不碎的话，上面还有n-i层，还需要f[n-i,m]次（子问题，实体n层楼的上n-i层需要的最少判断次数和实体n-i层楼需要的最少判断次数其实是一样的）。

1
2
状态转移方程：f[n,m] = min{ 1+max(f[i-1,m-1], f[n-i,m]) | i＝1..n } 
初始条件：f[i,0]=0（或f[i,1]=i），对所有i

程序没有写，但是如果把输出列出来会很有意思：

1
2
3
4
1个鸡蛋：1+1+1+1+1+...
2个鸡蛋：1+2+3+4+5+...（之间的差为1,1,1,1,1,1,...）
3个鸡蛋：1+2+4+7+11+16+...（之间的差为1,2,3,4,5...）
4个鸡蛋：1+2+4+8+15+26+...（之间的差为1,2,4,7,11...）

上面这个序列的逆序，就是最后剩余的尝试次数。

关于这个问题有专门的论文进行数学分析。

三、参考地址

http://blog.csdn.net/joylnwang/article/details/6769160

http://www.cnblogs.com/ltang/archive/2010/11/23/1885791.html