动态规划与数学方程法解决楼层扔鸡蛋问题

1.问题描述

两个软硬程度一样的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置,可以摔碎两个鸡蛋,求给出一个最佳策略,测出鸡蛋恰好不会碎的楼层,最佳策略满足的条件就是在最坏情况下所扔的次数比其它任意策略的最坏情况下所扔的次数要少。并求最佳策略在最坏情况下所仍的次数。

2.问题剖析

使用一个鸡蛋我们别无选择,只有一种方案就是从一楼逐层网上试探,最坏情况下需要100次试探。但是现在使用两个鸡蛋去试探安全楼层,有很多种试探方法,比如折半试探,在大楼高度一半处的楼层50层扔第一个鸡蛋,碎了只能乖乖的用另一个鸡蛋从一楼逐层往上试,不碎的话就从51~100层的中间层75层扔第一个鸡蛋,依次类推。这种方案如果第一次在第50层楼鸡蛋碎了,第49层是安全层的话,最坏情况下需要扔50次。那么多的测试方案,我们需要找出一个最佳的测试方案,最佳体现在在最坏的情况下扔鸡蛋的次数相比其它任意策略的最坏情况下所扔的次数要少。

什么叫最坏情况,因为我们并不知道鸡蛋会在哪一个楼层首碎,所以对于任意一个测试方案都会有一个最坏的情况,最坏的情况就是试探次数最多的情况。

求解这个问题有两种办法,一种是数学方程法,一种是动态规划法。按照程序员的思路,遇到最优问题的时候,往往可以先尝试一下动态规划的方法。其次,在众多的问题当中,有不少可以直接归结为数学方程式,如果我们能够写出数学方程式,那么,答案将是更加的简洁、美妙。下面一一讲解。

3.数学方程法

假设最坏情况下最少尝试次数为x,那么,第一个鸡蛋必须要从第x层扔下,因为如果碎了,前面还有x - 1层楼需要逐层尝试,如果没碎,后面还有x-1次机会。

如果没碎,第一个鸡蛋第二次就必须从x +(x - 1)层进行尝试,为什么是加上x - 1,因为现在只剩下x-1次机会了,类比第一次扔鸡蛋,有多少次机会,就必须从第多少层开始仍。当此时,如果第一个鸡蛋碎了,第二个鸡蛋还需要从x+1 到 x + (x - 1) - 1层进行逐层尝试,有x - 2次。如果还没碎,那第一个鸡蛋,第三次从 x + (x - 1) + (x - 2)层尝试。碎或者没碎,都有x - 3次尝试机会,依次类推。那么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层开始扔,以此类推。

4.动态规划法

使用动态规划的方法求解,首要的我们要找到构成这个最优问题的最优子问题。

为什么可以用动态规划来求解这个问题呢?仔细一想,寻找100层,因为可以从1~100层之间的任意一层开始开始仍鸡蛋,假设f[n]表示从n层楼找到仍鸡蛋不碎安全位置的最少判断次数。假设第一个鸡蛋第一次从第i层扔下,那么有两种情况: 情况一:碎了,就剩一个鸡蛋,为确定下面楼层中的安全位置,必须从第一层逐层试探,还需要i-1次; 情况二:没碎,上面还有n-i层,剩下两个鸡蛋,还需要f[n-i]次。这个就是子问题了,因为实体n层楼的上n-i层需要的最少判断次数和实体n-i层楼需要的最少判断次数其实是一样的。有了子问题,我们就应该要想到动态规划。

因此,最坏情况下还需要判断max(i-1,f[n-i])次。那么对于每一个i从1到n层,尝试次数最少的,就是f[n]的值。

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

有了初始状态,再根据状态转移方程递推到最终状态,最终状态就是问题的最优解。

最佳试探方案: 得到f[n]后,也就是最坏情况下最少试探次数,有了这个,就可以根据上面数学方程法中提到的试探方案得出最佳试探方案了。一旦确定了最坏情况下最少试探次数,最佳试探方案是唯一确定的,对于两个鸡蛋来说。

问题推广: 现在推广成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属于[1,n]

问题解的矩阵如下:

根据状态转移方程,逐步求出最终解f[n,m]。

具体实现:

/*********************************
@pram:high:楼层高度;eggNum:鸡蛋的数量;
@ret:最少次数
@ps:min和max为C++标准函数模板,申明在<algorithm>
*********************************/
int  eggThrowCnt(int high,int eggNum){
    int dp[32][1024]={0};

    for(int i=1;i<=high;i++)
        dp[1][i]=i;
    for(int i=1;i<=eggNum;i++)
        dp[i][1]=1,dp[i][0]=0;

    for(int i=2;i<=eggNum;i++){
        for(int j=2;j<=high;j++){
            //从k=1层开始仍,找到k=1到j层取最小值
            int k=1;                    
            int minimal=1+max(dp[i-1][k-1],dp[i][j-k]+1);   
            for(;k<=j;++k){
               minimal=min(minimal,1+max(dp[i-1][k-1],dp[i][j-k]));
            }
            dp[i][j]=minimal; 
        }
    }
    return dp[eggNum][high];
}

测试输出:

cout<<eggThrowCnt(39,3);    //输出6
cout<<eggThrowCnt(39,2);    //输出9
cout<<eggThrowCnt(36,2);    //输出8
cout<<eggThrowCnt(100,2);   //输出14
cout<<eggThrowCnt(200,2);   //输出20

多个鸡蛋(>2)的最佳试探方案: 两个鸡蛋我们通过数学推理能够得出最佳的试探方案。在多个鸡蛋的情况下,已经求出了最少试探次数的前提下,如何找到最佳的试探方案呢?

本人在网上查了很多资料,目前还是没有找到答案,也不知道这种情况下最佳试探方案是否唯一,请知道的网友留言告知,万分感谢。


参考文献

[1]楼层扔鸡蛋问题 [2]谷歌面试题——动态规划(扔鸡蛋)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏龙行天下CSIEM

科学瞎想系列之五十 场是个神马鬼

无论你信与不信,它无时无刻不存在着; 无论你用与不用,它无时无刻不作用着; 无论你懂与不懂,它无时无刻不影响着。 ...

31240
来自专栏人工智能LeadAI

命名实体识别 | NLP系列学习

在自然语言处理中,分词,词性标注,命名实体识别和句法情感分析是非常关键的分支,因为最近需要对此有一些应用,便去了解了一下特定领域目前使用的方法以及一些困难,特此...

31600
来自专栏大数据挖掘DT机器学习

从数据分析师笔试试题看职业要求

以下试题是来自阿里巴巴2011年招募实习生的一次笔试题,从笔试题的几个要求可见数据分析职业要求。 一、异常值是指什么?请列举1种识别连续型变量异常值的方法? 异...

44630
来自专栏大数据文摘

拓扑学——探寻大数据的内在模式

23650
来自专栏智能算法

机器人算法专题介绍

算法 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规...

47360
来自专栏量子位

怎样用GAN生成各种胖吉猫?谷歌大脑程序员教你撩妹神技

Facebook聊天框里出道的灰色短毛猫Pusheen,是柔软的微胖界宠儿,中文名字叫胖吉。

16020
来自专栏大数据挖掘DT机器学习

解析滴滴算法大赛---GBDT进行数据预测

按照前面文章的方法进行数据预测,完全不使用POI,天气,交通情况的数据,可以达到0.43的成绩。 不过如果想要获得更好的成绩,简单的预测方法显然无法满足要求了。...

1.7K100
来自专栏PPV课数据科学社区

【学习】趣味数据挖掘——借水浒传故事,释决策树思路

决策树(又称判定树,DecisionTree)是硕、博士生数据挖掘课程要点和难点,教学实践表明,这一章需要数学基础知识多,难得有趣。明知是难点,偏向难点行,再难...

38240
来自专栏AI科技评论

ACL 2018 奖项全公布,北大、哈工大上榜,Mark Steedman 获终身成就奖

AI 科技评论按:ACL 2018 于 7 月 15 日在墨尔本正式开幕,随着会议议程的推进,今天迎来大会的重头戏——ACL 奖项颁布仪式。

10430
来自专栏钱塘大数据

【图说】数据可视化在美国大选中的应用

美国总统并不是按一人一票选出,而是每个州有不同数量的选举人票,如果这个州大多数人投票选这个党派,则整个州的选举人票都被这个党派得到。选举人票数量跟那个州的面积人...

384110

扫码关注云+社区

领取腾讯云代金券