|
锁定老帖子 主题：百度二面智力题（破碎临界层）
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-10-28
zhanghh321 写道 楼主 那个面试的人到底给你说最少几次了没有啊?
哈哈.其实是这样的,之前唠了一个多小时的专业相关知识.然后,他说因为那天一个吉林大学的朋友和一个大连理工大学的朋友来不了,就开始给出了三道这类的智力题.这些题都是他在网上现找的,告诉我题,然后他自己在那边现看答案,再引导我思考. 关于这道题,他说是14次最优,好像提到了动态开平方分法,没听懂. 这结果并不重要,百度面试给我的感觉是:他们想看到的应聘者的思考过程,不会他们还会引导你.给人的感觉很好的说. 
|
| 返回顶楼 | |
|
发表时间：2011-10-28
yangguo 写道 yeshaoting 写道 gtssgtss 写道 不知道lz有没有忽略一个事实,就是只剩一个的时候没有取巧的丢法,只能一层一层丢
假设2未破,4破了,无法得知3到底破不破,因为只剩一个,4破了的就无法测试3了 面试时,本人采用二级分块查找是基于对临界层的如下理解: 临界层可以是刚好碎的那层,也可以是未碎的那层(即刚好碎的上一层). 因此,个人认为在二级分块中n块与n+1块都包含二层,n块第一层未碎,n+1块第二层碎的情况下,n块第二层即为临界层. 假设2未破,4破了. 若3破,则3是刚好破的临界层;若3未破,则3是刚好未破的临界层. 兄弟，已经没球让你继续破了！！ 若3破,则3是刚好破的临界层;若3未破,则3是刚好未破的临界层. 这是一个推断.将这层做为临界层.它破与不破不了解,但是可当作是临界层. 这是我当时面试时瞎想还瞎说的,很可能不对.见谅.
面试官好像提到的是动态平方分法. gtssgtss 写道 分10块是可以的,但是2级分块不成立的
分10块的时候,举个例子 第一次扔10破了,假设剩下一个的时候2没破的话不能扔4,因为如果4破了,不能确认到底界限在3还是4 剩一个瓶子的时候没的取巧,问题就在于第一次分块,开平方(就是分10层),2分,黄金分割,动态开平方分法等 |
| 返回顶楼 | |
|
发表时间：2011-10-28
最后修改：2011-10-28
我思考了一下,这道题可以一般化
对m层,有k个球,最少的搜索次数 an=1 bn=Sa(求和) cn=Sb ... kn=Sj 当Sk>m,且其中Sa,Sb,Sc,Sd....Sk的项数都相等时,Sk的项数为最少搜索次数 k=1时全为1,就是一次一层 k=2时看J_wp的帖子 看看k=3的情况 假设k=3,而m是一个比较大的数,用第一个球分割在105的位置时,第一个球破碎,那么就转化为k=2的问题了,第一个球在105没破的话,我们去找第一个球的第二次测试点,在105之内,我们需要14次找到位置,那么第二次测试点,我们只能用13次找位置了,于是下一个点就是105+(1+...+13)=105+91,再下一点就是105+91+78... |
| 返回顶楼 | |
|
发表时间：2011-10-28
最后修改：2011-10-28
那按楼主的意思。
我上回回答的就已经也可以了。只要10次！ 如果就临界点可以模灵两可的话，。 昨天和同事讨论了一哈。目前来说得到的最优是最多10次确认。 摔的顺序为： 第一分层是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楼就可以作为临界层。 以上情况共10次。 下面的情况类推： 36楼时摔破（此时确认19楼以下都未破，只需要计算21，23，25，27，29，31，33，35，最坏情况下34楼会作为临界楼。）........................ 51楼时摔破........................ ................... 99楼时摔破....................... 总的算下来，最坏的情况就是摔10次就能确认。 以上以上都是按照楼主的临界楼概念来说的！@ |
| 返回顶楼 | |
|
发表时间：2011-10-29
不是只有两颗玻璃球吗 一层一层摔上去肯定行了 没说要省功夫
|
| 返回顶楼 | |
|
发表时间：2011-10-29
shermenn 写道 不是只有两颗玻璃球吗 一层一层摔上去肯定行了 没说要省功夫
用什么最优策略知道这个临界的层是第几层 |
| 返回顶楼 | |
|
发表时间：2011-10-29
icanfly 写道 那按楼主的意思。
我上回回答的就已经也可以了。只要10次！ 如果就临界点可以模灵两可的话，。 昨天和同事讨论了一哈。目前来说得到的最优是最多10次确认。 摔的顺序为： 第一分层是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楼就可以作为临界层。 以上情况共10次。 下面的情况类推： 36楼时摔破（此时确认19楼以下都未破，只需要计算21，23，25，27，29，31，33，35，最坏情况下34楼会作为临界楼。）........................ 51楼时摔破........................ ................... 99楼时摔破....................... 总的算下来，最坏的情况就是摔10次就能确认。 以上以上都是按照楼主的临界楼概念来说的！@ 那我当时的理解就是错的呗~~ 还好没因为这个把我Pass掉.
|
| 返回顶楼 | |
|
发表时间：2011-10-29
cttnbcj 写道 gtssgtss 写道 cttnbcj 写道 joe9i0 写道 cttnbcj 写道 一群NX啊，几年的题，还百度。。。玩烂掉恶劣，谷歌到TX到百度。。。。百度也够丢人的~~
什么逻辑? 别人没见过的题,就你见过,就你不脑残? 阿基米德通过容积重量密度计算出国王王冠的含金量...中学物理都学过...
假设要是你没学过,几千年前的事你都不知道,你是不是巨脑残啊??? 这智商。。。关阿基米德鸟事。。。 这个题是N年前的面试题，也是出自趣味数学之类的书。。。很多公司弄过这题，没看过书这个也对，可是网络上遍地都是。。。要是这题能对可以进百度。。。。。。。。。。。。真是疯了 阿基米德是从无到有。。。想到计算方法 可是这个问题，你没见过的话，难道不会网上上看下嘛。。。。。。一群人，还说出二分，分块，半折。。。之类。。。。。这个才是在秀自己的智商~~~  要讨论问题请来,要秀下限请走,你就算在网络上找到100个地方有这题,也不如lz进入2面亲临这个题面个妹啊。二面还出网络上N久的题。。。也好意思拿出来~~~~~至少题目要有所变化吧。。。。否则考个坠子去啊 吃葡萄吧你，有本事你也到百度2面啊 |
| 返回顶楼 | |
|
发表时间：2011-10-29
cttnbcj 写道 gtssgtss 写道 cttnbcj 写道 joe9i0 写道 cttnbcj 写道 一群NX啊，几年的题，还百度。。。玩烂掉恶劣，谷歌到TX到百度。。。。百度也够丢人的~~
什么逻辑? 别人没见过的题,就你见过,就你不脑残? 阿基米德通过容积重量密度计算出国王王冠的含金量...中学物理都学过...
假设要是你没学过,几千年前的事你都不知道,你是不是巨脑残啊??? 这智商。。。关阿基米德鸟事。。。 这个题是N年前的面试题，也是出自趣味数学之类的书。。。很多公司弄过这题，没看过书这个也对，可是网络上遍地都是。。。要是这题能对可以进百度。。。。。。。。。。。。真是疯了 阿基米德是从无到有。。。想到计算方法 可是这个问题，你没见过的话，难道不会网上上看下嘛。。。。。。一群人，还说出二分，分块，半折。。。之类。。。。。这个才是在秀自己的智商~~~ 要讨论问题请来,要秀下限请走,你就算在网络上找到100个地方有这题,也不如lz进入2面亲临这个题面个妹啊。二面还出网络上N久的题。。。也好意思拿出来~~~~~至少题目要有所变化吧。。。。否则考个坠子去啊 实在看不下去了。 这位仁兄，你脸上长的不是豆豆，是满脸的喷嘴，喷出来的东西大家就不用说了。。。。 做人要厚道，莫装X，装X会被雷劈！ |
| 返回顶楼 | |
|
发表时间：2011-10-29
最后修改：2011-10-29
对于有N层，K个球，分成K次分块。即每次投球时的临界点从低处到高处依次是N的K次根(假设不碎)，N的K次根的2次方(假设不碎)，N的K次根的3次方(假设不碎)，...，N的K次根的K-1次方(假设不碎)，最后缩小范围到某一个N的K次根长度范围内，最多搜索的次数总共是K倍N的K次根。
|
| 返回顶楼 | |
