我要招人

去企业版

首页 > 试题广场 >

两个软硬程度一样的鸡蛋，它们在某一层摔下会碎，有个100层的

[问答题]

两个软硬程度一样的鸡蛋，它们在某一层摔下会碎，有个100层的建筑，要求最多用两个鸡蛋确定鸡蛋安全下落的临界位置，给出临界位置？如果是n层楼，m个鸡蛋，请给出确定临界位置的算法

万QQ

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

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

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

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

状态转移方程：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

发表于 2015-06-19 11:56:47 回复(0)

天外来客

看这里：http://blog.csdn.net/wolinxuebin/article/details/47057707

发表于 2016-09-28 18:17:49 回复(0)

小小娃爱吃甜食

动态规划解决，

100层楼时，临界位置为14

n层时：f(b-a+1,m)=min{max{1+k,1+f(b-a-k,m)}|0<=k<=b-a}

更多参考： http://blog.csdn.net/woodbean/article/details/7555310

发表于 2015-07-13 15:25:45 回复(0)

大逗比

第一个蛋第一次14楼，碎了第二个蛋从1开始，最多14次；

第一个蛋第二次27楼，碎了第二个蛋从15开始，最多14次；

第一个蛋第一次39楼，碎了第二个蛋从28开始，最多14次；

第一个蛋第一次50楼，碎了第二个蛋从40开始，最多14次；

第一个蛋第一次60楼，碎了第二个蛋从51开始，最多14次；

第一个蛋第一次69楼，碎了第二个蛋从61开始，最多14次；

第一个蛋第一次77楼，碎了第二个蛋从70开始，最多14次；

第一个蛋第一次84楼，碎了第二个蛋从78开始，最多14次；

第一个蛋第一次90楼，碎了第二个蛋从85开始，最多14次；

第一个蛋第一次95楼，碎了第二个蛋从91开始，最多14次；

第一个蛋第一次99楼，碎了第二个蛋从96开始，最多14次；

第一个蛋第一次100楼，//碎了第二个蛋从100开始，最多14次；

编辑于 2015-05-28 00:19:27 回复(2)

快乐记忆

需要从一层开始检测。摔碎为止。剩一个煮着吃掉。

发表于 2019-08-10 17:31:57 回复(0)

⊙∀⊙！！

二分的话许多不是扔log2(100)次？

发表于 2018-03-29 10:42:22 回复(0)

想奔跑的蜗牛

在假定在每一层下落安全概率相等的情况下可以使用二分法

发表于 2016-07-26 09:54:04 回复(0)

我呀哈哈哈

第一次 在16楼 如果碎了就拿第二个蛋去1楼，然后2楼...
如果不碎就去16+15 楼 如果碎了就去16+1 楼 
如果不碎去16+15+14楼 如果碎了就去16+15+1 楼 
如果不碎去16+15+14+13楼 如果碎了就去16+15+14+1 楼 
如果不碎去16+15+14+13+12楼 如果碎了就去16+15+14+131 楼 
如果不碎去16+15+14+13+21+11楼 如果碎了就去16+15+14+13+12+1 楼 
如果不碎去16+15+14+13+21+11+10楼 如果碎了就去16+15+14+13+21+11+1 楼 
如果不碎去16+15+14+13+21+11+10+9（=100）楼 如果不碎就OK了。 如果碎了去16+15+14+13+21+11+10+1 （91）楼 然后92... 

最多16次就OK了

发表于 2015-05-22 21:54:17 回复(0)

陈木木

动态规划方法
100层楼2个鸡蛋：f[n] = min(1 + max(i - 1, f[n - i])) i = 1……n
n层楼m个鸡蛋：f[i, 0] = 0; f[n,m] = min(1 + max(f[i - 1, m - 1], f[n - i, m]) i = 1…n

发表于 2015-05-05 14:34:43 回复(0)

提交观点

问题信息

动态规划

上传者：陈木木

难度：

9条回答 265收藏 12305浏览

两个软硬程度一样的鸡蛋，它们在某一层摔下会碎，有个100层的

问题信息

热门推荐

相关试题