【算法】一个小算法的非递归模式的两种实现
【算法】一个小算法的非递归方式的两种实现
某幢大楼有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)的空间，将每种层高的最佳方式从小到大先计算出来存储在数组中。然后在需要使用递归调用的地方直接取数组中的值进行计算即可。
- 算法实现
public class GlassBallAlgorithm {
public static void main(String[] args) {
GlassBallAlgorithm glassBallAlgorithm=new GlassBallAlgorithm();
glassBallAlgorithm.FindBestWays();
}
//楼层层高
static final int n=100;
//层高为index(1,2...n)时，最佳方法的最坏试验次数
static int[] maxTime=new int[n+1];//为了方便计算，从index=1开始存储
//层高为index(1,2...n)时，最佳方法中第一个检查的楼层
static int[] bestLayer=new int[n+1];//为了方便计算，从index=1开始存储
//为每种层高找到最佳方法
void FindBestWays(){
for(int i=1;i<maxTime.length;i++){
maxCount(i);
}
print();
}
//计算最高位n层的楼的最佳检查方法
void maxCount(int n)
{
if(n<=2){
maxTime[n]=n;//这里我们假设有可能100层都摔不坏，因此当n=2时，如果检查了其中的一层，还需要检查另一层
bestLayer[n]=1;
}
else{
maxTime[n]=n;//最佳方法的最大检查次数
for(int i=1;i<n;i++){
int longerSide=(1+maxTime[n-i]>i)?(1+maxTime[n-i]):i;
if(maxTime[n]>longerSide){
maxTime[n]=longerSide;
bestLayer[n]=i;//最佳方法中第一次检查的层
}
}
}
}
void print(){
System.out.println("使用最佳方法在最坏情况下需要检查"+maxTime[n]+"次。");
int floor=n;//最高层数
int i=0;//基数
//打印最好情况下的检查过程
System.out.println("最佳方法在最坏情况下的检查顺序为：");
while(floor>1){
System.out.println("=>检查第"+(bestLayer[floor]+i)+"层");
i+=bestLayer[floor];
floor=floor-bestLayer[floor];
}
System.out.println("=>检查第"+n+"层");
}
} 对于n=100，输出的结果为：
使用最佳方法在最坏情况下需要检查14次。 最佳方法在最坏情况下的检查顺序为： =>检查第9层 =>检查第22层 =>检查第34层 =>检查第45层 =>检查第55层 =>检查第64层 =>检查第72层 =>检查第79层 =>检查第85层 =>检查第90层 =>检查第94层 =>检查第97层 =>检查第99层 =>检查第100层
- 算法复杂度
空间复杂度为O(n)
时间复杂度为1+1+2+3+…+(n-2)+(n-1)，明显为O(n^2)。
解决方案2
写完方案1，查看了输出结果，才发现自己2了=. =其实算法可以很简单。
我们假设最坏情况下的最佳检查次数为n。
- 首先检查第m1层（此时共检查1次），m1必须小于等于n。（因为如果m1层摔碎了第一个玻璃珠，那么需要使用第二个玻璃珠依次检验1到m1之间的楼层，总检查次数不能大于n）
- 如果没摔碎则向上检查第m2层（此时共检查了2次），此时m1到m2之间最多有n-2个楼层。（因为如果m2层摔碎了第一个，那么需要使用第二个玻璃球依次检验m1与m2之间的楼层，总检查次数不能大于n）。
- 以此类推，m2到m3之间最多有n-3个楼层...
如果将上面的思路反向思考。最好的解决方式就是：在最坏情况下，最后检查第100层，倒数第二检查第99层，第99-2层，第(99-2)-3层，第(99-2-3)-4层...
- 算法实现
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)。