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

X*X <200
(X+1)X>200
X为整数

以十层为一单元是最合适吧，
大求每次从10*（n）开始
，而求求从10*(n-1)+(i++)
这样最多，大球最多最多要抛10次，
而小球最多要抛8次，
最多时候18次，
而且你是后一回合时，可以从99层抛，这样不用在意第一100层了
举例说：
大球丢的顺序是10,20,30,40,50,60,70,80,90,93,96,99.
小总是从底往上，比如在20时，球碎了，那么小球就可以从10-18层楼开始抛，
就该还要更快的办法吧，注意我的最后是,93.96,99,在10之类三个三个的试似乎更好点了

sum+1=i+(100/i)

+1

[quote=&quot;yeshaoting&quot;]
[size=small;] [/size]



[size=small;]题1 有一栋100层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，用什么最优策略知道这个临界的层是第几层？？？[/size]




[size=small;]顺序查找：从1层往100层试[/size]

public class DynamicP {
	public int[] list = new int[100];
	public void DynamicP()
	{
		for(int i=0;i<100;i++)
		{
			list[i]=0;
		}
	}
	public int t(int y)
	{
		//System.out.println(y);
		if(y==0)
		{
			return 0;
		}
		else if (y==1)
		{
			list[1] = 1;
			return 1;
		}
		int x = min(y);
		list[y-1] = x;
		return x;
	}
	public int max(int x,int y)
	{
		return (x>y?x:y);
	}
	public int min(int y)
	{
		int mi = 9000;
		for(int i=y-1;i>0;i--)
		{
			int z = 0;
			if(list[y-i-1]>0)
			{
				z = list[y-i-1];
			}
			else
			{
				z = t(y-i);
			}
			
			System.out.println("y:"+y+"z:"+z);
			int ma = max(i,1+z);
			System.out.println("max:"+ma);
			mi=(ma>mi?mi:ma);
		}
		return mi;
	}
	public static void main(String[] args)
	{
		System.out.println("begin:::::::");
		int r = new DynamicP().t(100);
		System.out.println("result:::::::"+r);
	}

}

这题目用二分压根不是最佳，如果第一次就碎了，你注定要试50（最坏）
就算平均你算法，你都要试25次。
那么  什么是最佳   。
给定m值,每次玻璃弹珠的最测试楼层是一层
所以间隙是1

那么我们得到1+ 2 +....+ n = m
100层我们得到是多少，N = 14，第一次测试是14，如果破了那么剩下的13楼层找，其中算法都是14次
然后第二次是13，如果破了   那么是1 + 13
.
.
.我们得出   最优化。算法是14,其实按道理，最优算法不是14  要少于14，因为如果我们把14也看作M
中间也可以得到最优算法，

剩下的就是实现的事，不会很难，我相信，其实我刚在打酱油，现在有事做，我想这里的高人一群一群的，

首先随机100内 然后首先得到Math.sqrt(m * 2) +1 = n 近似吧。  
然后开始用算法，然后记录count我想每次都会少于14的！  最不济是14，14不破,13不破，随机的是100 =- -！

- -  补充，14不能优化了，因为只剩下了一个球
然后   第一次14层，不破  第二次14+13层（还可以优化 math.sqrt(86) + 1）第二层是24
算法很简单

package util.check;

import java.util.Random;

public class What {
	private static int[] arr = null;//楼层
	private static int limit = -1;//临界点
	private static boolean a_broken = false;//A玻璃球
	private static boolean b_broken = false;//B玻璃球
	private static int count = 0;//总投次数
	/*
	 * 初始化楼层和临界点
	 */
	public static void init(int len){
		arr = new int[len];
		for(int i = 0; i < len; i++){
			arr[i] = i + 1;
		}
		limit = new Random().nextInt(len) + 1;
		int start = 0;
		int length =  (int) (Math.sqrt((arr.length - 0) * 2) + 1);
		if(length * (length - 1) / 2 >= arr.length ){
			length = length - 1;
		}
		start = len - (length) * (length + 1) / 2 - 1;
		System.out.println("临界点为:" + limit);
		doubleSearch(arr, start, length, count);
	}
	/*
	 * 双球search过程
	 */
	private static int doubleSearch(int[] arr, int start, int len, int count){
		count += 1;
		int newStart = start + len;
		System.out.println(count + "次: a球测试楼层:" + newStart);
		if(a_broken = arr[newStart] >= limit){
			System.out.println("------a玻璃球破灭在楼层" + (newStart) + "------");
			System.out.println("------开始进入单球测试------");
			signleSearch(arr, newStart, len, count);
		}else{
			System.out.println("------继续双球测试------");
			len = (int) (Math.sqrt((arr.length - newStart) * 2) + 1);
			if(len * (len - 1) / 2 >= arr.length - newStart){
				len = len - 1;
			}
			
			doubleSearch(arr, newStart, len, count);
		}
		return -1;
	}
	/*
	 * 单球search过程
	 */
	private static int signleSearch(int[] arr, int start, int len, int count){
		if(start < 0){
			start = 0;
		}
		for(int i = 0; i < len; i++){
			int newStart = start - len + i;
			System.out.println((++count) + "次: b球测试楼层:" + (newStart));
			if(b_broken = arr[newStart] >= limit){
				System.out.println("------b玻璃球破灭，找到临界点------");
				return newStart + 1;
			}
		}
		return limit;
	}
	
	public static void main(String[] args) {
		init(100);
	}
}

这个回答很好，起码回答是正确的

但是可以做一些假设优化一下
先重点说一下前提，球是会碎的，碎了就不能用了

所以，可以有很多方法：
1、前面所说，从代码角度，可以先做二分试探，然后最后剩下一个球时逐层查找
2、也可以两个两个的查，例如100、98、96...
无论怎么做都是可以的，但效率的话，可以先做些假设：
前提假定只有100层，我们可以假定例如临界层在4、16、32、64之类的，然后分
析各个解在各种方法上的效率，就可以总结出一种最优方法出来(ps:实际上，还要考虑上楼和下楼的消耗，毕竟没有提供升降机)。