java - 欧拉计划 12 - 优化

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

这个问题似乎与 help center 中定义的范围内的编程无关。 .

已关闭 9 年前。

Improve this question

我正在研究Project Euler Problem 12 。任何人都可以提供有关如何改进我的代码以便它在我的有生之年执行的任何提示吗？

public class HighlyDivisibleTriangularNumber {

public static void main(String[] args) {
    int divisors = 0;
    int count = 1;
    while(divisors <= 501) {
        long triNum = triangularNumber(count);
        divisors = getFactors(triNum);
        System.out.println(triNum+"_"+divisors);
        count++;
    }
}

private static int getFactors(long triNum) {
    int divisors = 0;
    while(triNum > 1) {
        triNum = triNum / 2;
        divisors++;
    }
    return divisors;
}

private static long triangularNumber(int i) {
    long total = 0;
    for(int k = 1; k <= i; k++) {
        total += k;
    }
    return total;
}
}

Answer 1

1) 三角形数

您可以做的第一个(可能也是最重要的)优化是计算三角数的方式。

您可以观察到第 n 个三角形数(我们称之为 t(n) )等于 n + t(n-1)。因此，每次计算三角数时，只需将前面的三角数加上 n 即可。这将导致朴素的递归函数:

private static long triangularNumber(int i) {
    if(i == 1) return 1;
    else return i+triangularNumber(i-1);
}

但这不会提高性能太多......要解决这个问题，我建议你对内存进行一些研究并调整我给你的函数(我不会给你答案，这是一个很好的练习)

现在，在普通计算机上，您应该在合理的时间内得到问题的答案。但还可以改进一点

2) 计算除数

您计算除数的函数是错误的。您应该做的就是尝试将您的数字除以连续的自然数，然后看看结果是否是自然整数。

private static int getFactors(long triNum) {
    int divisors = 0;
    for(int i = 1; i <= triNum; ++i) {
        if(triNum%i == 0) // triNum is a multiple of 1 <=> i is a divisor of triNum
          divisors++;
    }
    return divisors;
}

您甚至可以通过仅计算 trinum 的平方根并每次添加两个除数来改进这一点。但如果你这样做的话，有一个技巧，如果你决定尝试这个，我会让你弄清楚。