据说这是一道google的面试题. 看似是一个智力题,实际是编程题。
两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。现有座36层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置,可以摔碎两个鸡蛋,要求用最少的测试次数。
1 |
如果你从某一层楼扔下鸡蛋,它没有碎,则这个鸡蛋你可以继续用 |
2 |
如果这个鸡蛋摔碎了,则你可以用来测试的鸡蛋减少一个 |
3 |
所有鸡蛋的质量相同(都会在同一楼层以上摔碎) |
4 |
对于一个鸡蛋,如果其在楼层i扔下的时候摔碎了,对于任何不小于i的楼层,这个鸡蛋都会被摔碎 |
5 |
如果在楼层i扔下的时候没有摔碎,则对于任何不大于i的楼层,这颗鸡蛋也不会摔碎 |
6 |
从第1层扔下,鸡蛋不一定完好,从第36层扔下,鸡蛋也不一定会摔碎。 |
实际上,我们的终极目的是要找出连续的两层楼i,i+1。在楼层i鸡蛋没有摔碎,在楼层i+1鸡蛋碎了,问题的关键之处在于,测试之前,你并不知道鸡蛋会在哪一层摔碎,你需要找到的是一种测试方案,这种测试方案,无论鸡蛋会在哪层被摔碎,都至多只需要m次测试,在所有这些测试方案中,m的值最小。
为什么是两个鸡蛋呢?如果只有一个鸡蛋,我们只能从下往上一层一层的测试。对于2个鸡蛋,比较容易想到的就是使用二分的方法,现在18层测试,如果这颗碎了,则你从第1层,到第17层,依次用第2颗鸡蛋测试。否则继续用两个鸡蛋测试上半部分的楼层,最多需要18次测试,减少了一半。看似是个不错的方法,可惜正确答案是8次。
其实,对于任何连续的M层,这M层在下面或在下面,对于这M层来说需要的测试次数都没有影响。因此,可以把这个问题一般化,考虑n个鸡蛋 k层楼,记为E(n,k)。解决的办法是试着从每一层掉落一个鸡蛋(从1到k)并递归计算需要在最坏的情况下需要的最小测试次数。考虑用程序来穷举所有情况找到答案。
1) 最优子结构
当我们从一个楼层x扔下鸡蛋时,有可能出现两种情况(1)鸡蛋破(2)鸡蛋不破。
1)鸡蛋破,那么我们只需要用剩下的鸡蛋测试 x层以下的楼层; 所以问题简化为x-1层和n-1个鸡蛋
2)如果鸡蛋没有破,那么我们只需要检查比x较高的楼层; 所以问题简化为 k-x 和n个鸡蛋。
最优子结构可以表示为:
1 |
k ==> 楼层数 |
2 |
n ==> 鸡蛋数 |
3 |
eggDrop(n, k) ==>最少需要的测试次数(考虑所有情况)
|
4 |
eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)):
|
5 |
x 属于 {1, 2, ..., k}}
|
下面用递归的方法解决这个问题:
01 |
# include <stdio.h> |
02 |
# include <limits.h> |
03 |
04 |
int max( int a, int b) { return (a > b)? a: b; }
|
05 |
06 |
int eggDrop( int n, int k)
|
07 |
{ |
08 |
// 基本情况
|
09 |
if (k == 1 || k == 0)
|
10 |
return k;
|
11 |
12 |
//如果只有一个鸡蛋,最坏的情况下需要k测试
|
13 |
if (n == 1)
|
14 |
return k;
|
15 |
16 |
int min = INT_MAX, x, res;
|
17 |
18 |
// 考虑从第1层到底k层扔下鸡蛋的所有情况 的最小结果
|
19 |
for (x = 1; x <= k; x++)
|
20 |
{
|
21 |
res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));
|
22 |
if (res < min)
|
23 |
min = res;
|
24 |
}
|
25 |
return min + 1;
|
26 |
} |
27 |
28 |
/* 测试 */ |
29 |
int main()
|
30 |
{ |
31 |
int n = 2, k = 10;
|
32 |
printf ( "\nMinimum number of trials in worst case with %d eggs and "
|
33 |
"%d floors is %d \n" , n, k, eggDrop(n, k));
|
34 |
return 0;
|
35 |
} |
上面的程序问题是复杂度太大 O(2^k)。如果k=36的话,基本是跑不出结果。
重叠子问题
因为上面的程序重复计算了很多子问题。以E(2,4)为例:
01 |
E(2,4)
|
02 |
|
|
03 |
-------------------------------------
|
04 |
| | | |
|
05 |
| | | |
|
06 |
x=1/\ x=2/\ x=3/ \ x=4/ \
|
07 |
/ \ / \ .... ....
|
08 |
/ \ / \
|
09 |
E(1,0) E(2,3) E(1,1) E(2,2)
|
10 |
/\ /\... / \
|
11 |
x=1/ \ .....
|
12 |
/ \
|
13 |
E(1,0) E(2,2)
|
14 |
/ \
|
15 |
......
|
16 |
对于2个鸡蛋,4层楼 部分递归 |
因此完全可以用动态规划解决。
01 |
# include <stdio.h> |
02 |
# include <limits.h> |
03 |
int max( int a, int b) { return (a > b)? a: b; }
|
04 |
int eggDrop( int n, int k)
|
05 |
{ |
06 |
/* eggFloor[i][j] 表示对于 i个鸡蛋 j 层楼,需要的最少测试次数 */
|
07 |
int eggFloor[n+1][k+1];
|
08 |
int res;
|
09 |
int i, j, x;
|
10 |
// 初始化
|
11 |
for (i = 1; i <= n; i++)
|
12 |
{
|
13 |
eggFloor[i][1] = 1;
|
14 |
eggFloor[i][0] = 0;
|
15 |
}
|
16 |
17 |
//只有一个鸡蛋,没得优化,需要j次
|
18 |
for (j = 1; j <= k; j++)
|
19 |
eggFloor[1][j] = j;
|
20 |
21 |
// 最优子结构的递推
|
22 |
for (i = 2; i <= n; i++)
|
23 |
{
|
24 |
for (j = 2; j <= k; j++)
|
25 |
{
|
26 |
eggFloor[i][j] = INT_MAX;
|
27 |
for (x = 1; x <= j; x++)
|
28 |
{
|
29 |
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
|
30 |
if (res < eggFloor[i][j])
|
31 |
eggFloor[i][j] = res;
|
32 |
}
|
33 |
}
|
34 |
}
|
35 |
return eggFloor[n][k];
|
36 |
} |
37 |
38 |
/* 测试*/ |
39 |
int main()
|
40 |
{ |
41 |
int n = 2, k = 36;
|
42 |
printf ( "\nMinimum number of trials in worst case with %d eggs and "
|
43 |
"%d floors is %d \n" , n, k, eggDrop(n, k));
|
44 |
return 0;
|
45 |
} |
参考:http://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/
相关推荐
C#,动态规划(DP)丢鸡蛋问题(Egg Dropping Puzzle)的三种算法与源代码 动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等...
Dropping-Thunder:Dropping Thunders TD模拟器
JavaScript
textlint-rule-no-dropping-i这是一个检测丢失单词的规则。 are我们正在发展。 developing我在发展。安装npm install @textlint-ja/textlint-rule-no-dropping-i用法将@textlint-ja/textlint-rule-no-dropping-i ....
语言:English通过空中景观放下苹果,绝对不会错过重要的掉苹果活动,例如小睡放苹果可以帮助您与商店的预购开店保持最新并保持个人时间表...使用Airscape的Dropping Apple绝不会错过重要的Apple Droping事件,例如小睡
BallDropping是一个会让人上瘾的噪音制造器,如果平时无聊的时候也可以当作小游戏来玩。很多小球从天而降,根据碰击角度、速度的不同,掉在鼠标划的线上会发出大珠小珠落玉盘的声音。 <br>你可不要小看了...
gps测试,jieshougps数据存储数据库,检测发送命令地
人が来れないんです安装npm install textlint-rule-no-dropping-the-ra用法将“ no-drop-the-ra” .textlintrc { " rules " : { " no-dropping-the-ra " : true }}贡献叉吧! 创建功能分支: git checkout -b my-new...
Call dropping performance analysis of the eNB-first channel access policy in LTE-Advanced relay networks
偏好(或批准)投票表以选择选举竞赛的优胜者或排名决定。 使用丢弃成本最小化来组合两种Condorcet方法:克隆Schwartz顺序丢弃和Tideman的排名对。
This paper is concerned with the distributed fusion estimation in sensor networks where local estimates are sent to a fusion centre for fusion estimation, with random delays and packet dropouts....
TCL script to find wireless packet dropping nodes2609002STC12C5A60S2+2.4TFT+DS1302+DS18B20+GPS+FM 自动校时收音机电子钟 STC12C5A60S2+2.4TFT+DS1302+DS18B20+GPS+FM 自动校时收音机电子钟 捣鼓了许久
当VirtualBox 2.1.4升级到2.2.0以后,突然发现虚拟的系统无法使用主机的网络上网了,google了一下,发现很多人碰到这个问题,但没有解决办法,甚至有人认为是VirtualBox的Bug,其实不然。 经过研究发现,2.2.0缺省...
中文版文档 Emoji Rain Hey, it's raining emoji! This is a really simple and funny animation for Android. You could find similar ...How many emojis will dropping in each flow, default 6 duration
2D滴入式软体 自学项目我一直对计算机模拟物理世界充满热情。 最近,我试图在二维中模拟与刚体碰撞时的软体变形。 该程序仍未完成,但是现在我将其留在这里,过一会儿我将返回它。
35个用户在1000time slot中,以0.2的概率产生packets
抛球游戏 827游戏的第一款游戏
Qt Serialbus 报错 dropping older ADU fragments due to larger than 3.5 char 用qt打开此项目编译安装即可解决
dropping probabilities, i.e., the packet dropping probability due to energy depletion and that due to channel error. Numerical examples are provided to illustrate the theoretical findings, and new ...
Delphi written try dropping bombs on game