动态规划法(七)鸡蛋掉落问题(二)
上次我们讲到,我们的主人公丁丁由于用动态规划法解决了鸡蛋掉落问题(egg dropping problem)而获得了当地科学家的赏识。这不,正当丁丁还沉浸在解决问题的喜悦中,科学家又给丁丁出了一个难题:
假设有n个鸡蛋和d次尝试机会,那么,最多能探索多少层楼?
这无疑是鸡蛋问题的翻版,因为这两个问题实在太像了。丁丁没有犹豫,立马按照之前的想法开始思考:
用f(d,n)f(d,n)表示该问题的解。假设从k层楼扔下鸡蛋(k足够大),若鸡蛋碎了,则剩下n-1个鸡蛋,d-1次尝试机会,最多能向下探索f(d−1,n−1)f(d−1,n−1)层楼;若鸡蛋没碎,则剩下n个鸡蛋,d-1次尝试机会,最多能向上探索f(d−1,n)f(d−1,n)层楼,于是:
令 g(d,n)=f(d,n+1)−f(d,n)g(d,n)=f(d,n+1)−f(d,n),则:
因为 f(0,n)=f(d,0)=0f(0,n)=f(d,0)=0,对于任意的 n,dn,d,且 f(d,1)=df(d,1)=d,故 g(0,n)=0,g(d,0)=d.g(0,n)=0,g(d,0)=d.因为在组合数学中,有:
因此,由数学归纳法可知: g(d,n)=Cn+1d.g(d,n)=Cdn+1.当 n+1≥dn+1≥d时, Cn+1d=0.Cdn+1=0.对于 f(d,n)f(d,n),有:
因为 f(d,0)=0f(d,0)=0,因此 f(d,n)=∑i=1nCid,d≥1.f(d,n)=∑i=1nCdi,d≥1.于是,科学家的问题就解决了。
突然,丁丁又想到了:能不能用这个结果来解决鸡蛋掉落问题呢?答案是肯定的,对于给定的 k=f(d,n)k=f(d,n),只需要对d从1开始算起,得到d,恰好使得 f(d,n)≥k,f(d,n)≥k,则d即可鸡蛋掉落问题的解。
科学家看了丁丁的解答,十分满意,他终于下定决心招丁丁为自己的助手。不过,丁丁说,他还要去外面的世界再看看,因此,科学家也没有挽留,但他祝愿丁丁好运。
本文不再给出相关的程序,读者可以自己实现哦~~
本文的参考文献为: https://brilliant.org/wiki/egg-dropping/ 。
注意:本人现已开通两个微信公众号: 用Python做数学(微信号为:python_math)以及轻松学会Python爬虫(微信号为:easy_web_scrape), 欢迎大家关注哦~~
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
jdk9+版本的bug
今天从jvm大神"你假笨"的公众号上,看到一个jdk 9+版本的编译bug,记录一下: public class JavacEvalBug{ private static String[] array = {""}; static int test(){ System.out.println("evaluated!"); return 0; } public static void main(String[] args) { //相当于int index=test(); array[index] +="a"; array[test()] += "a"; } } test()方法里输出了一个固定字符串,上面这段代码,如果是在jdk8版本里,执行后,只会输出:evaluated! 一次(这符合预期,因为test()只调用了1次) 但如果把jdk升级到jdk9或10,再次编译运行,evaluated!就会输出2次,即test()方法会多执行了1次,如果test()方法是复杂的业务逻辑,比如创建订单/库存扣减之类,这就成大问题了。 原因在于jdk8与jdk9+的编译机制不同,javap -ve...
- 下一篇
关于URL编码
一、问题的由来 URL就是网址只要上网就一定会用到。 一般来说URL只能使用英文字母、阿拉伯数字和某些标点符号不能使用其他文字和符号。比如世界上有英文字母的网址"http://www.abc.com"但是没有希腊字母的网址"http://www.aβγ.com"读作阿尔法-贝塔-伽玛.com。这是因为网络标准RFC 1738做了硬性规定 "...Only alphanumerics [0-9a-zA-Z], the special characters "$-_.+!*'()," [not including the quotes - ed], and reserved characters used for their reserved purposes may be used unencoded within a URL." "只有字母和数字[0-9a-zA-Z]、一些特殊符号"$-_.+!*'(),"[不包括双引号]、以及某些保留字才可以不经过编码直接用于URL。" 这意味着如果URL中有汉字就必须编码后使用。但是麻烦的是RFC 1738没有规定具体的编码方法而是交给应用程序浏览...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- CentOS6,CentOS7官方镜像安装Oracle11G
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- 设置Eclipse缩进为4个空格,增强代码规范
- Mario游戏-低调大师作品
- MySQL8.0.19开启GTID主从同步CentOS8
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS8编译安装MySQL8.0.19
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池