这道题是说,100层楼,两个一模一样的鸡蛋,某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论过这个问题的解法,因为只想记录一下思路和讨论过程,写得很简略。现在,我想重新整理一下这个问题,再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述,把这个问题的前后说清楚。
现在只有两个鸡蛋,而算法必须是可行的,就是说要能找出这一层来,所以你得假设你的运气最差,这就意味着,我求解的是在每种扔鸡蛋的策略下都有一个需要扔的次数的最大值,而现在需要求解的是这些最大值中的最小值的问题。如果我只有一枚鸡蛋,这就意味着,我只能从第一层开始老老实实地一层一层往上试,不能越层;而我的运气非常非常差,于是我这样试验的结果就是一直试验到最高一层鸡蛋依然没破,试验的次数就等于楼层数N。
动态规划法求解
现在,我有两枚鸡蛋,第一枚鸡蛋从哪一层楼开始扔就显得至关重要了。如果第一枚鸡蛋碎了,那就回到刚说的只有一枚鸡蛋的问题了。我相信很多人立即映射到脑子里的词是“二分法”,也就是说,第一枚鸡蛋从N/2开始扔,如果碎了,扔的楼层数就是N/2(注意取整);如果没碎,剩下N/2楼层里继续用二分法。可以预计,如果没碎的情况,扔鸡蛋的总次数要小于N/2。也就意味着,还有潜力可挖,如果不用二分法,让扔第一枚鸡蛋的楼层数为x,它小于N/2;同时如果第一枚鸡蛋没碎,接下去的策略,在运气最差的情况下仍然让扔的次数等于x,就最经济了。
最常规的解法是动态规划。可以用动态规划法求解的问题必须满足这样的条件,分割成的子问题是最优解的时候,原问题也是最优解。显然这个问题满足这一点:假设扔的总次数为f(x),在第一次扔碎了的情况下,接下去只能一层一层试验,最多从第1层到第x-1层需要试验x-1次,加上扔第一个鸡蛋那一次,总的次数就是(x-1)+1=x;在第一次没碎的情况下,就相当于一个新的相似子问题:在N-x层中寻找新的扔鸡蛋次数f(N-x),因此总次数就是f(N-x)+1。那么:
f(x)=max(x, f(N-x)+1)
同时,递归求解的出口是:当x=1,f(x)=1。所以,算法大致如下:
// times[i]表示N取值为i的时候,需要扔多少次 private static int[] times; public static int dropEgg(int N) { // 初始化数组 times = new int[N + 1]; return dp(N); } private static int dp(int N) { // 两层楼或一层楼就没有计算的必要了 if (1 == N) return 1; else if (2 == N) return 2; for (int x = 2; x < N; x++) { int max = maxTimes(N, x); if (0 == times[N] || times[N] > max) times[N] = max; } return times[N]; } // 碎和不碎的次数最大值 private static int maxTimes(int N, int x) { int sum = dp(N - x) + 1; if (x < sum) return sum; else return x; }
“两个鸡蛋”到“m个鸡蛋”
现在把问题扩展一下,由两个鸡蛋扩展到m个鸡蛋,times数组第一维表示最多可以扔几次,第二维表示扔第几次:
public static int dropEgg(int N, int m) { // 初始化数组 times = new int[m + 1][N + 1]; return dp(N, m); } private static int dp(int N, int m) { if (1 == m || 1 == N || 2 == N) return N; for (int time = 2; time <= m; time++) for (int x = 2; x < N; x++) { int max = maxTimes(N, x, time); if (0 == times[time][N] || times[time][N] > max) times[time][N] = max; } return times[m][N]; } // 碎和不碎的次数最大值 private static int maxTimes(int N, int x, int m) { int sum = dp(N - x, m) + 1; if (x < sum) return sum; else return x; }
寻找规律
还是回到两个鸡蛋,随着N的值改变,可以发现x呈现这样的变化:
N=1, x=1
N=2, x=2
N=3, x=2
N=4, x=3
N=5, x=3
N=6, x=3
N=7, x=4
N=8, x=4
N=9, x=4
N=10, x=4
N=11, x=5
N=12, x=5
N=13, x=5
N=14, x=5
N=15, x=5
N=16, x=6
N=17, x=6
N=18, x=6
N=19, x=6
N=20, x=6
N=21, x=6
……
换言之,x=1的有1项,x=2的有2项,x=3的有3项……网上最多的问法是当N=100的时候,x是多少,根据这个规律:
(1+x)*x/2>=100
得知x的最小值是14。
下面来证明一下这个猜想:
因为当扔鸡蛋的最小次数为x的时候,第一次从x层开始扔,如果碎了,那么接下去就要扔x-1次;如果没碎,接下去就变成了扔鸡蛋最小次数为x-1的子问题了,此时再扔的楼层数变成了x+(x-1),在这种情况下碎和不碎两种情况下需要再扔的次数是相等的,已经是最经济的扔法了,继续之,可以得到,扔鸡蛋最小次数为x的时候,最高可以检测到的楼层数为:
x+(x-1)+(x-2)+……+1
正好是一个等差数列求和的公式。
这也是为什么,我们可以从网上找到的扔鸡蛋问题,好多都是N等于15、21、28、36这样的数,这正好等于这个等差数列和。
现在把问题稍稍转变一下,把鸡蛋数量的限制去掉,再把求爬楼梯的限制加上,不妨再来求解:
如果鸡蛋数量无限,但是假如说扔一次鸡蛋需要耗费力气a,每爬一层楼(无论向上还是向下)需要耗费力气b,现在用怎样的扔鸡蛋策略,可以让耗费的总力气量最小?
相关推荐
区间DP概率DP树形DP插头DP,每种DP一道典型例题,有助于初学者
得宝 迪普乐DP-F850 DP-F650 DP-F620 DP-F550 DP-F520 制版印刷一体机 维修手册
蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A...
DP83848中文数据手册 DP83848中文文档 全篇翻译无排版 DP83848C / I / VYB / YB PHYTER™QFP单端口10/100 Mb / s以太网物理层收发器 从–40°C到105°C的多个温度范围•IEEE 802.3 ENDEC,10BASE-T收发器和 • 低...
1. 同一项目中S7-1200 与 S7-300 集成 DP 口之间 DP 主从通信,S7-1200 通过CM1243-5作为 DP 主站,S7-300 集成 DP 口作为 DP 从站; 2. 不同项目中S7-1200 与 S7-300 集成 DP 口之间 DP 主从通信,S7-1200 通过CM...
VESA官网的DP1.4标准协议
DP接口介绍 1、 DP接口简介 2、 DP接口分类 2.1 标准DP接口 2.2 Mini-DP接口 3、 DP版本迭代 3.1 DP 1.0版本 3.2 DP 1.1a版本 3.3 DP 1.2版本 3.4 DP 1.3版本 3.5 DP 1.4版本 3.6 DP 2.0版本 3.7 版本对比 4、 DP...
2 DP软件的文件结构 4 2.1 DP软件的配置信息 4 2.2 DP软件的执行程序 4 2.3 DP软件的内部数据库 4 3 DP软件的后台进程 5 3.1 DP软件的自动启动配置 5 3.2 DP软件的手工启动方法 5 3.3 DP软件的后台进程 5 4 DP软件...
C#,动态规划(DP)丢鸡蛋问题(Egg Dropping Puzzle)的三种算法与源代码 动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等...
Android 蓝牙 A2dp 听歌卡音?audio数据到a2dp通道流程解析----A2dp流控原理(Acl Flow Control),一文搞懂蓝牙卡音问题处理
ASL CS5523是MIPI DSI输入、DP/e DP输出转换芯片。MIPI DSI最多支持4个通道,每个通道的最大运行速度为1.5Gps。对于DP 1.2输出,它由4个数据通道组成,支持1.62Gbps和2.7Gbps的链路速率。支持1.62Gbps和2.7Gbps的...
GSD EC1-DEB-DPM Elau
16位LED恒流源驱动芯片,DP5020B 是专为 LED 显示屏设计的驱动芯片,内 建 CMOS 位移寄存器与锁存功能,可以将串行的输入 数据转换成并行输出数据格式
DP5020是LED显示面板设计的驱动IC,它内建的CMOS位移寄存器与锁存功能,可以将串行的输入数据转换成平行输出数据格式。
DP83640中文手册
dp modeler 使用手册
适用于RD-EB、RD-ET、RD-EZ、RD-EB-MX、RD-ET-MX、RD-EZ-MX、KRD-EB、KRD-ET、KRD-EZ、KRD-EB-MX、KRD-ET-MX、KRD-EZ-MX 、SRD-R100、Q3-R100、Q3-R101、Q3-R102、DP-R103、DP-R 113、DP-R123、DP-R133、DP-R143、...
很实用的DP/DP COUPLE 快速使用教程
以太网DP83848设计参考
DP1.4标准——VESA Proposed DisplayPort (DP) Standard.pdf