Egg Dropping Puzzle
The following is a description of the instance of this famous puzzle involving n=2 eggs and a building with k=36 floors.
Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing. We make a few assumptions:
…..An egg that survives a fall can be used again.
…..A broken egg must be discarded.
…..The effect of a fall is the same for all eggs.
…..If an egg breaks when dropped, then it would break if dropped from a higher floor.
…..If an egg survives a fall then it would survive a shorter fall.
…..It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor do not cause an egg to break.
If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from the second floor window. Continue upward until it
breaks. In the worst case, this method may require 36 droppings. Suppose 2 eggs are available. What is the least number of egg-droppings that is guaranteed to work in all cases?
The problem is not actually to find the critical floor, but merely to decide floors from which eggs should be dropped so that total number of trials are minimized.
Source:Wiki for Dynamic Programming
In this post, we will discuss solution to a general problem with n eggs and k floors. The solution is to try dropping an egg from every floor (from 1 to k) and recursively calculate the minimum number of droppings needed in worst case. The floor which gives
the minimum value in worst case is going to be part of the solution.
In the following solutions, we return the minimum number of trails in worst case; these solutions can be easily modified to print floor numbers of every trials also.
这道题有点拗口,就是要知道基本情况:
1 有0楼的时候,就不需要实验了,返回0
2 有1楼的时候,只需要试验一次就可以了
3 有一个蛋的时候,最坏情况就需要把所有楼都试验一次
在这三种基本情况假设下去想这个问题就容易多了
分两个情况:
1 碎蛋:往下走
2 没碎蛋:往上走
无论往上走和往下走都可以截去下面和上面的楼层不考虑
不过注意的就是,碎蛋,那么蛋蛋减小1了,没碎蛋那么蛋蛋不用减小。
理解透彻,那么优化动态规划法就可以写出来了:
下面是GeeksforGeeks的动态规划法和递归法求解,和我写的eggDropDPSaveSpace版本,只使用了2个一维表。只需要记住前一行的信息就能填写下一行的信息,那么就可以只用两个一维表。甚至一个一维表。
递归法很慢,楼层多了就直接算不出来。
/* Function to get minimum number of trails needed in worst
case with n eggs and k floors */
int eggDropDP1(int n, int k)
{
/* A 2D table where entery eggFloor[i][j] will represent minimum
number of trials needed for i eggs and j floors. */
vector<vector<int> > eggFloor(n+1, vector<int>(k+1));
int res;
int i, j, x;
// We need one trial for one floor and0 trials for 0 floors
for (i = 1; i <= n; i++)
{
eggFloor[i][1] = 1;
eggFloor[i][0] = 0;
}
// We always need j trials for one egg and j floors.
for (j = 1; j <= k; j++)
eggFloor[1][j] = j;
// Fill rest of the entries in table using optimal substructure
// property
for (i = 2; i <= n; i++)
{
for (j = 2; j <= k; j++)
{
eggFloor[i][j] = INT_MAX;
for (x = 1; x <= j; x++)
{
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
if (res < eggFloor[i][j])
eggFloor[i][j] = res;
}
}
}
// eggFloor[n][k] holds the result
return eggFloor[n][k];
}
//n eggs and k floors
int eggDropDPSaveSpace(int n, int k)
{
//特殊处理0或1层楼的时候,和只有一个蛋的时候
if (k <= 1 || n == 1) return k;
//i eggs and j floors.
vector<vector<int> > eggFloor(2, vector<int>(k+1));
bool flag = false;
eggFloor[!flag][1] = 1;
eggFloor[flag][1] = 1;
for (int j = 2; j <= k; j++)
eggFloor[!flag][j] = j;
for (int i = 2; i <= n; i++)
{
for (int j = 2; j <= k; j++)
{
eggFloor[flag][j] = INT_MAX;
for (int x = 1; x <= j; x++)
{
int res = 1 + max(eggFloor[!flag][x-1], eggFloor[flag][j-x]);
if (res < eggFloor[flag][j])
eggFloor[flag][j] = res;
}
}
flag = !flag;
}
return eggFloor[!flag][k];
}
/* Function to get minimum number of trails needed in worst
case with n eggs and k floors */
int eggDrop(int n, int k)
{
// If there are no floors, then no trials needed. OR if there is
// one floor, one trial needed.
if (k == 1 || k == 0)
return k;
// We need k trials for one egg and k floors
if (n == 1)
return k;
int min = INT_MAX, x, res;
// Consider all droppings from 1st floor to kth floor and
// return the minimum of these values plus 1.
for (x = 1; x <= k; x++)
{
res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));
if (res < min)
min = res;
}
return min + 1;
}
int main()
{
int n = 18, k = 136;
//printf ("\nMinimum number of trials in worst case with %d eggs and "
// "%d floors is %d \n", n, k, eggDrop(n, k));
printf ("\nDP1:Minimum number of trials in worst case with %d eggs and "
"%d floors is %d \n", n, k, eggDropDP1(n, k));
printf ("\nDP:Minimum number of trials in worst case with %d eggs and "
"%d floors is %d \n", n, k, eggDropDPSaveSpace(n, k));
system("pause");
return 0;
}
分享到:
相关推荐
geeks-for-geeks-solutions:有关Geeks-for-Geeks的问题的解决方案。解决方案可用于C ++
2022最新版:GEEKS V1.0.10主题:在线学习市场WordPress主题.rar
Geeks2TheRescue:使用MERN的Web App,旨在连接雄心勃勃的开发人员
geeks_algorithms 极客算法编码问题
带有React JS的WebApp样板 要求: 确保您使用的是节点版本10 安装软件包: $ npm install 创建一个.env文件: $ cp .env.example .env 开始编码! 以及具有实时重新加载功能的webpack开发服务器(适用于Windows...
夏季极客提交 这个Web应用程序被配制成在Innnovaccer SDE实习分配的一部分,使用的NodeJS,MongoDB的,NodeMailer的电子邮件和Nexmo的手机信息,根据。 预习 报到表格 结帐电子邮件 使用的技术 ...
欢迎来到4Geeks学院 <\编码时间>内容关于。创始人。团队。奖项。校友关于4Geeks是一家大公司,感觉就像一家小公司;每个人都可以访问,我们喜欢与人接触,我们相信量身定制的教育,而不会离开您的工作,并且100%...
:sparkles: gloomhaven-geeks :sparkles: 这是一个使用Git作为的网站。 它是在不到一分钟的时间内使用创建的。 您可以像这样,或探索一些变体。 如何不同: :artist_palette: 看 :pencil: 内容管理系统 :gear: 静态...
geeks for geeks上的资源,大家下载下,我攒点几分,呵呵。
极客换极客 Geeks-For-Geeks 实习文章 使用 scapy 嗅探数据包 - 使用 Javascript 和 DOM 创建棋盘模式 - 如何将链接从一个 iframe 加载到另一个 iframe -
Geeks for Geeks的DSA练习: :
本题的难度并不在最短路径本身这个算法,而是在于堆的操作: 1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好...
Geeks3D Furmark(OpenGL显卡基准测试工具)V1.17.1 中文官方版
Hardware Hacking Projects for Geeks 英文chm 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
geek极客们都用什么神器,这篇文章给了你答案。
Mac OS X For Unix Geeks 2003
当你准备面试 Java 编程工作时,考虑将被问到的问题非常重要。这些面试问题可能将因许多因素而异,包括公司类型、职位级别以及你面试的公司的经营时间。考虑这么多因素,你如何准备回答这些问题?通过考虑展示你的 ...
Ubuntu for Non-Geeks (Fourth Edition)
Cooking.for.Geeks, hope all programer have good food
A HashMap for Geeks and normal programmers.