|
锁定老帖子 主题：百度二面智力题（破碎临界层）
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-10-28
icanfly 写道 昨天和同事讨论了一哈。目前来说得到的最优是最多11次确认。
摔的顺序为： 第一分层是19，36，51，64，75，84，91，96，99 第二分层为每隔两楼 例如： 若19楼时摔破，则从下往上两楼两楼地摔： 2，4，6，8，10，12，14，16，18 这种情况下，因为在19楼已经摔了一次，且摔破。记+1 最坏情况在18楼破（2，4，6，8，10，12，14，16均未破，18破）共摔+9次。 因为在18破的情况下不能确定是不是17也破，故在17也摔一次确认。故+1次。 以上情况共11次。 下面的情况类推： 36楼时摔破（此时确认19楼以下都未破，只需要计算21，23，25，27，29，31，33，35，最坏情况下34楼会作为最后一次确认楼。）........................ 51楼时摔破........................ ................... 99楼时摔破....................... 总的算下来，最坏的情况就是摔11次就能确认。 请问第2个球两楼两楼往上扔,我就说现在在第2楼碎了..请问,1楼是临界还是2楼? |
| 返回顶楼 | |
|
发表时间：2011-10-28
最后修改：2011-10-28
J_wp 写道 icanfly 写道 昨天和同事讨论了一哈。目前来说得到的最优是最多11次确认。
摔的顺序为： 第一分层是19，36，51，64，75，84，91，96，99 第二分层为每隔两楼 例如： 若19楼时摔破，则从下往上两楼两楼地摔： 2，4，6，8，10，12，14，16，18 这种情况下，因为在19楼已经摔了一次，且摔破。记+1 最坏情况在18楼破（2，4，6，8，10，12，14，16均未破，18破）共摔+9次。 因为在18破的情况下不能确定是不是17也破，故在17也摔一次确认。故+1次。 以上情况共11次。 下面的情况类推： 36楼时摔破（此时确认19楼以下都未破，只需要计算21，23，25，27，29，31，33，35，最坏情况下34楼会作为最后一次确认楼。）........................ 51楼时摔破........................ ................... 99楼时摔破....................... 总的算下来，最坏的情况就是摔11次就能确认。 请问第2个球两楼两楼往上扔,我就说现在在第2楼碎了..请问,1楼是临界还是2楼? 算错了。不对。。。两个球不能确认。我忽略了一个情况就是在确认那次时，已经要摔第三个球了。。。。。囧。。。。 |
| 返回顶楼 | |
|
发表时间：2011-10-28
引用 二级分块查找：将100层，以10层为一块分成10块，另外，将10层以2层为一块再分成5块，再利用上述分块查找的方法找出临界层。二级分块以2层为一块的目的是，顺序查到某块时，若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层。 请问楼主，你这个二级分块由我刚才的错误回答想到了，有问题啊？ 引用 若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层
如10层未破，12层破，你不能说明11层是临界层！！！ 因为球有可能在11层破。。。但是如果最后一个球在12层破了，，那你已经用完两个球，而现在还根本无法确认11楼是否会摔碎啊。。。。 大家认为呢。 |
| 返回顶楼 | |
|
发表时间：2011-10-28
icanfly 写道 引用 二级分块查找：将100层，以10层为一块分成10块，另外，将10层以2层为一块再分成5块，再利用上述分块查找的方法找出临界层。二级分块以2层为一块的目的是，顺序查到某块时，若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层。 请问楼主，你这个二级分块由我刚才的错误回答想到了，有问题啊？ 引用 若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层
如10层未破，12层破，你不能说明11层是临界层！！！ 因为球有可能在11层破。。。但是如果最后一个球在12层破了，，那你已经用完两个球，而现在还根本无法确认11楼是否会摔碎啊。。。。 大家认为呢。 前面我给出求的方法,最优策略应该是14次. 通用数学表达式求解公式为 1+2+3+...+n >= K (K为楼层数) 求解出的n的最小值即为最优策略的次数. |
| 返回顶楼 | |
|
发表时间：2011-10-28
yangguo 写道 都不知一群二百五在讨论什么，答案还五花八门，错上加错。楼主早就说出答案了，就是二级分块查找。
智商要135以上能看懂以下等式： 9 + 4 + 1 = 14 呵呵... |
| 返回顶楼 | |
|
发表时间：2011-10-28
joe9i0 写道 cttnbcj 写道 一群NX啊，几年的题，还百度。。。玩烂掉恶劣，谷歌到TX到百度。。。。百度也够丢人的~~
什么逻辑? 别人没见过的题,就你见过,就你不脑残?  阿基米德通过容积重量密度计算出国王王冠的含金量...中学物理都学过...
假设要是你没学过,几千年前的事你都不知道,你是不是巨脑残啊??? 这智商。。。关阿基米德鸟事。。。 这个题是N年前的面试题，也是出自趣味数学之类的书。。。很多公司弄过这题，没看过书这个也对，可是网络上遍地都是。。。要是这题能对可以进百度。。。。。。。。。。。。真是疯了 阿基米德是从无到有。。。想到计算方法 可是这个问题，你没见过的话，难道不会网上上看下嘛。。。。。。一群人，还说出二分，分块，半折。。。之类。。。。。这个才是在秀自己的智商~~~ |
| 返回顶楼 | |
|
发表时间：2011-10-28
cttnbcj 写道 joe9i0 写道 cttnbcj 写道 一群NX啊，几年的题，还百度。。。玩烂掉恶劣，谷歌到TX到百度。。。。百度也够丢人的~~
什么逻辑? 别人没见过的题,就你见过,就你不脑残? 阿基米德通过容积重量密度计算出国王王冠的含金量...中学物理都学过...
假设要是你没学过,几千年前的事你都不知道,你是不是巨脑残啊??? 这智商。。。关阿基米德鸟事。。。 这个题是N年前的面试题，也是出自趣味数学之类的书。。。很多公司弄过这题，没看过书这个也对，可是网络上遍地都是。。。要是这题能对可以进百度。。。。。。。。。。。。真是疯了 阿基米德是从无到有。。。想到计算方法 可是这个问题，你没见过的话，难道不会网上上看下嘛。。。。。。一群人，还说出二分，分块，半折。。。之类。。。。。这个才是在秀自己的智商~~~ 火气好大啊，， 我以前也没有见过类似的题，这次看到有个人给出的算法还是不错的，学习了。 |
| 返回顶楼 | |
|
发表时间：2011-10-28
cttnbcj 写道 joe9i0 写道 cttnbcj 写道 一群NX啊，几年的题，还百度。。。玩烂掉恶劣，谷歌到TX到百度。。。。百度也够丢人的~~
什么逻辑? 别人没见过的题,就你见过,就你不脑残? 阿基米德通过容积重量密度计算出国王王冠的含金量...中学物理都学过...
假设要是你没学过,几千年前的事你都不知道,你是不是巨脑残啊??? 这智商。。。关阿基米德鸟事。。。 这个题是N年前的面试题，也是出自趣味数学之类的书。。。很多公司弄过这题，没看过书这个也对，可是网络上遍地都是。。。要是这题能对可以进百度。。。。。。。。。。。。真是疯了 阿基米德是从无到有。。。想到计算方法 可是这个问题，你没见过的话，难道不会网上上看下嘛。。。。。。一群人，还说出二分，分块，半折。。。之类。。。。。这个才是在秀自己的智商~~~  要讨论问题请来,要秀下限请走,你就算在网络上找到100个地方有这题,也不如lz进入2面亲临这个题
|
| 返回顶楼 | |
|
发表时间：2011-10-28
J_wp 写道 zhanghh321 写道 J_wp 写道 gtssgtss 写道 如果只求最坏情况要好的话,第一次可以这么扔
15,28,40,51,61,70,78,85,91,97 和我想法一样,不过你的顺利貌似有点问题.我的是: 15, 29, 42, 54, 65, 75, 84, 92. (如果前七次第一个球不坏就这么扔; 如果坏了就在那个区间顺序扔) 这样最坏的情况也就扔15次. 当然如果再92层还不坏就折半扔次,这个肯定比15次少. 所以,最优策略是15次!!!! 这个方法挺好的 不过这个15这个数字怎么得到的呢？ 为啥不是16 或者14呢 其实算法思想就是 递减分块. 我们可以转成数学题来做. (1+2+3+...+n) >= 100 解为要求的值n. 为什么要这样转换大家可以自己思考下. 感觉不是这样的饿。。。 按照14次的算法，最后一次递减不是1 应该是6（1-->97） 因此 应该是(6+7+8+...+n) >= 100 而且也不能用>=这个符号，应该是哪个最接近100 不知道这样想对不对啊 |
| 返回顶楼 | |
|
发表时间：2011-10-28
zhanghh321 写道 phk070832 写道 ansjsun 写道 弱弱的问一句..总共就两个都摔碎了...怎么二分
1.摔碎一个还有一个 2.对于只有2层作为选择，两个都摔碎了，那么答案不是显而易见吗。 我目前感觉javaeye上的人很神秘： 1.感觉很笨。 2.感觉很聪明。 不知道那个方面是装的。 我看了这个解释以后还是没有明白啊 假如在50层碎了，然后应该是去25层啊，如果再碎了呢。 那就没有球了啊 怎么在继续下去啊 参考楼主 二级分块查找 |
| 返回顶楼 | |
