有限层数和蛋数,求即使最坏情况下需要的最少判断次数
两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。
这是典型的动态规划问题。假设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)
实际上,两个鸡蛋的情况用数学方程就可以解决,前提是你知道该怎么扔:
一种想法是第一个鸡蛋折半搜索,如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层开始扔。依此类推,各次尝试的楼层依次为
14
27 = 14 + 13
39 = 27 + 12
...
99 = 95 + 4
100
现在推广成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
原文地址:http://www.cnblogs.com/ltang/archive/2010/11/23/1885791.html
分享到:
相关推荐
从一幢楼房的不同楼层往下扔鸡蛋,用最少的最坏情况试验次数,确定鸡蛋不会摔碎的最高安全楼层。仅有一个鸡蛋供试验时,只能采用顺序查找法。有足够多的鸡蛋时,可以采用二分查找法。有多于一个但数量有限的鸡蛋时,...
电梯楼层显示电路.。。。。。。。。。。。。。。。。。
模型分离,楼层扩散,模型爆炸效果
直接定位菜单楼层,并选中相应的菜单,便于用户一直看到页面的相应内容和结构
电梯楼层显示电路课程设计
项目中遇到比较多的的文档内容,为了方便查找里面的小内容,一般都会在左侧或者右侧放一个固定楼层的导航栏,今天就来分享一下这个固定楼层导航栏的思路以...
页面分为几个楼层展示内容,向下滑动左侧出现楼层按钮,点击楼层按钮跳转到对应楼层处,滑动时,楼层也在变化
单片机课设 电梯楼层显示器设计.doc
基于three.js的商场楼层的展示以及导航功能,可以独立楼层的选择、查看,整体三维的效果,还是不错的。
lineayout实现仿网易楼层
重庆建筑shpfile数据(含楼层)可用于城市规划,数据分析,三维可视化 重庆建筑shpfile数据(含楼层)可用于城市规划,数据分析,三维可视化 重庆建筑shpfile数据(含楼层)可用于城市规划,数据分析,三维可视化 ...
jQuery楼层定位菜单代码是一款商城常用的点击侧边楼层或者鼠标滚轮滚动都能精确定位到页面对应的楼层位置的折叠式楼层菜单网页特效。
jquery 实现商城首页楼层滚动
随着无线网络技术及应用的快速发展,越来越多的场合需要组建方便、快捷的无线网络,本文介绍的是一种多楼层无线网络覆盖方案 的部署与配置。 多楼层无线网络覆盖 推荐方案:无线漫游网络 优点:无线客户端在信号覆盖...
模拟程序还包含一个调度器(Scheduler),它通过随机设置两个时间开始每一天:第一个时间是一个人首次走到1层,并按下楼层按钮召唤电梯时间,第二个时间是一个人首次走到2层,并按下按钮召唤电梯时间。每个时间都是...
楼层滚动简易模板,js、css、html楼层滚动模板 js、css、html楼层滚动模板,看看就行
绍兴建筑shpfile数据(含楼层),可用于城市规划,三维可视化分析 绍兴建筑shpfile数据(含楼层),可用于城市规划,三维可视化分析 绍兴建筑shpfile数据(含楼层),可用于城市规划,三维可视化分析 绍兴建筑...
基于 vue + leaflet 的 商城楼层平面图展示 ,商城内部个区域分割且实现点击,支持自定义GeoJSON 文件 ,适用于有一定前端基础的人员。
在c#中实现楼层的输出 按顺序 按楼层的输出先关信息
西安建筑shpfile数据(含楼层),可用于城市规划,三维可视化分析 西安建筑shpfile数据(含楼层),可用于城市规划,三维可视化分析 西安建筑shpfile数据(含楼层),可用于城市规划,三维可视化分析 西安建筑...