2018年Java方向C组第十题

如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

输入数据，一个整数n（3<n<10000）,表示测试塔的高度。
输出一个整数，表示最多测试多少次。

例如：
输入：
3

程序应该输出：
2

解释：
手机a从2楼扔下去，坏了，就把b手机从1楼扔；否则a手机继续3层扔下

再例如：
输入：
7

程序应该输出：
3

解释：
a手机从4层扔，坏了，则下面有3层，b,c 两部手机2次足可以测出指数；
若是没坏，手机充足，上面5,6,7 三层2次也容易测出。

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

---

笨笨有话说：
我觉得3个手机太难了，要是2个手机还可以考虑一下。

歪歪有话说：
想什么呢，你！要是1部手机还用你编程啊？那样的话只好从下往上一层一层测。

解析：

Scanner input = new Scanner(System.in);
int fNum = input.nextInt();   //输入楼层高度
int pNum = 3;   //手机数量为3
//定义二维数组，pNum+1行,fNum+1列，+1因为我们从下标1开始使用数组，使用更加方便
//行和列交叉的值保存最终测试次数，例如arr[2][4]里面存储2部手机4层楼需要测试几次。
//题目实际上是要得到数组最后一个元素值，但是我们必须存储所有元素值，因为数组后面的值需要根据前面的值计算出来
int[][] arr = new int[pNum+1][fNum+1];  
for (int i = 1; i < arr.length; i++) {
    for (int j = 1; j < arr[i].length; j++) {
        //如果是只有1楼，那么测试数量就是1
        //如果只有一部手机，楼层数量就是测试数量，
        //并且手机数量越多，测试数量肯定越少，
        //如此赋值后，第一行和第一列是正确的值，其它数组元素值是所有方案中的最大值。
        arr[i][j] = j;
    }
}
//需要理解的部分：
//假设pNum个手机，fNum层楼，开始从任意一层X层丢手机，测试次数如下，两种情况
//手机摔坏：测试次数arr[pNum][fNum] = arr[pNum-1][X-1]
//手机完好：测试次数arr[pNum][fNum] = arr[pNum][fNum-X]
//从X层丢手机只是一种方案，题目意思是要求最优方法的最大值，所以在此单独方案下，求测试次数
//实际上是求该方案下的最大值，即：
//Math.max(arr[pNum-1][X-1],arr[pNum][fNum-X])

//从第二个手机开始循环，因为一个手机的时候arr数组里面已经是正确值了
for (int p = 2; p <= pNum; p++)  
{
    //从第二层楼开始循环，因为第一层楼的时候arr数组里面已经是正确值了
    for (int f = 2; f <= fNum; f++) 
    {
        //此循环求一共p个手机，f层楼的测试次数
        //遍历所有方案，即从第1，第2，。。。直到第f层楼开始先扔手机
        for (int i = 1; i <= f; i++) 
        {
            //Java中int类型数组元素默认值为0，所以当i-1或f-i等于0的时候实际上向上和向下是没有次数的，
            //正好和0的值匹配，不影响程序
            int wrong = arr[p-1][i-1] + 1;  //手机摔坏的情况
            int good = arr[p][f-i] + 1;       //手机完好的情况
            //求最优方案的最大测试次数，所以本次方案次数为
            int count = Math.max(wrong, good);
            //由于arr存储的是最优方案，所以把本次方案需要和以前方案比较得到最小值
            arr[p][f] = Math.min(arr[p][f], count);
            //举例循环第一次p=2,f=2,i=1,即求2部手机，2层楼的次数
            //wrong = arr[p-1][i-1] + 1 = arr[1][0] + 1 =0 + 1 = 1
            //good = arr[p][f-i]+1 = arr[2][1] + 1 = 1+1=2
            //count = Math.max(wrong, good) = 2
            //arr[2][2] = Math.min(arr[p][f], count) = Math.min(2, 2) = 2
            //就这样依次循环下去可以将arr数组所有元素全部填满，最后一行，最后一列就是题目要的答案
        }
    }
}
System.out.println(arr[pNum][fNum]);

备注：具体图解如下：
（1）数组定义：

捕获.PNG

（2）过程推理

捕获.PNG