|
锁定老帖子 主题：百度二面智力题（破碎临界层）
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-10-28
最后修改：2011-10-28
J_wp 写道 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次!!!! 再想了下...可以只要14次...按下面扔. 14 ,27, 39, 50, 60, 69, 77, 84, 90, 95 看错,会摔碎,那的确是这样 |
| 返回顶楼 | |
|
发表时间：2011-10-28
yeshaoting 写道 lzrzhao 写道 14次？ 怎么二分的啊
我认为是: 二级分块查找：将100层，以10层为一块分成10块，另外，将10层以2层为一块再分成5块，再利用上述分块查找的方法找出临界层。二级分块以2层为一块的目的是，顺序查到某块时，若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层。 "若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层" 可你还是确定不了上一块第二层是否会破阿？ |
| 返回顶楼 | |
|
发表时间：2011-10-28
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呢 |
| 返回顶楼 | |
|
发表时间：2011-10-28
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呢 我测试了一下14， 这样的话就是 14 27 39 50 60 69 77 84 90 95 99 这样算下来最多14次就可以了啊 |
| 返回顶楼 | |
|
发表时间：2011-10-28
cttnbcj 写道 一群NX啊，几年的题，还百度。。。玩烂掉恶劣，谷歌到TX到百度。。。。百度也够丢人的~~
什么逻辑? 别人没见过的题,就你见过,就你不脑残?  阿基米德通过容积重量密度计算出国王王冠的含金量...中学物理都学过...
假设要是你没学过,几千年前的事你都不知道,你是不是巨脑残啊??? |
| 返回顶楼 | |
|
发表时间：2011-10-28
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呢 其实要说怎么得到很难说,只能是分情况讨论. 后面通过再比较.其实还可以少一次..最优策略是14次. |
| 返回顶楼 | |
|
发表时间：2011-10-28
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. 为什么要这样转换大家可以自己思考下. |
| 返回顶楼 | |
|
发表时间：2011-10-28
最后修改：2011-10-28
我错了。。。
|
| 返回顶楼 | |
|
发表时间：2011-10-28
最后修改：2011-10-28
还真是递归折半查找 从小的层开始 没碎可以继续摔
|
| 返回顶楼 | |
|
发表时间：2011-10-28
最后修改：2011-10-28
不对。。不对。。
|
| 返回顶楼 | |
