|
锁定老帖子 主题：百度二面智力题（破碎临界层）
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-10-24
最后修改：2011-10-28
题1 有一栋100层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略知道这个临界的层是第几层？？？ 顺序查找：从1层往100层试 题2 有一栋100层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略知道这个临界的层是第几层？？？ 二分查找：从50层试一次，若50层破，则从1层顺序查找；若50层未破，则在75层试一次。类推。 分块查找：将100层，以10层为一块分成10块。第一个玻璃球用来从第一块开始顺序查找到块，第二个玻璃球用来从块内第一个开始顺序查找。 二级分块查找：将100层，以10层为一块分成10块，另外，将10层以2层为一块再分成5块，再利用上述分块查找的方法找出临界层。二级分块以2层为一块的目的是，顺序查到某块时，若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层。
大家怎么看~~ 面试时,本人采用二级分块查找是基于对临界层的如下理解: 临界层可以是刚好碎的那层,也可以是未碎的那层(即刚好碎的上一层). 因此,个人认为在二级分块中n块与n+1块都包含二层,n块第一层未碎,n+1块第二层碎的情况下,n块第二层即为临界层.
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2011-10-24
你自己google一下吧，最优策略是最多14次就可以的
|
| 返回顶楼 | |
|
发表时间：2011-10-24
JohnnyJian 写道 你自己google一下吧，最优策略是最多14次就可以的
嗯... 二级分块查找就是14次 |
| 返回顶楼 | |
|
发表时间：2011-10-27
弱弱的问一句..总共就两个都摔碎了...怎么二分
|
| 返回顶楼 | |
|
发表时间：2011-10-27
ansjsun 写道 弱弱的问一句..总共就两个都摔碎了...怎么二分
二分只是一个快速减半的条件，当第一个球碎时可以判断破碎临界楼层是在1-50还是51-100之间，然后再在1-50或者51-100之间用逐层向上试探进行。当第二个球碎时，证明该楼层是临界点。第一个球碎明显加速了查找，但是第二球就得一个一个逐层上向寻找，比较费时。 |
| 返回顶楼 | |
|
发表时间：2011-10-27
简单的二分查找而已。
|
| 返回顶楼 | |
|
发表时间：2011-10-27
14次？ 怎么二分的啊
|
| 返回顶楼 | |
|
发表时间：2011-10-28
lzrzhao 写道 14次？ 怎么二分的啊
我认为是: 二级分块查找：将100层，以10层为一块分成10块，另外，将10层以2层为一块再分成5块，再利用上述分块查找的方法找出临界层。二级分块以2层为一块的目的是，顺序查到某块时，若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层。 |
| 返回顶楼 | |
|
发表时间：2011-10-28
yawei 写道 简单的二分查找而已。
简单二分貌似得不到14次吧.至少得先分下块呀. 简单二分最坏50次,分块后再二分19次. |
| 返回顶楼 | |
|
发表时间：2011-10-28
yeshaoting 写道 lzrzhao 写道 14次？ 怎么二分的啊
我认为是: 二级分块查找：将100层，以10层为一块分成10块，另外，将10层以2层为一块再分成5块，再利用上述分块查找的方法找出临界层。二级分块以2层为一块的目的是，顺序查到某块时，若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层。 那我问你，1000层的时候是多少次，10000层的时候又是多少 |
| 返回顶楼 | |
