java - 优化递归方法

Question

我有一些代码需要运行一些相当大的数字，并且它涉及递增到递归方法，因此速度非常慢，以至于我什至无法得到我想要的答案。有人可以帮我优化一下吗？不过我是初学者，所以我不能做任何非常复杂/困难的事情。

public class Euler012{
    public static void main(String[]args){
        int divisors=0;
        for(long x=1;divisors<=501;x++){
            divisors=1;
            long i=triangle(x);
            for(int n=1;n<=i/2;n++){
                if(i%n==0){
                    divisors++;
                }
            }
            //System.out.println(divisors+"\n"+ i);
            System.out.println(i+": " + divisors);
        }
    }
    public static long triangle(long x){
        long n=0;
        while(x>=0){
            n+=x;
            x--;
            triangle(x);
        }
        return n;
    }
 } 

Answer 1

首先:我不认为这是一个优化问题，因为它是一个小任务，但正如评论中提到的，你做了很多不必要的事情。

好的，现在让我们看看可以在哪些方面进行优化:

递归

递归通常性能不佳，特别是如果您不保存值，这在您的示例中是可能的。

例如:具有保存值的递归三角数函数

private static ArrayList<Integer> trianglenumbers = new ArrayList<>();

public static int triangleNumber(int n){
    if(trianglenumbers.size() <= n){
        if(n == 1)
            trianglenumbers.add(1);
        else
            trianglenumbers.add(triangleNumber(n-1) + n);
    }
    return trianglenumbers.get(n-1);
}

但正如 @RichardKennethNiescior 所提到的，您可以简单地使用以下公式:(n² + n)/2

但是这里我们也可以做优化!你不应该做 /2 而应该做 *0.5 甚至 >>1 (右移)但大多数编译器都会为你做这件事，所以不需要让你的代码不可读

你的主要方法

public static void main(String[]args){
    int divisors = 0; //skip the = 0
    for(long x=1;divisors<=501;++x){ // ++x instead of x++
        divisors=0;
        long i=(x*x + x) >> 1; // see above, use the one you like more
        /*how many divisors*/
        if(i == 1) divisors = 1;
        else{ /*1 is the only number with just one natural divisor*/
            divisors = 2; // the 1 and itself
            for(int n = 2; n*n <= i; ++n){
                if(n*n == i) ++divisors;
                else if(i%n == 0) divisors += 2;
            }
        }
        System.out.println(i+": " + divisors);
    }
}

解释了++x 而不是 x++ 的事情 here

除数部分的数量:除 1 之外的每个数字都至少有 2 个约数(质数、数字本身和 1)要检查一个数有多少个约数，我们只需要找到该数的根(例如 36 -> 它的平方根是 6)36 有 9 个约数(4 个配对){1 和 36、2 和 18、3 和 12、4 和 8、6(和 6)}

1 和 36 被跳过 (for(**int n = 2**))，但计入 divisors = 2第 2、3 和 4 行将除数数量增加了 2如果它是一个平方数 (n*n == i) 那么我们加 1