经典谷歌面试题：高楼扔鸡蛋

本文主要是介绍经典谷歌面试题：高楼扔鸡蛋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

经典谷歌面试题：高楼扔鸡蛋

存在某T层高楼，在该高楼中存在这样的一层，在该层之下的所有楼层扔鸡蛋，鸡蛋摔到地上都不会碎，还可以继续扔；在该层及该层之上的所有楼层，扔下鸡蛋都会摔碎。
目前手里有两个鸡蛋，怎样扔才能在最坏情况下，使得扔的次数最小。

Java代码如下，更改楼层层高T，可输入扔鸡蛋的最小次数。

package code.improved;
public class ThrowEggs {//谷歌高楼扔鸡蛋问题//从T层高楼扔下鸡蛋，用何种方式使得在最坏情况下，使尝试的次数最少public static void main(String[] args) {int T=39;int[] mall=new int[T+1];//初始化一个数组，用于存储递归过程中的中间数据System.out.println(f(T,mall));   }//递归算法static int f(int n,int[] mall){if(n<0) System.out.println("error");if(n==0) return mall[0]=0;if(mall[n]!=0) return mall[n];int fn_1=f(n-1,mall);//递归函数的结果赋值给局部变量，让递归函数只执行一遍。//将f(n-i)的第一个结果f(n-1)的结果赋值给minResult，以方便后面循环中的比较。int result=0,minResult=0>=fn_1?1:fn_1+1;//遍历不同的i，找到最小的f(n)作为返回for (int i = 2; i <= n; i++) {int fn_i=f(n-i,mall);result=i-1>=fn_i?i:fn_i+1;minResult=result<minResult?result:minResult;}   return mall[n]=minResult;}
}

改进版，可以输入扔鸡蛋的策略

package code.improved;
public class ThrowEggsStrategy {//“改进版”谷歌高楼扔鸡蛋问题，能够输出扔鸡蛋的楼层//从T层高楼扔下鸡蛋，用何种方式使得在最坏情况下，使尝试的次数最少public static void main(String[] args) {int T=100;int[] mall=new int[T+1];//初始化一个数组，用于存储递归过程中的中间数据//用来存储扔鸡蛋的楼层信息，如100层的高楼，第一个扔的鸡蛋是在14层，则throwEggs[100]=14;int[] throwEggs=new int[T+1];System.out.println("在最坏情况下，至少要扔鸡蛋的次数为："+f(T,mall,throwEggs));   //输入扔鸡蛋的策略int floor=0;for (int i = throwEggs.length-1; i >=1; i=i-throwEggs[i]) {floor+=throwEggs[i];System.out.println("对于高度为"+T+"的楼层,应该在"+floor+"层扔鸡蛋");}}//递归算法static int f(int n,int[] mall,int[] throwEggs){if(n<0) System.out.println("error");if(n==0) return mall[0]=0;if(mall[n]!=0) return mall[n];int fn_1=f(n-1,mall,throwEggs);//递归函数的结果赋值给局部变量，让递归函数只执行一遍。//将f(n-i)的第一个结果f(n-1)的结果赋值给minResult，以方便后面循环中的比较。int result=0,minResult=0>=fn_1?1:fn_1+1;//遍历不同的i，找到最小的f(n)作为返回for (int i = 2; i <= n; i++) {int fn_i=f(n-i,mall,throwEggs);result=i-1>=fn_i?i:fn_i+1;minResult=result<minResult?result:minResult;}    //已获得minResult，再找一遍，输出是在哪个i获得的minResult//该循环中，对于i使用逆序的原因是，尽量从较高的楼层扔鸡蛋，使得满足条件的扔鸡蛋的楼层更高，跨度更大一些。for (int i = n; i >= 1; i--) {int fn_i=f(n-i,mall,throwEggs);result=i-1>=fn_i?i:fn_i+1;if(minResult==result){//System.out.println("对于高度为"+n+"层的高楼，在第"+i+"层扔出鸡蛋。");throwEggs[n]=i;//对于某个n层高楼，可能存在多个楼层扔出鸡蛋，使得扔鸡蛋的次数最小。//即，存在多个i可以使得minResult最小。因此只需要一个值即可，故用break跳出循环。   break;}; }return mall[n]=minResult;}
}