`

大楼扔鸡蛋问题的求解讨论

阅读更多

有道经典的算法题,100层楼,两个鸡蛋。某层之上扔鸡蛋就会碎。问至少要测试多少次才能找出这层楼来。

 

如果只有一个鸡蛋,我就只能一层一层试验。两个的话关键就是找着第一个鸡蛋试验的位置,第二个鸡蛋还是只能一层一层试验。

这道问题其实可以扩展到任意个鸡蛋,但现在还是只看2个鸡蛋的情况。

2个鸡蛋只有n层的最优解求出来假使为k,那么,n+1层的时候,把第一个鸡蛋在第k层释放,只有两种情况(n+1只是分解成两个<=n的子问题,这两个都是已经有解了的):

(1)破碎,于是只有之后就只能遍历从地面到第k-1层,一层层遍历,不能偷懒,最坏的情况在此要尝试k次;

(2)没碎,那问题不就变成了要在n-k层里面求解的子问题了吗?

假设最优解y=f(2,n),所以得到:

 

f(2,n+1) = max(k, f(2,n-k)+1)

 

接下去的递归求解就豁然开朗了。

 

我本以为问题就差不多可以结了,赶紧去写代码吧,可是小罗同学叫住我了:

表急,好像有更简单的解法:

 

找一个k  k(k+1)/2>=100,k可取的最小整数值就是最优解

 

 

这个好像是猜出来的,得证明一下。

(a)要证明k(k+1)/2>=n里面k是可以准确找出这层楼的解;

(b)当k<=k-1的时候,不等式恒不成立

这样才能得出这个k是最优解。

 

小罗同学说,可以用数学归纳法证明这第(a)点:

 

k=1时,1(1+1)/2>=1成立。
现在用数学归纳法,根据f(k-1)=(k-1)(k-1+1)/2>=n-k,得出f(k)=k(k+1)>=n,依据是前面提到了碎和没碎两种情况的分类讨论。

 

 

当然,还可以用“递降法”:

 

要证明k(k+1)>n
只需要证明(k-1)(k-1+1)/2>=n-k
只需要证明(k-2)(k-2+1)/2>=n-k-(k-1)
……
只需要证明0>=n-(k+k-1+k-2+...1)
等价于k(k+1)/2>=n

 

 

无论如何,这只完成了上面的第(a)点,还有第(b)点没有证明呢,即:

当k<=k-1的时候,不等式恒不成立,又即下面的不等式恒成立:

 

(k-1)k/2<n

 

走到这一步似乎没法进行下去了……

谁来为我指指路呢?呵呵。

 

--------------------------------------------------------------------------------------------------------------------------------

2012-2-3晚上补充:

上式的解决办法,还是数学归纳法:

 

f(k)的时候,第一次测试不能高于k层(因为第一次测试高于k的时候,如果碎了,就肯定不能保证k次测试出来了)
如果f(k)=x,第一次不能高于k,那么剩下至少是x-k是吧 
剩下的次数是k-1次是吧 
所以x-k>=f(k-1)=(k-1)(k-1+1)/2
所以x>=k(k+1)/2 
又显然f(1)=1(1+1)/2=1 
所以对于f(k-1)成立的话,f(k)也成立
 

 

文章系本人原创,转载请注明出处和作者

1
2
分享到:
评论
6 楼 lightgjc1 2012-02-05  
重在思想。。。
5 楼 血冷狼 2012-02-03  
天啊  不懂
4 楼 RayChase 2012-02-03  
mixer_a 写道
转载的吧,以前是仍玻璃球吧,又是这些垃圾的问题

文章系本人原创,转载请注明出处和作者
3 楼 mixer_a 2012-02-03  
转载的吧,以前是仍玻璃球吧,又是这些垃圾的问题
2 楼 ericchandn 2012-02-03  
原题是扔玻璃球吧,扔鸡蛋能不碎?
1 楼 RayChase 2012-02-03  
关于上面最先写的那个递归求解方法,参见 Tsaid 的代码:
http://blog.csdn.net/tsaid/article/details/6835908

相关推荐

    智能问题求解课件

    5. **专家系统中的问题求解方法**:“第二部分 专家系统中的问题求解方法.ppt”可能讨论了基于知识的系统如何利用领域专家的经验来解决问题,包括规则推理、模糊逻辑和神经网络等知识表示和推理方法。 6. **博弈论...

    数据抽象和问题求解-C++语言描述(第四版)源码

    《数据抽象和问题求解-C++语言描述(第四版)源码》是一本深度探讨C++编程中的数据抽象和问题解决策略的专业书籍。在学习C++编程的过程中,数据抽象是核心概念之一,它涉及到如何设计和实现复杂系统,以及如何通过...

    数据结构与问题求解Java语言

    本书从讲解什么是数据结构开始,延伸至高级数据结构和算法分析,强调数据结构和问题求解技术。本书的目的是从抽象思维和问题求解的观点提供对数据结构的实用介绍,试图包含有关数据结构、算法分析及其Java实现的所有...

    漫画:动态规划解决扔鸡蛋问题 - IT程序猿1

    在扔鸡蛋问题中,动态规划可以帮助我们找出在有限的鸡蛋数量下,找到鸡蛋不会摔碎的最高楼层所需的最少尝试次数。 扔鸡蛋问题通常设定为有M层楼和N个鸡蛋,目标是找到摔不碎鸡蛋的临界点。这个问题的关键在于确定一...

    c++数据结构原理与经典问题求解(源代码)

    《C++数据结构原理与经典问题求解》是一本深入探讨C++编程语言在数据结构领域的应用和问题解决的书籍。源代码的提供为读者提供了实际动手操作的机会,加深理解并提升技能。以下是对该主题的详细阐述: 一、C++语言...

    凸约束二次规划问题求解的一般方法.pdf

    "凸约束二次规划问题求解的一般方法" ...本文讨论了凸约束二次规划问题的求解方法,包括标准对偶变换的基本思想、对偶问题的构建、求解对偶问题等。这些方法可以广泛应用于实际问题中,解决凸约束二次规划问题。

    matlab基于求解器intlinprog求解TSP问题

    matlab基于求解器intlinprog求解52城市TSP问题完整数据与代码。本案例说明如何使用二元整数规划来求解经典的TSP问题。此问题涉及找到一条历经一系列停留点(城市)的最短回路(路径)。在本例中有 52 个停留点,但你...

    基于python+gurobi的数值双层规划问题求解

    在标题中提到的“基于python+gurobi的数值双层规划问题求解”,意味着我们将使用Python作为编程语言,并利用Gurobi这个强大的优化求解器来解决双层规划问题。Gurobi是一个商业的数学优化软件,它能高效地处理线性...

    ipopt优化问题求解器

    Ipopt(Interior Point Optimizer)是一种强大的开源优化求解器,专门用于解决连续非线性优化问题。在数学规划领域,非线性优化是寻找一个函数的最小值或最大值,其中至少有一个变量与目标函数的关系不是线性的。...

    数据结构与问题求解 Java语言版 第4版

    数据结构与问题求解 Java语言版 第4版

    使用求解器求解车间调度问题、带阻塞的车间调度问题

    标题中提到的“使用求解器求解车间调度问题、带阻塞的车间调度问题”,指的是利用特定的优化软件工具来解决这类问题。以下是三个常用的求解器: 1. **Cplex**:这是一个由IBM开发的强大的线性、整数和混合整数编程...

    代码 人工鱼群求解TSP问题源代码

    代码 人工鱼群求解TSP问题源代码代码 人工鱼群求解TSP问题源代码代码 人工鱼群求解TSP问题源代码代码 人工鱼群求解TSP问题源代码代码 人工鱼群求解TSP问题源代码代码 人工鱼群求解TSP问题源代码代码 人工鱼群求解TSP...

    数据结构与问题求解(Java语言版)(第4版) 带完整目录标签

    数据结构与问题求解(Java语言版)(第4版) 带完整目录标签,

    n皇后问题的求解n皇后问题的求解

    n皇后问题 Very Goodn皇后问题的求解n皇后问题的求解

    matlab指派问题求解函数

    关于matlab指派问题的求解函数,可求解最大效益或最小成本。代码文件为.m形式,使用软件为matlab,详解博文https://blog.csdn.net/weixin_67016521/article/details/126087775?spm=1001.2014.3001.5502

    汇编语言汉诺塔问题求解

    汇编语言汉诺塔问题求解 使用递归方法求解 还有系统时间

    代码 改进蚁群算法求解连续空间优化问题代码

    代码 改进蚁群算法求解连续空间优化问题代码代码 改进蚁群算法求解连续空间优化问题代码代码 改进蚁群算法求解连续空间优化问题代码代码 改进蚁群算法求解连续空间优化问题代码代码 改进蚁群算法求解连续空间优化...

    如何求解问题-现代启发式方法

    本书《如何求解问题:现代启发式方法》是由Zbigniew Michalewicz与David B. Fogel共同撰写,由曹宏庆等人翻译的作品。该书以一种深入浅出的方式,介绍了一系列现代启发式方法,即借助计算机技术来求解各类问题的先进...

    ECOS求解器求解二阶锥问题C语言程序

    ECOS(Embedded Cone Solver)是一种高效且开源的求解器,专门用于解决凸优化问题,尤其是包含锥约束的问题。在二阶锥问题中,我们处理的是一类特殊的凸优化问题,其中约束集由不同类型的锥体(如线性锥、二次锥等)...

    程序设计与问题求解

    程序设计与问题求解I第一章

Global site tag (gtag.js) - Google Analytics