关闭。这个问题需要详细或明确。它目前不接受答案。
**想改进这个问题吗?**编辑这篇文章,添加细节并澄清问题。
昨天关门了。
改进这个问题
我有一个功能,它可以查找有n个版本的软件应用程序的a错误版本。计算方法如下所示:
public boolean isBadRelease(int releaseNumber){
List<Application> apps= new ArrayList<>();
for(Application app:apps){
if(app.checkForFaulty(releaseNumber))
return true;
else
return false;
}
return false;
}
public boolean findFirstBadRelease(int N){
// call from 1 to N where 1<=N<=500
//Line 1
for(int i=0;i<N;i++)
isBadRelease(n);
}
如何减少对第1行的isbadrelease(n)方法的调用数。如果我们发现任何版本有问题,那么从那里所有剩余的版本都会有问题。
1条答案
按热度按时间bf1o4zei1#
因为在第一个故障版本之后,所有剩余的都是错误的,您可以在中间开始测试,将整个范围划分为两个,根据结果,可以通过将一半的一半(1/第四)加到或减去一半来缩小范围。
例如,如果n=500,则一半为250
检查版本是否正确
250
如果是,则为故障,即第一个故障位于[0, 250]
,再次将该范围一分为二,并检查版本是否正确125
这是错误的。如果125有故障,则第一个故障在范围内[0,125]
否则第一个故障在范围内[125, 250]
如果250
没有故障,则第一个故障保证在范围内[251, 500]
. 将此范围一分为二,然后检查版本250+125 = 375
. 与上述if版本相同的方法375
一次故障的故障范围[250, 375]
范围内的其他[375, 500]
.执行此操作,直到范围仅包含一个数字。无论您的第一个错误在哪里,对方法的调用都将保持不变。对于n=500的示例,对于第一个错误的地方,最多需要调用9次方法。
我刚用过
N/2
作为250
以保持示例的简单性。您需要使用2的幂来生成范围,该范围将以唯一的结果结束。所以起点应该是二的最近幂,等于或大于N/2
. 就你而言256
. 这个数字也定义了你需要多少次迭代。256 = 2^8
,所以您最多需要8 +1
迭代或一般情况下,如果您从2^m
你需要m+1
迭代。上述方法的演示可能如下所示(我已经更改了您的
findFirstBadRelease
至int):注意:当n增长时,更改硬编码值,如256、8、9