刚在电脑报上看到一道有意思的题说是Google校园招聘的其中一道面试题
“有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎，用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。”
大家都是怎么想的都来说说吧...........
“有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎，用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。”
大家都是怎么想的都来说说吧...........
从下向上，两层两层的找google是比较变态，不过如果lz不给我点分也不够意思
2,4,6,8,....这样每层扔一次。
如果n层摔了，就到n-1层，如果这次又坏了，说明临界是n,否则就是n-1
if ok
直接跳到6楼
else
2楼丢一个（可以判断）6楼
if ok
to 9楼
else
5楼丢一个（可以判断）假设在50楼，一共需要丢18次，上下楼捡棋子需要9次
我觉的先在50楼丢一个 再用 fool_leave 的方法是不是会更好啊
6楼不可以
还有4楼、5楼需要查，只有一个棋子
从4楼扔下来，如果碎了，ok，3楼临界点
如果没碎，从5楼扔下来，如果碎了，4楼临界点，否则5楼临界点
6楼
if ok
to 9楼
else
5楼丢一个（可以判断）你的程序。
应该改成
else
4楼丢一个
其中[100/n]表示取上整。
都是隔n层，碎了，然后从(k-1)*n向上丢
to baiyunyuan2(白云无限) (
隔3层：最大尝试次数：n+[100/n]＝35＋
隔10层：最大尝试次数：不会超过20
就是 masse(当午) 的
＂用数学方法来解释一下阿丹的方法为什么最少吧代价:等价于求得一个数n，使得n+[100/n]的值最小 1<n<100
其中[100/n]表示取上整。＂
再详细点说说吧
旗 鲁 特
(n-1)：在某一层摔了，就要从(k-1)*n层，一层一层往上丢，一直到k*n-1
k*n-1 -(k-1)*n = n-1所以最大次数：n-1+【100/n】我最开始给出的方法是错的，因为最多可能跑51次
另外，大家是怎么定义1楼的？1楼通常就是地面吧，所以1楼一定不会碎，是吗？
如果这样，一楼就可以跳过了公式修改为：(n-1)+【99/n】
【】定义为取下整n=10的时候，先从11层开始丢，然后21,31,41,....,91如果在91坏了，就从82,83...90
一共18次（这个是最坏的情况）如果91没坏，这个时候还有两个好的棋子。
就从91开始，剩下9楼，继续套用上面的公式，得出n=3
然后从94，97开始....
如果在所有层碎的概率是相同的，那么平均次数为100/2n+(n-1)/2。求使得该表达式的值最小的n的值，求该函数的微分，得到1-100/n^2, n=10，该微分为0，说明，在 0<n<10的区间，随着n的增大，函数值减少，在 10<n<100的区间，随着n的增大，函数值增大，因此n=10的时候，函数值是1-100的区间中的最小值。
因此该题的解决方案为每隔10层仍1次
如果选择:
A）先从2楼扔一个 int i=2;
for(i=2;i<=100;i+=2)
{
if(m1没碎){ //丢下程序boolbreak(int m,int i)
continue;
}else{
i-=1;
if(m2没碎){
printf(i+1是临界层);
break;
}else{
printf(i是临界层);
break;
}
}
}
B)先从50楼扔一个
int i=50;
if(m1碎了){
for(i=1;i<50;i++){
if(m1碎了){
printf(i是临界层);
break;
}
}
}else(m1没碎){
for(i=51;i<=100;i++){
if(m1碎了){
printf(i是临界层);
break;
}
}
}
分析两种算法的效率;
如果是在临界层随即均匀
A的平均循环次数是(2+1+3+2+4+3+...+51+50)/100={51+2*(1+50)*50/2}/100
=(51+51*50)/100
=26.01次
B的平均循环次数是{1+(1+2+3+...+50)+(1+2+3+...+50)}/100={1+2*(1+50)*50/2}/100
=(51*50+1)/100
=25.51次
至于100和50的特殊判断,省略之.
故相对而言 B方法好一点....鄙视下,有从50楼扔下还不碎的玻璃吗~~
==================================================================
我支持你
找到一个知道答案的人（这个人肯定存在，要不然Google早就黄了）把这两个玻璃球跟他交换让他告诉你那个楼层，如果你幸运，你还能剩一个。要不就是把所有面试的都叫来，每层一个人，扔那个玻璃球，保证能找到。最后大家一人剩一个玻璃球多好。
____________________________________________________
顶你,我是google就录用你了,哈哈(这才叫众智成城)
/*
* 理解题目为：高于99层围棋子一定会碎。
*
*
*
*
*
*
* */public class OutPut {
ClassBall b1;//创建两个玻璃小球；
ClassBall b2;//创建两个玻璃小球；
int min ;//1楼
int max ;//100楼
int critical;//临界值
int total;//b1扔的次数；
int total1;//b2扔的次数；
List<Integer> i_arr;//记录b1球每次扔楼层。
OutPut(){
b1 = new ClassBall();
b2 = new ClassBall();
min = 1;
max = 100;
critical = 1;
i_arr = new ArrayList<Integer>();
b1.setBreakornot(false);
b2.setBreakornot(false);
}
public void GetBreak(ClassBall b/*传入b1*/,int randomi){
int k ;
while (!b.breakornot){
total++;
critical =(int)(((critical+100)/2));//二分法？
System.out.println("第一个小球扔于"+critical+"层");
i_arr.add(critical);
if ( randomi<= critical){
b.setBreakornot(true);
k = i_arr.size();
if (k >1){
for (int i = i_arr.get(k-2)+1; i <= i_arr.get(k-1); i++) {
total1++;
System.out.println("第二个小球扔于"+i+"层");
if (randomi==i){
b2.setBreakornot(true);
System.out.println("两个小球都碎了");
System.out.println("小球1扔了"+total+"次");
System.out.println("小球2扔了"+total1+"次");
System.out.println("临界为："+i+"层,通过扔球"+(total+total1)+"次确定.");
break;
}
}
}
else{
for (int i =1; i <= i_arr.get(k-1); i++) {
total1++;
System.out.println("第二个小球扔于"+i+"层");
if (randomi==i){
b2.setBreakornot(true);
System.out.println("两个小球都碎了");
System.out.println("小球1扔了"+total+"次");
System.out.println("小球2扔了"+total1+"次");
System.out.println("临界为："+i+"层,通过扔球"+(total+total1)+"次确定.");
break;
}
}
}
}
}
} public static void main(String[] args) {
OutPut out = new OutPut();
out.GetBreak(out.b1,49);
}}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
下午交空闲，代码实现了一下，请高手指出错误。其中GetBreak函数的randomi参数是手工指定围棋子摔碎的楼层，通过算法推断出这个楼成数。
public class ClassBall {
ClassBall(){}
public void setBreakornot(boolean br){
breakornot=br;
}
public boolean getBreakornot(){
return breakornot;
}
public void setBreakceng(int bi){
breakceng=bi;
}
public int getBreakcengt(){
return breakceng;
}
public boolean breakornot;
public int breakceng;}
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
这个只是辅助的类。
题目明确了->两个相同的玻璃棋子.同意 danjiewu(阿丹) 的算法。。均衡一下他的比较好。我的那个算法要是第一个棋子在50层碎的那么第二个棋子就得从1层扔到50，哎~^_^。
从2层开始
2,4,6,8,....这样每层扔一次。
如果n层摔了，就到n-1层，如果这次又坏了，说明临界是n,否则就是n-1不要做书呆子,光想着编程中如何更快,也不想想如果超过2层放下第一颗后碎了,你下一颗放到那?
难道从1层开始,1 层1曾试吗?不过我觉得出这道题的人本身就是个傻子,大家想想,如果这个棋子摔了10次,已经都裂的不行了,
只要从1层丢下来就能摔得粉碎,那能得到正确的结果吗?
一楼一定要扔
所以 同意 danjiewu(阿丹) 的算法
2,4,6,8,....这样每层扔一次。
如果n层摔了，就到n-1层，如果这次又坏了，说明临界是n,否则就是n-1
求模的累加式子怎么简化? 比如(1%n + 2%n + 100%n) 1<n<100答案：
(1%n + 2%n + 100%n)
= 1+2+...+(n-1)+0+1+2+...+(n-1)上面这个你自己再总结一下，就出来了。
我认为临界值会超过１０楼吗？所以我还是支持masse(当午)的方法 因为１０楼以下，咱们的算法比 阿丹 的快当午你别那么快放弃啊 哈哈