百度二面智力题（破碎临界层）

如果再加上这个球的脆弱度，就是说这个球摔一次，就脆弱10%之类，这个题就更有意思了

一看到算法我就头晕

智商不够  求解释

第二个摔碎了，表示找到了临界点。所以就不用再查了

我可以推导出来3个球，4个球，5个球的状态，所以我很肯定我的算法是对的

让我先把题目确认一下，我做这题的前提是
1.第1层也会破
2.第100层也可能不破
因此，那些所谓的从第2层开始计算或者忽略最后一层在我这里根本不考虑

做这题，只要搞清楚下面2个问题就好
1.问：如果有无限个球，那么n次最多可以确认多少层？
答：2^n-1
2.问：只允许扔3次，能确认多少层？
答：6

只要搞清楚为什么3次是6层而不是7层，答案就很明朗了

不均分块:
分为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的算法导论公开课

很多人还在考虑均等分块。。。。  估计是我说的不明确，均等分块纯粹就是考虑楼层只有100层的情况，如果是1w，100w层试试看。

采用我上面说的方法 如果第n次有球摔碎了，这时两种状况 2的n次方+1层球破了，直接可以确认临界层 
                                                     2的n+1次方层球破了，最多还需要2的n次方-2次确认临界层

在第n次  ，  算法比较次数为   （n+n+2的n次方-2）/2

如果楼层数是M   那么n<=logM


打字不行，在考虑一下临界层应该是均匀分布的，这么一算应该比较好计算出算法复杂度了。

无限个球的话,用正统的算法就可以了

你的算法的话,3个球6次是多少层?

3个球的话

1次：1层
2次：3层
3次：7层
4次：14层
5次：25层
6次：41层

请按你这个.2个球扔4次可以确定多少层?