用2个玻璃球找到从一100层的大楼的某一层落下刚好会摔碎，如何制定最优策略？
有一栋100层高的大楼，给你两个完全相同的玻璃球，假设从某一层开始丢下玻璃球会摔碎，怎么利用手中的两个玻璃球，用什么最优策略（最少次数）知道这个临界的层是第几层
最近是不是到了面试季，看到好多经典面试题。这个题目首先是关于“最优”的定义。考虑best-worse case最坏情况下最优。也就是说假如你的算法是从第一楼逐楼往上试，那么相应最坏的情况是在100楼破，相应的是一百次。这种情况下最优策略也就是匿名用户提到的从14楼开始递减间隔的办法，worst case 需要14次。解法：记n层s球的问题为Q(n,s),对应的最坏情况最优解为ba(n,s);一些简单的结果：(0) ba(m,2)&=ba(n,2) 如果m&n,trivial.(1) ba(n,1)=n当你只剩下一个球，为了能够检验出临界点，你只能逐层检验，最坏情况下所需的检验次数为n；(2)ba(1,2)=1(3)iterative: 假设你从k层扔球，有两种情形：球破。那么临界层必然在1层到k-1层之间，剩下一球，由(1)得出，最坏情况最优所需的步数为: 1 + ba(k-1,1)=k;球不破。问题变成n-k层两球的问题Q(n-k,2), 所以最坏情况最优所需步数是：1+ba(n-k,2);综合1，2，最坏情况所需步数： 当k=1+ba(n-k,2)的时候，ba(n,2)=ba(n-k,2)+1结合(2),(3),由(2)迭代得知:当n = 1+2+3+...+kba(n,2)=k当k=13时， n=91；ba(100,2)=max(9,1+ba(91,2))=14所以100层，最坏情况最优策略的步数是14.
我们首先需要一些假设：玻璃球一定在1－100层底某一层恰好碎掉，而且概率服从平均分布。我们给出的最优是指期望值最小的做法。如果是希望在最少的步数内一定能确定出楼层的，请参考其他人的***。我们的策略是首先选定一些特定的楼层，在这些楼层自下往上试验第一个玻璃球，直到破碎或者到达最后一个特定的楼层，然后我们可以得到一个区间，再在这个区间内从下往上试验第二个玻璃球。第一个球：假设第一个球的试验楼层为。令，那么每次试验落在到之间的概率为，其中，而我们得到这样的区间的尝试次数为。除非在楼层的时候都没碎，此时我们可以确定恰好碎掉的楼层在到之间，次数为。第二个球：如果楼层落在到之间，恰好碎掉的楼层为，其中前个试验次数分别为，而如果恰好碎掉的楼层为所需次数为次，无需再试验层。因此这一步我们平均需要的次数为。我们得到最后的步数的期望值为记，则。(1) 如果允许取任意正实数，我们知道全部相等时达到极小。此时。(2) 但是实际上只能取半整数，容易验证这些数至多相差1时达到极小值。令的小数部分，那么有个和个，(3) 此外，我们还要求。当很大的时候，如果取值相等，将会小于这个范围。这样我们就需要将下标较大的适当地提高以满足实际情况。然而，我们知道如果将大于平均值的一个数调大，而相应地小于平均值的某个数调小时，总的平方和会增大。因此，为了平方和尽量小，我们希望取值尽量靠近，而这样的结果就是，或者说。这种情形实际上可以退化成的情形，所以我们可以不妨假设，，。(4) 我们计算我们发现k&13时，它大于，于是，所以在k-1不能达到极小。因此g的极小值出现在k&=12。k=12时，mu=9/12,g(k)=2062.，此时有8个14和5个13。，此时有8个14和6个13。，此时有9个14和6个13（某些情形会退化）。某些读者可能会注意到一点，因为第一个球有可能在楼层不破碎，这时看上去我们应当将到楼层再进行一次细分，把这个不破碎的球再利用起来。然而实际上由于我们得到的已经是极小值了，因此这种情形不会影响我们的结论，而且我们得到或2或3，简单计算可以发现再次细分不会影响次数的期望值，因此还是变成了我们得到的情形。结论：当且仅当且满足我们给定的情形时，
这题看似直白，其实并不容易。这里的不容易是两个层面的，一是给出一种最优的策略，二是证明该策略是最优的，显然第二层“不容易”要更不容易一些。在正式回答这个问题之前，先对原题做一些补充说明：暂时假设在每个楼层球破碎的概率是一致的。在没有外加信息的情况下，假设均匀的概率分布是最合理的方式（熵最大原理），但这种假设并不能被看作是先验的，我把这种假设称作“均匀分布假设”。事实上，如果把这个题目看成物理问题，考虑球摔碎的力学过程的话，在每个楼层摔碎的概率就更没有理由都相等。为了简明起见，以及为了接下来突出核心问题，暂时认可“均匀分布假设”。（如同题目中标注的，）最优指的是尝试次数最少。如果把最优理解为其他含义，比如“跑上跑下的总楼层数最少”，那显然会得到不同的结论。最终得到的结果将依赖于破碎楼层的概率分布，以及对于“最优”的诠释。再详细回答前，先给出一种（相对）最优的策略：第一个球在没扔碎前，按照如下楼层尝试：13 25 36 47 56 65 72 79 85 90 94 97 98 99 100直到确定一个“不碎-碎”的楼层区间：比如在47层没碎，在56层碎了。第二个球在第一个球确定的“不碎-碎”区间中，逐层向上尝试：比如球最终会在50层碎，那第一个球确定了（47，56]的区间，第二个球依次尝试：48 49 50，将发现球在49层没碎，在50层碎了，于是得到临界层50。图1：不同临界楼层时，该最优策略给出的尝试次数关于上述策略，有必要做几点解释：该策略给出的平均尝试次数为10.31次。（注：此处10.31为精确值；“平均”指的是对球在每一层砸碎的可能情况下的尝试次数的平均值。）该策略的大致思路是显而易见的：通过第一个球确定区间，再通过第二个球逐层搜索。由于要求一定要找到临界层，所以第二个球必须采用需要逐层往上的方式，以免漏过临界层而把仅有的一个球摔碎；所以，这个问题的关键在于找到第一个球尝试的楼层序列，定义为F现在正式解答问题：如上所述，该问题可以粗略的简化为寻找第一个球的尝试序列，但显然可能的序列的总数非常之多，它们构成了一个非常庞大的集合（或者空间），以至于几乎很难处理。所以首先要找到处理这个问题的方法论：1.
给出了一个重要的思路，在几乎是无数种可能的序列挑选出一组特殊的子集，然后用解析的方法求出最优化的解。该特殊的子集要求第一个球的尝试层数是等间隔的：如10 20 30 40 ......，或者6 12 18 24......等。经过一系列的分析， 给出了在这个子集中的最优解：10 20 30 40 50 60 70 80 90 100经过计算，该策略给出的平均尝试次数为10.9，已经比较接近我在之前给出的结果了。我把这个方法称为“等间隔模型”。这种方法论最漂亮的地方在于从一个复杂而庞大的空间选取一个子空间，用类似泛函的方法求出子集中的极值，非常类似于量子力学中的变分法，给出的结果可以视作最优策略（即“基态”）的上界。但这个方法也有明显的问题，即选取的某个子空间很有可能不包括真正的最优解。换句话说，对等间隔模型而言，真正的最优解的序列是否是等间隔的，并不是一件显然的事情，它很有可能（也的确）是错的。图2：不同临界楼层时，等间隔模型给出的尝试次数图2：不同临界楼层时，等间隔模型给出的尝试次数2.第二类方法是一种非常“不靠谱”的做法，就是“猜”。当然这里的猜并不是胡猜，它依据一定的逻辑推理。从分析上述“等间隔模型”的问题开始，将指引我们去“猜”出某种最优的解。对于等间隔模型给出的最优策略，如果真正的临界楼层比较低的时候，这种策略的效率较高，比如：临界楼层是5层，仅尝试一次就可以将区间确定在9层之内；但当临界楼层比较高的时候，比如95层，那么按照该策略，需要从10 20 30开始一直尝试到100层，（共10次），才能将区间确定在9层之内。换句话说，此时，多用了9次尝试才得到了和低楼层时一样的区间，这显然是相对低效的。通过如上分析，我们可以得知关于最优策略的一些信息：即序列F的间隔应该递减。这样对于较高的临界楼层的情况，虽然第一个球尝试的次数不可避免的会比较多，但已经将楼层限定在了一个比较小区间内，这样将减少第二个球的尝试次数。可以随手写出一个符合这种条件的序列F，比如：14 27 39 50 60 69 77 84 90 95 99 100（除了最后一个间隔，）该序列的间隔依次比上一个间隔小1，第一个数取14（或者13），可以大致保证间隔依次减小到1时刚好到100。此时的平均尝试次数为10.39。再比如：12 22 34 45 55 64 72 79 85 90 94 97 99 100（除了第一个间隔，）该序列的间隔依次比上一个间隔小1，且刚好停在100。此时的平均尝试次数为10.35。可以看到这两个序列都给出了比等间隔模型更好的结果，并且很接近我给出的最终结果，表明上述分析是相当合理的。3.还可以有其他的方法，比如穷举法，写出所有100以内递增的序列，但显然实在太多了。还有类似共轭梯度法等传统的最优化方法，虽然可以写出一个矢量（即序列F）F(1) F(2) F(3) ......F(100)该序列可以有重复的数，比如F(20)=F(21)=......=F(100)=100，同时要求单调递增的约束条件。但即便如此，似乎也有一种无从下手的感觉。这正是这个题目有意思的地方，因为很难找到一种特别合适的方法来处理它。4.所以只能另辟蹊径。需要找到一种方法，它应该要能自适应的依据优化的要求，在庞大的参数空间中逐渐搜索到最优解。最终我使用了遗传算法（的思路）（注：本人非计算机专业出身，对于遗传算法更是知之甚少，只是在梅拉妮?米歇尔的《复杂》一书中看到了遗传算法，对其强大的功能以及别样的思路印象很深。之前也没有自己写过相关的算法，就这这个有意思的题目，按照遗传算法的思路，写了一小段程序，势必不入方家之眼，还希望得到专业人士的指点。）非常简单地重复一下我的算法的思路：生成一系列随机的序列，这些序列都符合递增到100的要求；计算每个序列的平均尝试次数，找到最好的两个序列；让这两个序列“杂交”生成子代，即子代序列中每一位数都有50%的几率沿袭“父”或“母”序列中相应位数的数值；子代序列中每一位数有30%的几率发生变异，即数字增加或减少1；对子序列重复步骤2；直到最终收敛在一种（一组）最优的策略上。5.遗传算法的结果是很不错的，大约在几百代就可以给出最优解，对应的平均尝试次数是10.31次。由于遗传的随机性，每次给出的最优结果的策略都略有不同，比如：13 25 36 46 56 64 72 79 85 90 94 96 98 99 100或者14 27 38 48 57 66 73 79 85 90 93 96 98 99 100等序列能给出同样的平均尝试次数。这一系列的最优策略的共同点就是是都有着递减的间隔，以及初始的尝试楼层都是13或者14，与前文的猜想给出的定性考虑一致。补充两点：我将程序运了一晚上，遗传了代，并没有得到更好的结果；另外，遗传算法不是证明，我们没法通过遗传算法得知这究竟是不是最优的解。6.我没法保证我的算法是最好的，甚至不能保证该算法是正确的，这种算法甚至有可能在原则上错过真正最优的策略。又或者有某种非常直接的做法，可以给出最优的解；又或者有某种非常巧妙的做法，可以证明某个解是最优的；又或者还有着更好的***----这些我都不知道。附：matlab代码1. 根据序列F计算各临界楼层的尝试次数的程序：function T=zhihu_floor_result(F,N)
% return try time T for all possible crashing floor
% F is sequence of testing floor number
% N is total floor number
T=zeros(1,N);
for ii=1:N
t1=find(F&ii,1,'last');
t2=ii-F(t1);
T(ii)=t1+t2-(ii==F(t1+1));
2.遗传算法：未免有误，贻笑大方，暂时不贴出来。
经典面试题动规啊。
* m个球，n层楼，最少几次（假设为最坏情况下的最少次数，不是平均次数）
* 能判断从哪层楼开始扔球会坏掉，假设球摔坏的概率与楼层高度无关且每层相等,
* 并且不一定肯定有一层能摔坏
* 递推公式：
* b(m,n) = min{ max{ b(m-1,k-1)+1, b(m,n-k)+1 } }
#include &stdio.h&
int max(const int &a, const int &b){
return a&b ? a :
int min(const int &a, const int &b){
return a&b ? b :
void mball_nfloor(int m, int m);
int main(int argc, char **argv){
fprintf(stdout, "\n**********************mball_nfloor(4, 100)************************\n");
mball_nfloor(4, 100);
fprintf(stdout,
"\n******************************************************************\n");
fprintf(stdout, "\n**********************mball_nfloor(1, 100)************************\n");
mball_nfloor(1, 200);
fprintf(stdout,
"\n******************************************************************\n");
fprintf(stdout, "\n**********************mball_nfloor(4, 1)**************************\n");
mball_nfloor(4, 1);
fprintf(stdout, "\n******************************************************************\n");
//b(m,n) = min{ max{ b(m-1,k-1)+1, b(m,n-k)+1 } }
//n&=1,m&=2,1&=k&=n
//For convenience, we handle m=1, n=0 separately
void mball_nfloor(int m, int n){
if(m&=0 || n&=0)
int result[m+1][n+1];
int temp_min = n+1;
int temp_max = 0;
//for n==0 and n==1
for(int i=0;i&=m;i++){
result[i][0] = 0;
result[i][1] = 1;
//for m==0 and m==1
for(int i=0;i&=n;i++){
result[1][i] =
result[0][i] = 0;
if(m&1 && n&1){
//start from 2 balls
for(int a=2;a&=m;a++){
//start from 1 floors
for(int i=1;i&=n;i++){
for(int k=1;k&=i;k++){
temp_max = max(result[a-1][k-1]+1, result[a][i-k]+1);
temp_min = min(temp_min, temp_max);
result[a][i] = temp_
temp_min = n+1;
for(int i=1;i&=m;i++){
fprintf(stdout, "\n======%d个球，%d层，每种楼层各种丢球方法中最坏情况下的最少丢球次数======\n", i, n);
for(int j=1;j&=n;j++){
fprintf(stdout, "%d\t", result[i][j]);
fprintf(stdout, "\n");
因为只有两个球，所以要保证有解的情况下，策略是，利用第一个球，用尽量少的次数找到一个（不碎－碎）区间，利用第二个球，找出临界值。所以重点在于如何利用第一个球找出最小空间，如在50层试一次，如果50层球碎了，那么第二个球就必须从第一层开始一层一层递进，才能找到临界层，否则如第一层未碎，直接第三层尝试，第三层碎了，则无法得知临界值是2还是3.
此时，此题变为，在如题所述的条件下，把（0－100）分割成a个100/a个连续数字的区间，总次数为（a＋100/a）次（100/a，为总10个集合需搜索次数的平均值），当a＝10时，该值最小，值为20，即第一个球10层10层地递增时，最多19次（9个截点即可将分出10个线段），即可找到临界值。
即第一个球从10层开始，如果10层碎了，则第二个球从第一层开始逐层往上找到临界值。如果10层没碎，则第一个球在第20层开始尝试，依次递归到90层。ps-------------------------------------------------------------------------感谢后来的同志指出问题，因为有初值的存在（就是落在不同区间内段内的破碎层，在划分区段时有实际已经使用的初始值不同情况出现），所以到了切割10段后，本题就由算法题变为了概率题，，可以缩小落在高低区间之间的次数差距（平均法是各个区间从低到高依次递增），来达到优化期望值，最理想的方案，应该是10个区间，每个区间内的期望次数也是相等，相当于方差为0时，效果最优（大学时期没好好学概率论，哈哈）。我在估算不会超过11时，就忽略了初值与期望优化，实际上。当此时N足够大时，理论期望可接近N的平方根，最优方法的期望次数能做到比平均法少最多到1次（概率方面的知识储备流失严重，没法做严谨的公式论证，希望有更严谨的论证）
玻璃球在第一次落地之后已经不是原来的玻璃球了吧？
早年的信息学国家集训队论文《鹰蛋》就是这道题目的最优解动态规划
三个假设：由于是100层的大楼，所以假设地基是水泥地等坚硬是合理的；由于题目没有给出特别说明，所以假设玻璃球是普通玻璃球是合理的；假设玻璃球自由下落，没有初速度；三个先验结论：基于上述三个假设，认为在五楼及以上玻璃球一定碎裂(小时候玩弹珠游戏，力气大的时候能一下把弹珠撞烂碎裂，若弹珠自由往前滚动，能有十几米，滚动摩擦系数小于一，所以才有这个先验条件)；在一楼高度太低(人身高)一定不会碎裂(力气小打弹珠不会裂)；由于玻璃珠的滚动，在楼上扔下玻璃珠若没碎裂就滚弹到远处再也找不到，无法用第二次，若碎裂则能找到，从而判断是否碎裂；那么只剩下二三四楼，第一次选择3楼：1～若第三层不碎裂，则用第二个玻璃球检验第四层；若第四层不碎裂，说明临界楼层是五层；若第四层碎裂，说明临界楼层是四楼；2～若第三层碎裂则检验二楼是否碎裂，若不碎裂说明临界楼层是三层；若碎裂说明临界楼层是二层；于是整个方法用到的玻璃球的期望是两个，刚好用完所给条件完美解决问题。至于一百层，呵呵，被绕进去的孩子不少。转载请注明出处！
楼上很多想法，可能很正确。我思考了很久觉得***应该为5次操作吧，不知道和 的意思是否相同。这个问题假设大概上面都已经说了，还要补充一个，100中玻璃球必碎。最优策略的理解为【通过最少次操作必然可以遍历在所有情况下解决问题】。这个问题先变形一下，楼层数为N,问题变化为每层楼对应信号一个信号（相同结果信号相同），那么问题变成求信号突变发生在那一层楼。之后每次操作用1个探针探测得到一个信号，最坏的情况应该是2**n&=N，n为探测到突变值。现在情况变为你有两个探针，那么应该情况是3**n&=N，n为探测到突变值。3**5=243，3**4=81，虽然这个情况下和上面问题不同，有可能有一个探测器会消失，问题由两个探测器变为1个探测器的情况，但是我想可能依然是可以实现最优策略的，虽然我现在还没有想明白。
已有帐号？
无法登录？
社交帐号登录第一章 土方工程试题及***_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
第一章 土方工程试题及***
上传于||暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩6页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢　　想去100层看看， 求高手解答，去的 第一高楼的朋友告诉下？
楼主发言：2次 发图：0张 | 更多
　　我就在那后面上班。。。。好像不能随便上。。。。。
　　上面有餐厅, 去吃霸王餐就行了　　
　　改装下，变超人飞上去　　
　　@ysjsuhop
18:52:00　　改装下，变超人飞上去　　本帖发自天涯社区手机客户端　　-----------------------------　　刚才打了这个瑞吉酒店这个***，问100层是免费的还是消费？他说100层有个酒吧最低消费158元，从下午17点到凌晨2点，可以观光深圳第一高楼看深圳全市，我操。又说，可以早上10点观光到凌晨2点，买一张100元的观光卷就可以了，我日。[吐血]我要去啊，我就说去找人的，我靠[哼]
　　@深圳上古手游网 可以进 但不能保证能不能出得来
19:01:00　　@深圳上古手游网 可以进 但不能保证能不能出得来　　-----------------------------　　要花钱的
　　有朋友去过了，不要理睬保安，假装是去消费的，可以坐电梯到96楼，可以看到香港，一分钱都不花。
　　变成蜘蛛侠，你去哪里都是FREE滴，
　　你从瑞吉酒店大门进去，会有***妹在那里等着，你说住店的，忘了带卡了，让他帮你刷下卡，有部分电梯只有1和96层的按钮，有部分多一两个楼层，进去时不要东张西望，否则那些***妹或保安会问你住哪间房的。上了96楼就是酒店大堂，也是个观景层，转到后面有几部电梯，有些可以到100层，有些只能向下到房间，下楼是不用刷卡的，原路返回就行了。
　　嘿嘿，这个还真不知道，来我们群呗：，都是一群非常可爱的人喔，没有一大堆的群规，就是开心吹水，HOHO
　　直接坐电梯上去，溜达一圈再下来，当然别穿的别太邋遢
　　请问深圳第一高楼是哪里　　帝王大厦 还是哪里
请遵守言论规则，不得违反国家法律法规回复(Ctrl+Enter)《梦回三国》萌现灵芝塔 是男人就冲100层
发布时间： 14:22
　《梦回三国》专区
　　神秘千年灵芝塔惊现萌三国！为了虏获激萌三国美女们的真心，勇士们快来挑战极限吧！100层冲刺闯关大作战，最终奖励绝对火爆刺激！最开心的穿越，就在《梦回三国》！
　　主城里点击[千年灵芝塔]即可进入塔内进行挑战！《梦回三国》终极测试期间，冲关达到指定等级，还能免费赢黄金宝箱！还等神马？整装待发，冲啊！
　　《梦回三国》终极测试，线上线下精彩无间断，十四大活动好礼送不停！给您惊喜一波又一波！每日登陆还能累积快乐大转盘抽奖次数，大奖IPAD、PSP3000等您抱回家！
　　马上登陆大转盘抽奖&&&&
　　新手上线游戏，元宝、礼券不够用？无需担心！十余种办法让您每天都能免费领元宝和礼券，总数超过80000＋元宝和9000＋礼券哦！参与活动开心乐盛夏，轻轻松松有钱花！
　　元宝、礼券赢取攻略&&&&
　　更多新手指引，就在《梦回三国》新手专题！上线5步教会您独步穿越，笑傲九州！
　　新手引导5步学会穿越&&&&
　　《梦回三国》官方论坛线下精彩延续中！提建议、写攻略，与万千穿越者一同分享激萌三国的快乐每一天！参与活动，还能赢Q币和点卡，更有机会畅游杭州，和策划面对面交流游戏心得！快来参加！
萌现灵芝塔
　　最精彩的穿越，最激萌的三国！终极测试狂欢最后24小时，让一切美好，都停留在穿越大陆！《梦回三国》，给自己的暑假留下一个最难忘的美好纪念！
【延伸阅读】
【看到这篇文章你的心情是？】
【新闻评论】
荆州新闻网欢迎您参与评论......
【更多相关】