|
锁定老帖子 主题：百度二面智力题（破碎临界层）
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-11-05
对于第一个每个球。只要不破就认为其还可以使用。第一个球用在1，2，4，8等的2指数次方所在楼层来做实验。在破和不破两次实验之间的楼层用第二球从下到上一层一层做实验。直到球破了为止。就可又求出临界层了。
|
| 返回顶楼 | |
|
发表时间：2011-11-07
hexh2003 写道 jellyfish 写道 hexh2003 写道 不均分块:
分为m块,每块有Cm层楼 该问题等同于: C1+C2+C3+...+Cm=n时,求集合{i+Ci|i∈[1,m]}中的最大值何时最小. 假设当k∈[1,m]时,k+Ck为该集合中的最大值,则: 任意p∈[1,m]有k+Ck≥p+Cp ==>Cp≤Ck+(k-p) 则:C1+C2+C3+...+Cm≤mCk+(k-1)+(k-2)+...+(k-m) mCk+(k-1)+(k-2)+...+(k-m)=mCk+(k-1)k/2-(k-m-1)(k-m)/2 =mCk+km-m(m+1)/2 mCk+km-m(m+1)/2≥n Ck+k≥n/m+(m+1)/2≥2*(n/m)^0.5*[(m+1)/2]^0.5 第一个等号成立条件:Cp=Ck+(k-p) 即Cm=Cm-1-1 第二个等号成立条件:n=m(m+1)/2 m=[((8n+1)^0.5-1)/2] 当n=100时求得m=14,但m=14时n=105,所以舍弃2块C1=1,C2=2,并且C3=1 由下到上每块的层数分别为:14,13,12,11,10,9,8,7,6,5,4,1 最坏情况的次数为:i+Ci-1=14 蛋疼的早晨...... 上上周去baidu面试的,看来没戏了. 面试之前看了一个星期的算法,以前不知道栈,堆为何物,呵呵,可惜一题没问啊... http://v.163.com/special/opencourse/algorithms.html MIT的算法导论公开课 I like this logic. There is a minor problem: C1+C2+C3+...+Cm=n时,求集合{i+Ci|i∈[1,m]}中的最大值何时最小. should be C1+C2+C3+...+Cm=n时,求集合{(i-1)+Ci|i∈[1,m]}中的最大值何时最小. Then eventually, we should have mCk+(k-1)m-m(m-1)/2≥n All Ck + (k-1) are the same in the worst case, and so they are just m in worst case. Now we have m^2 - m(m-1)/2 >= n This means m(m+1)/2 >=n. The left side is just 1 + 2 + ... + m. The rest follows through my blog. 是的，是(i-1)+Ci,求解过程每个都写-1麻烦啊，所以省去了。 得去结果时加上了-1:"最坏情况的次数为:i+Ci-1=14" 无聊时又想了一下3个球和更多球的情况: 记S(k,m)为k个球，扔m次，最多能确定的层数,则有: S(k,m)=S(k-1,1)+S(k-1,2)+...+S(k-1,m-1)+m 证明略 
S(0,m)=0 S(1,m)=m S(2,m)=m(m+1)/2 S(3,m)=m(m-1)(m+1)/(2*3)+S(1,m) S(4,m)=(m-2)(m-1)m(m+1)/(2*3*4)+S(2,m) S(5,m)=(m-3)(m-2)(m-1)m(m+1)/(2*3*4*5)+S(3,m) S(6,m)=(m-4)(m-3)(m-2)(m-1)m(m+1)/(2*3*4*5*6)+S(4,m) ........ break the formula so others can understand it: S(k-1, m-1) + 1 is for C1 S(k-1, m-2) + 1 is for C2 .... Good work!!! |
| 返回顶楼 | |
|
发表时间：2011-11-07
如果球是 山寨的，1楼下去都会碎我看你们 分，你们是球太多了。
因该引入物理分析， 上去100层率一个球下来，看看碎到什么程度，通过物理学，分析硬度，得到大概的一个临界层，在在这个界层率一个球下来校对， 必须保证两次球率坏了的可能。 |
| 返回顶楼 | |
|
发表时间：2011-11-08
我觉得这个就是求100/x + x的最小值（0<x<100），然后把最小值减1，就是最少的次数。应该是按10来分吧，19次。
|
| 返回顶楼 | |
|
发表时间：2011-11-08
搂主的二级分块法。如果临界点是在第10大块的话，9次后，手里还有2个瓶子 楼层剩下10层 4＋1是可以找到的。。。
可是如果要是临界点在第9大块的话。。。9次后，手里有2个瓶子，但楼层剩下19层 4＋1好像就找不到了啊？ |
| 返回顶楼 | |
|
发表时间：2011-11-09
2个球14次是没有什么问题的，随便google下就可以找到答案。
看着大家讨论的这么热烈，给大家加点难度，用3个球如何用最少的次数找到100层里正好摔碎的那一层？ |
| 返回顶楼 | |
|
发表时间：2011-11-09
yeshaoting 写道 lzrzhao 写道 14次？ 怎么二分的啊
我认为是: 二级分块查找：将100层，以10层为一块分成10块，另外，将10层以2层为一块再分成5块，再利用上述分块查找的方法找出临界层。二级分块以2层为一块的目的是，顺序查到某块时，若此块第一层破了，而上一块第一层未破，则说明上一块第二层是临界层。 分块之后第一个球破了就不能再分块了吧。比如说第一个球在80层碎了，那第二个球只能从71开始一层一层试啊。。。。你如果从72开始，那72碎了，你就不知道到底是71还是72是临界了。。。 |
| 返回顶楼 | |
|
发表时间：2011-11-09
zha_zi 写道 ku_sunny 写道 在最坏的情况下 最快是8+9次 如果第一个球每层10曾试 如果临界是89层 那么此时是最坏的 因为如果99层 是9+5 后面5是由于有两个球都好的 我可以两层两层的试 如果在最坏的情况下能找出比17次更快的 我就佩服你了
89是最坏结果 你是在第九次才能测试出89层是临界点 应该是18次把 是18次 我大意了 |
| 返回顶楼 | |
|
发表时间：2011-11-10
惭愧~惭愧
|
| 返回顶楼 | |
|
发表时间：2011-11-11
假设最多试验n次,那么第一次试验n层就好了,大不了是最差结果.
以此类推,每试验一次,再选取下一个可能达到最差结果的位置. |
| 返回顶楼 | |
