【算法】一个小算法的非递归方式的两种实现

某幢大楼有100层。你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候，一定会有两个结果，玻璃珠碎了或者没碎。这幢大楼有个临界楼层。低于它的楼层，往下扔玻璃珠，玻璃珠不会碎，等于或高于它的楼层，扔下玻璃珠，玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式，使得在该方式下，最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。

解决方案1（一个非常容易理解的方案，但是时间复杂度较高）

算法分析

最容易理解的方法是递归。

当楼层层高为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)。