【算法】一个小算法的非递归方式的两种实现
某幢大楼有100层。你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候，一定会有两个结果，玻璃珠碎了或者没碎。这幢大楼有个临界楼层。低于它的楼层，往下扔玻璃珠，玻璃珠不会碎，等于或高于它的楼层，扔下玻璃珠，玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式，使得在该方式下，最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。
最容易理解的方法是递归。
当楼层层高为n时，我们使用第一个玻璃珠检查第i层是否能摔碎。
如果摔碎了，我们只好谨慎的使用第二个玻璃珠，从第1层开始检查，直到第i-1层。共检查了1+(i-1)次。如果木有摔碎，我们需要对上面的(n-i)层进行检查，此时与检查一个层高为(n-i)的楼的方法是一样的。我们假设对上面的(n-i)层的检查的最佳方法是P(n-i)。共检查了1+P(n-i)次。
因此从i层开始检查的这种方式的最差情况是1+(i-1)与1+P(n-i)较差的那个（次数较多的那个）。
我们 依次令i=1,2,…n,可以得到一个最差情况下检查次数最少的i。这个i就是最佳情况中第一次检查的楼层。
以此类推，直到第一个玻璃球摔碎或检查到只剩一层或两层为止。我们就可以得出最佳情况下每次检查的楼层，以及总共检查的次数。
得出递归式：
对于n=1或2, P(n)=1
当n>2, P(n)=min[ max(1,1+P(n-1)), max(2,1+P(n-2)), …, max((n-1), 1+P(1)) ]
当然，我们可以通过递归式来编写递归的方法求出层高为100时的最佳方法。但是明显这种方法会重复对某种层高进行计算。为了减少时间复杂度，我们开辟了O(n)的空间，将每种层高的最佳方式从小到大先计算出来存储在数组中。然后在需要使用递归调用的地方直接取数组中的值进行计算即可。
import java.util.ArrayList; public class EasySolution { static final int n=100; static ArrayList<Integer> selectedLayers=new ArrayList<Integer>();//反向存储最坏情况下所有选择检查的楼层 static int count=0;//最坏情况下检查的次数 public static void main(String[] args) { EasyWay(); } static void EasyWay(){ int m=n; for(int i=0;m>0;i++,m-=i){ selectedLayers.add(m); count++; } print(); } static void print(){ //打印最优方案 System.out.println("最优方法在最差情况下需要检查"+count+"次。"); System.out.println("最佳方法在最坏情况下的检查顺序为："); for(int i=selectedLayers.size()-1;i>=0;i--){ System.out.println("=>检查第"+selectedLayers.get(i)+"层"); } } }复杂度这种方法时间空间复杂度都为O(n)。