|
锁定老帖子 主题：百度二面智力题（破碎临界层）
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-11-01
这个破碎临界层 是指这层会破 还是不会破？
|
| 返回顶楼 | |
|
发表时间：2011-11-01
J_wp 写道 请按你这个.2个球扔4次可以确定多少层?
10层 |
| 返回顶楼 | |
|
发表时间：2011-11-01
public static long n(long times, long balls){
if(balls>times){
return n(times,times);
}
if(balls == 1L){
return times;
}else{
balls--;
times--;
long sum = 1L;
while(times>0){
sum += 1L + n(times, balls);
times--;
}
return sum;
}
}
是这样子的么? |
| 返回顶楼 | |
|
发表时间：2011-11-01
gtssgtss 写道
public static long n(long times, long balls){
if(balls>times){
return n(times,times);
}
if(balls == 1L){
return times;
}else{
balls--;
times--;
long sum = 1L;
while(times>0){
sum += 1L + n(times, balls);
times--;
}
return sum;
}
}
是这样子的么? 就是这个样子 |
| 返回顶楼 | |
|
发表时间：2011-11-01
最后修改：2011-11-01
我的理解就是解一个方程式 2个球，100层。
n+(n-1)+(n-2)+(n-3)+(n-4).....<100层 如果是三个球，就是多一层循环，将前一次算出来的N再代入100 然后再加上100/n取整，球再多就可以循环此算法。 |
| 返回顶楼 | |
|
发表时间：2011-11-02
我抛个砖
能不能根据什么物理公式计算出这个临界点，一些外界的因素不考虑，例如什么风向，风速，地面的材质，球的重量是可以知道的，在球的某一点（也就是受力面）压强大于多少玻璃球就会碎，就跟玻璃的熔点是多少一个意思，然后计算在什么高度能达到这个值 说的不对不要抽我啊，我只是把我的想法说出来 |
| 返回顶楼 | |
|
发表时间：2011-11-02
最后修改：2011-11-02
vissalan 写道 计算在什么高度能达到这个值
|
| 返回顶楼 | |
|
发表时间：2011-11-02
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的算法导论公开课 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] 这部分是怎么推导出来的?第一个等号指哪个？第二个等号又是指哪个？ |
| 返回顶楼 | |
|
发表时间：2011-11-02
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. |
| 返回顶楼 | |
|
发表时间：2011-11-03
都说了这是智力题，我觉得应该抛弃程序员的固定思维。
只有2个球的前提下，只有在保证至少有一个球不破的前提下，才能找到临界点 答案应该是2,4,6,8....这样上去。 |
| 返回顶楼 | |
