|
锁定老帖子 主题：百度二面智力题（破碎临界层）
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-11-03
最后修改：2011-11-03
归纳解法 一共X次 第一次在X层 第二次在Ｘ＋Ｘ－１ 第三次在Ｘ＋Ｘ－１＋Ｘ－２ ．．．． 最后一次 X+X-1+X-2...+1 =>X+X-1+X-2...+1>=100 求的X=14 |
| 返回顶楼 | |
|
发表时间：2011-11-03
lavafree 写道 ku_sunny 写道 在最坏的情况下 最快是8+9次 如果第一个球每层10曾试 如果临界是89层 那么此时是最坏的 因为如果99层 是9+5 后面5是由于有两个球都好的 我可以两层两层的试 如果在最坏的情况下能找出比17次更快的 我就佩服你了
准确的说是9+8，梅十层的试9次，接下来试8次，第89层不用试，玻璃球完好 你不扔？那请问你是怎么知道是89层还是第90层是临界值？ |
| 返回顶楼 | |
|
发表时间：2011-11-03
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次!!!! 当最后折半的时候，两次都碎了，看你咋仍？（96碎，94碎，咋办？） |
| 返回顶楼 | |
|
发表时间：2011-11-03
Shabrave 写道 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次!!!! 当最后折半的时候，两次都碎了，看你咋仍？（96碎，94碎，咋办？） 首先我要说在回答上面的15次以后,我有补充其实最少是14次.按下面顺利扔: 14 ,27, 39, 50, 60, 69, 77, 84, 90, 95 这样只要扔14次. 现在针对你的问题,就按15次的这个来说,(可能你没理解我的意思). 1.现在是92层没坏(注意此时一个球也没坏),我再站在96层扔,如果坏,再按93,94,95扔3次,这样共扔12次;当然如果还没坏,你应该知道我要怎么扔了吧. 2.现在92层坏了,我就从85一层一层扔到91,这样最多共15次. |
| 返回顶楼 | |
|
发表时间：2011-11-03
其实,我想知道的是,不碎的玻璃球会自动回到你的手中吗?
所谓最优是指的什么?试验者需要爬楼和捡玻璃球吗,或者只是在计算机上"扔下"某个球, 获得它是否碎了的输出? |
| 返回顶楼 | |
|
发表时间：2011-11-04
最后修改：2011-11-04
先称称重量，敲碎一个，检测材质，算算冲量，测测地面的材质、形变系数，测测楼层高度，算出一个相对保守的楼层数据，比如20楼，然后拿另一个从18楼或19楼开始验证，最后得到结论。顺利的话撑死三四次知道结果，而且真的只用两个球。
|
| 返回顶楼 | |
|
发表时间：2011-11-04
BuN_Ny 写道 先称称重量，敲碎一个，检测材质，算算冲量，测测地面的材质、形变系数，测测楼层高度，算出一个相对保守的楼层数据，比如20楼，然后拿另一个从18楼或19楼开始验证，最后得到结论。顺利的话撑死三四次知道结果，而且真的只用两个球。
他真的只有两个玻璃球 |
| 返回顶楼 | |
|
发表时间：2011-11-04
2分查找应该是相对于1个球而言，现在有2个球，应该是同时将2个球从不同曾扔下，这样如果你能保证在2个球全都碎或者碎了一个球之后找到那一个临界层，那么应该不是简单的2分法
|
| 返回顶楼 | |
|
发表时间：2011-11-05
呵呵，这其实是一个数列题，公式是：
n + (n-1) + (n-2) + (n-3) + (n-4) + (n-5) + (n-6) + (n-m) <=100 需要保证n与m尽量的接近。 如果先以10分片，大概需要18次，但很明显，18次不是极限。 上面的公式，经过多次化简，再用试错法(大约两三次)，可以得出15是最佳初始值。 答案如下： 15 28 40 51 61 70 78 85 91 96 |
| 返回顶楼 | |
|
发表时间：2011-11-05
最后修改：2011-11-05
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) ........ |
| 返回顶楼 | |
