动态规划法(六)鸡蛋掉落问题(一)(egg dropping problem)
继续讲故事~~
这天,丁丁正走在路上,欣赏着路边迷人的城市风景,突然发现前面的大楼前围了一波吃瓜群众。他好奇地凑上前去,想一探究竟,看看到底发生了什么事情。
原来本市的一位小有名气的科学家正在这幢大楼进行一个实验:某种材料的防护性能。他在大楼的底下铺了一层这种防护材料,想拿鸡蛋做实验,将鸡蛋从楼层掉下,看看鸡蛋从哪一层掉下去会摔碎,以此测试该材料的防护性能。这就是著名的鸡蛋掉落问题(egg dropping problem),即给定N个鸡蛋和k层楼,试问至少需要几次才能确定鸡蛋从哪一层楼掉下去恰好摔碎。
一听到这个问题,他顿时感觉无从下手,没有丝毫的头绪。但他尝试着先从最简单的情形入手:
- 若鸡蛋数N=0或者楼层数为0,则尝试0次即可。
- 若鸡蛋数N=1, 对于楼层数为k,最坏的情况为尝试k次,因此至少需要k次才能确定鸡蛋从哪一层楼掉下去恰好摔碎。
有了最基本的情形还不够,对于其他的N,k并没有给出答案。这时,他想到自己这几天正在研究的算法:动态规划法,他想也许这个算法可以帮上忙。假设用numdrops(N,k)表示该问题的解。则将鸡蛋从x层扔下,有以下两种情形:
- 鸡蛋摔碎了,此时剩下N-1个鸡蛋,需要考虑比x层低的楼层,即1,2,…,x-1层,因为比x层高的楼层扔下去必定也摔碎,故可不比考虑。因此,这个问题会被缩减到numdrops(N-1, x-1).
- 鸡蛋没有摔碎,此时剩下N个鸡蛋,需要考虑比x层高的楼层,即x+1, x+2,…,k层,共有k-x层。因此,问题会被缩减到numdrops(N, k-x).
对于以上两种情形,应该去两者的最大值。同时,考虑到x=1,2,3,…,k, 因此有如下公式:
有了以上算法,再加上如下初始情况:
- numdrops(0, x)=0, numdrops(x,0)=0.
- numdrops(1, x)=x.
就可以用动态规划法求解该问题了。他迅速地写下了Python代码:
import numpy as np def solvepuzzle(n, k): numdrops = np.array([[0]*(k+1)]*(n+1)) for i in range(k+1): numdrops[1, i] = i for i in range(2, n+1): for j in range(1, k+1): minimum = float('inf') for x in range(1, j+1): minimum = min(minimum, (1+max(numdrops[i, j-x], numdrops[i-1, x-1]))) numdrops[i, j] = minimum print(numdrops) return numdrops[n,k] t = solvepuzzle(3, 10) print(t)
输出结果如下:
[[ 0 0 0 0 0 0 0 0 0 0 0] [ 0 1 2 3 4 5 6 7 8 9 10] [ 0 1 2 2 3 3 3 4 4 4 4] [ 0 1 2 2 3 3 3 3 4 4 4]] 4
这样就可以求出该问题的解了,比如4个鸡蛋10层楼,则只需要3次即可。
丁丁连忙把这个解答问题通过助手告诉了科学家。科学家听后兴奋不已,立马叫丁丁过来讨论。科学家对他说道:“你的解决方法是如此的巧妙,让人叹为观止,很难相信它是出自一个少年的脑袋中。但是,亲爱的朋友,你能告诉我具体应该怎么扔鸡蛋呢?”
丁丁听了,又是欢喜又有点担心,因为科学家又提出了一个问题。他看看了输出的numdrops表格,立马就有了主意。
对于N=2,k=50的情形,numdrops(N,k)=10,给出的方案如下:
从哪一层扔鸡蛋 | 鸡蛋摔碎后的情形 | 次数 |
---|---|---|
10 | 1->2->3->4->5->6->7->8->9 | 9+1=10 |
19 | 11->12->13->14->15->16->17->18 | 8+2=10 |
27 | 20->21->22->23->24->25->26 | 7+3=10 |
34 | 28->29->30->31->32->33 | 6+4=10 |
40 | 35->36->37->38->39 | 5+5=10 |
45 | 41->42->43->44 | 4+6=10 |
49 | 46->47->48 | 3+7=10 |
50 | 8 |
尝试着对上表做说明:先从第10层扔下,若鸡蛋摔了,则还剩一个鸡蛋,依次从1,2,3…9层扔下,若鸡蛋没碎,则失去了一次尝试机会,再将鸡蛋从19层扔下,若鸡蛋碎了,则还剩一个鸡蛋,依次从11,12,…,18层扔下……
对于N=4,k=20的情形,numdrops(N,k)=10,输出的numdrops表如下:
[[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20] [ 0 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6] [ 0 1 2 2 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5] [ 0 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5]] 5
首先找到numdrops(3,14)=4, 次数比5小一次, 层楼k尽可能大,则将鸡蛋从15扔下,若鸡蛋没碎,则剩下3个鸡蛋,探索4层楼,因为numdrops(3,14)=4,故能完成。若鸡蛋碎了,则再找到numdrops(2,6)=3,则将鸡蛋从7楼扔下,若鸡蛋碎了,则情形转化为numdrops(2,6)的情形,若鸡蛋没碎,则用剩下的鸡蛋探索7层楼,是可以搞定的。
当科学家看到这个结果后,满意地点点头,他想着是否要聘请这个少年来当自己的助手。不过,他决定再考验丁丁一回~~
未完待续~~
注意:本人现已开通两个微信公众号: 用Python做数学(微信号为:python_math)以及轻松学会Python爬虫(微信号为:easy_web_scrape), 欢迎大家关注哦~~
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
关于深度学习,这里有一份入门公开课(文末福利)
点击图片购书 参与文末话题讨论,每日赠送异步图书 ——异步小编 前不久,“逃犯看张学友演唱会被抓”的新闻让不少人都感慨,原来演唱会还能用来干这个!其实这都是AI面部识别技术的功劳,在支付、安防等领域,AI面部识别技术有着广泛的应用。在互联网金融信贷风险控制中,我们也会借助机器学习和统计分析的模型,对信贷申请者进行“AI面部识别”。即使一个微博、一条朋友圈这些看似平常的个人社交信息,经过AI模型计算后,也能帮助我们识别出那些可能的“逃犯”——信贷欺诈者。 本次公开课将从建模的角度,介绍互联网金融反欺诈模型的关键——如何从信贷申请数据中提取出有用的特征。实际的建模结果表明,信贷申请人的“社交网络”特征往往是最有效的。 1|分享嘉宾介绍我是谁?我为什么要开公开课 唐亘,数据科学家,《精通数据科学:从线性回归到深度学习》一书作者。热爱并积极参与Apache Spark、 scikit-learn等开源项目。作为讲师和技术顾问为多家机构(包括惠普,华为,复旦大学等)提供百余场技术培训。 在此之前,工作和研究集中于经济和量化金融,曾参与经合组织(OECD)的研究项目并发表论文,并担任英国在线出...
- 下一篇
3 个 Python 模板库比较
在我的日常工作中,我花费大量的时间将各种来源的数据转化为可读的信息。虽然很多时候这只是电子表格或某种类型的图表或其他数据可视化的形式,但也有其他时候,将数据以书面形式呈现是有意义的。 但我的头疼地方就是复制和粘贴。如果你要将数据从源头移动到标准化模板,则不应该复制和粘贴。这很容易出错,说实话,这会浪费你的时间。 因此,对于我定期发送的任何遵循一个共同的模式的信息,我倾向于找到某种方法来自动化至少一部分信息。也许这涉及到在电子表格中创建一些公式,一个快速 shell 脚本或其他解决方案,以便使用从外部源提取的信息自动填充模板。 但最近,我一直在探索 Python 模板来完成从其他数据集创建报告和图表的大部分工作。 Python 模板引擎非常强大。我的简化报告创建的使用案例仅仅触及了它的皮毛。许多开发人员正在利用这些工具来构建完整的 web 应用程序和内容管理系统。但是,你并不需要有一个复杂的 web 应用程序才能使用 Python 模板工具。 为什么选择模板? 每个模板工具都不甚相同,你应该阅读文档以了解其确切的用法。但让我们创建一个假设的例子。假设我想创建一个简短的页面,列出我最近编写...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Windows10,CentOS7,CentOS8安装Nodejs环境
- Docker安装Oracle12C,快速搭建Oracle学习环境
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS8编译安装MySQL8.0.19
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS7,8上快速安装Gitea,搭建Git服务器