您现在的位置是:首页 > 文章详情

动态规划法(七)鸡蛋掉落问题(二)

日期:2018-06-05点击:351

上次我们讲到,我们的主人公丁丁由于用动态规划法解决了鸡蛋掉落问题(egg dropping problem)而获得了当地科学家的赏识。这不,正当丁丁还沉浸在解决问题的喜悦中,科学家又给丁丁出了一个难题:

假设有n个鸡蛋和d次尝试机会,那么,最多能探索多少层楼?

这无疑是鸡蛋问题的翻版,因为这两个问题实在太像了。丁丁没有犹豫,立马按照之前的想法开始思考:

f(d,n)f(d,n)表示该问题的解。假设从k层楼扔下鸡蛋(k足够大),若鸡蛋碎了,则剩下n-1个鸡蛋,d-1次尝试机会,最多能向下探索f(d1,n1)f(d−1,n−1)层楼;若鸡蛋没碎,则剩下n个鸡蛋,d-1次尝试机会,最多能向上探索f(d1,n)f(d−1,n)层楼,于是:

f(d,n)=1+f(d1,n1)+f(d1,n).f(d,n)=1+f(d−1,n−1)+f(d−1,n).

g(d,n)=f(d,n+1)f(d,n)g(d,n)=f(d,n+1)−f(d,n),则:
g(d,n)=f(d,n+1)f(d,n)=[1+f(d1,n)+f(d1,n+1)][1+f(d1,n1)+f(d1,n)]=[f(d1,n+1)f(d1,n)]+[f(d1,n)f(d1,n1)]=g(d1,n)+g(d1,n1)g(d,n)=f(d,n+1)−f(d,n)=[1+f(d−1,n)+f(d−1,n+1)]−[1+f(d−1,n−1)+f(d−1,n)]=[f(d−1,n+1)−f(d−1,n)]+[f(d−1,n)−f(d−1,n−1)]=g(d−1,n)+g(d−1,n−1)

因为 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.因为在组合数学中,有:
Ckn=Ckn1+Ck1n1,Cnk=Cn−1k+Cn−1k−1,

因此,由数学归纳法可知: g(d,n)=Cn+1d.g(d,n)=Cdn+1. n+1dn+1≥d时, Cn+1d=0.Cdn+1=0.对于 f(d,n)f(d,n),有:
f(d,n)=++++[f(d,n)f(d,n1)][f(d,n1)f(d,n2)][f(d,1)f(d,0)]f(d,0).f(d,n)=[f(d,n)−f(d,n−1)]+[f(d,n−1)−f(d,n−2)]+⋯+[f(d,1)−f(d,0)]+f(d,0).

因为 f(d,0)=0f(d,0)=0,因此 f(d,n)=i=1nCid,d1.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), 欢迎大家关注哦~~

原文链接:https://yq.aliyun.com/articles/615194
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章