如何在java中最小化函数调用

1cklez4t  于 2021-08-20  发布在  Java
关注(0)|答案(1)|浏览(347)

关闭。这个问题需要详细或明确。它目前不接受答案。
**想改进这个问题吗?**编辑这篇文章,添加细节并澄清问题。

昨天关门了。
改进这个问题
我有一个功能,它可以查找有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)方法的调用数。如果我们发现任何版本有问题,那么从那里所有剩余的版本都会有问题。

bf1o4zei

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):

public class Example {
    public static void main(String[] args) {
        System.out.println(findFirstBadRelease());
    }

    public static boolean isBadRelease(int releaseNumber){
        //change 260 to whatever you want where the first faulty should be
        return releaseNumber >= 260 ? true: false;
    }

    public static int findFirstBadRelease(){
        // call from 1 to N where 1<=N<=500
        //Line 1
        int n = 256;
        int t = n/2;
        int iterations = isBadRelease(n) ? 8 : 9;

        for(int i = 0; i < iterations; i ++){
            n =  isBadRelease(n) ? n - t : n + t;
            t =  t == 1 ? t : t / 2;
        }
        return n;
    }
}

注意:当n增长时,更改硬编码值,如256、8、9

相关问题